Страница 56 номер 78, ГДЗ по алгебре за 10 класс к учебнику Бунимовича. Математика вероятность и статистика
Докажите, что если между двумя различными вершинами графа есть путь, то существует и цепь, которая их соединяет.
Пусть \(u\) и \(v\) — различные вершины графа и между ними есть путь. Длина каждого пути — целое неотрицательное число, поэтому среди путей из \(u\) в \(v\) есть самый короткий; возьмём его.
Все вершины в его записи различны. Предположим, что вершина \(w\) встречается дважды, и вычеркнем всё, что записано между её первым и вторым появлением, вместе со вторым появлением. Оставшаяся последовательность снова путь из \(u\) в \(v\): вершина, стоявшая после второго появления \(w\), соединена ребром именно с \(w\). Но вычеркнуто хотя бы одно ребро, и путь стал короче кратчайшего — противоречие.
Раз все вершины различны, различны и все рёбра: ребро задаётся парой соседних вершин, а все такие пары разные.
Путь без повторяющихся рёбер — это цепь, значит, кратчайший путь из \(u\) в \(v\) и есть искомая цепь.
Ответ: утверждение доказано: если между двумя различными вершинами есть путь, то кратчайший из таких путей не содержит повторяющихся вершин, а потому и повторяющихся рёбер, то есть является цепью, соединяющей эти вершины.
Докажите, что если между двумя различными вершинами графа есть путь, то существует и цепь, которая их соединяет.
Пусть \(u\) и \(v\) — различные вершины графа и между ними есть путь. Требуется найти цепь, то есть путь без повторяющихся рёбер, соединяющий \(u\) и \(v\).
Путей из \(u\) в \(v\) может быть много, но длина каждого — целое неотрицательное число, поэтому среди всех таких путей есть самый короткий, то есть содержащий наименьшее число рёбер. Возьмём его и покажем, что он и является цепью.
Сначала убедимся, что в записи этого пути все вершины различны. Предположим, что какая-то вершина \(w\) встречается в записи дважды. Вычеркнем всё, что записано между её первым и вторым появлением, вместе со вторым появлением. Оставшаяся последовательность снова является путём из \(u\) в \(v\): до вершины \(w\) и после неё соседние вершины по-прежнему соединены рёбрами, потому что вершина, стоявшая после второго появления \(w\), соединена ребром именно с \(w\). При этом вычеркнуто хотя бы одно ребро, значит, новый путь короче прежнего. Это противоречит тому, что прежний путь был самым коротким.
Значит, все вершины кратчайшего пути различны. Тогда различны и все его рёбра: ребро пути задаётся парой соседних вершин, а раз все вершины разные, то и все такие пары разные, и ни одно ребро не встретится дважды.
Путь без повторяющихся рёбер — это цепь. Значит, кратчайший путь из \(u\) в \(v\) и есть искомая цепь.
Ответ: утверждение доказано: если между двумя различными вершинами есть путь, то кратчайший из таких путей не содержит повторяющихся вершин, а потому и повторяющихся рёбер, то есть является цепью, соединяющей эти вершины.
