Страница 67 номер 81, ГДЗ по алгебре за 10 класс к учебнику Бунимовича. Математика вероятность и статистика
Города — вершины, дороги — рёбра; граф связный. Пусть городов \(n\), причём \(n \geqslant 2\).
Будем выбрасывать рёбра, лежащие на циклах: связность сохраняется, ведь между концами удалённого ребра остаётся путь по другой части цикла. Когда циклы кончатся, останется дерево на тех же \(n\) вершинах, а в нём \(n-1\) ребро.
В дереве есть вершина степени 1: сумма степеней равна \(2(n-1) = 2n-2\), а будь каждая степень не меньше 2, сумма была бы не меньше \(2n\). Значит, есть вершина степени не больше 1, а по связности при \(n \geqslant 2\) её степень ровно 1; пусть это город \(X\).
Закроем все дороги, ведущие в \(X\). Любые два других города \(P\) и \(Q\) соединены в дереве цепью, и через \(X\) она не проходит: придя в вершину степени 1, выйти можно только по тому же ребру, а в цепи рёбра не повторяются. Значит, из \(P\) в \(Q\) по-прежнему можно проехать.
Ответ: такой город всегда найдётся: если выбросить из сети все дороги, лежащие на кольцевых маршрутах, останется дерево, а в дереве есть город, в который ведёт ровно одна дорога, — его и надо выбрать.
Заменим железнодорожную сеть графом: вершины — города, рёбра — дороги между ними. По условию из любого города можно попасть в любой другой, то есть граф связный. Пусть городов \(n\), причём \(n \geqslant 2\).
Будем выбрасывать из графа рёбра, лежащие на циклах. Пока цикл есть, любое его ребро можно удалить, и связность сохранится: между концами удалённого ребра остаётся путь по другой части цикла. Когда циклы кончатся, останется связный граф без циклов, то есть дерево на тех же \(n\) вершинах; в нём \(n-1\) ребро.
В этом дереве есть вершина степени 1. Действительно, сумма степеней всех вершин вдвое больше числа рёбер и равна \(2(n-1) = 2n-2\). Если бы каждая вершина имела степень не меньше 2, сумма была бы не меньше \(2n\), а \(2n-2\) меньше, чем \(2n\). Значит, нашлась вершина степени не больше 1, а так как дерево связно и вершин не меньше двух, её степень равна ровно 1. Пусть это город \(X\).
Закроем на ремонт все дороги, ведущие в \(X\). Возьмём два любых других города \(P\) и \(Q\): в дереве их соединяет цепь, и через \(X\) она не проходит — придя в вершину степени 1, выйти из неё можно только по тому же ребру, а в цепи рёбра не повторяются. Значит, все дороги этой цепи уцелели, и из \(P\) в \(Q\) по-прежнему можно проехать.
Ответ: такой город всегда найдётся: если выбросить из сети все дороги, лежащие на кольцевых маршрутах, останется дерево, а в дереве есть город, в который ведёт ровно одна дорога, — его и надо выбрать.
