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

Рассмотрим вариант решения задания из учебника Бунимович, Булычев 10 класс, Просвещение: 81. В некоторой стране железнодорожная сеть устроена так, что можно попасть из любого города в любой другой (возможно, через другие города). Докажите, что всегда можно выбрать такой город, что если закрыть на ремонт все ведущие в него дороги, то всё равно можно будет попасть из любого города в любой другой (кроме самого выбранного города).

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

Рассмотрим самый длинный простой путь в этом графе. Обозначим его вершины через $$v_1, v_2, \dots, v_k.$$

Возьмём один из его концов, например город $$v_1.$$ Докажем, что после удаления всех дорог, ведущих в этот город, остальные города по-прежнему останутся связными.

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

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

Ответ

Такой город всегда существует: достаточно взять конец самого длинного простого пути в связном графе.