Упр.78 ГДЗ Бунимович Булычев 10 класс (Алгебра)

Рассмотрим вариант решения задания из учебника Бунимович, Булычев 10 класс, Просвещение: 78. Докажите, что если между двумя различными вершинами графа есть путь, то существует и цепь, которая их соединяет.

Пусть между двумя различными вершинами графа существует путь. Тогда этот путь можно записать как последовательность вершин и рёбер, в которой некоторые вершины могут повторяться.

Если в пути есть повторяющаяся вершина, то участок между двумя её одинаковыми вхождениями образует замкнутый фрагмент. Этот фрагмент можно удалить, не нарушая соединения начальной и конечной вершин пути.

Повторяя такое удаление для всех повторяющихся вершин, получим маршрут без повторений вершин. А такой маршрут и есть цепь.

Следовательно, если между двумя различными вершинами графа есть путь, то существует и цепь, соединяющая эти вершины.

Ответ

Если между двумя различными вершинами графа существует путь, то из него можно удалить все повторяющиеся вершины и получить цепь, соединяющую эти вершины.