ГДЗ по алгебре 7 класс Мерзляк Базовый уровень номер - 203

Представим схему метрополитена как сеть, где станции — это точки (вершины), а перегоны между соседними станциями — соединяющие их линии. По условию задачи эта сеть является связной: с любой станции можно доехать до любой другой. 1. Если в схеме метро есть замкнутые кольцевые маршруты (циклы), мы можем мысленно убрать один перегон из любого кольца. Возможность добраться от любой станции до любой другой при этом сохранится, так как вместо убранного участка всегда можно проехать по оставшейся части кольца. 2. Будем последовательно убирать по одному перегону из каждого имеющегося кольца до тех пор, пока замкнутых маршрутов вовсе не останется. В результате получится связная сеть, объединяющая все станции города и не содержащая ни одного кольца (в математике такую структуру называют деревом). 3. В любой связной сети без колец обязательно есть хотя бы одна тупиковая (конечная) станция, которая соединена перегоном только с одной-единственной соседней станцией. *(Действительно, если выйти с любой станции и двигаться по перегонам, не проходя дважды через одну и ту же станцию, то из-за конечного числа станций мы рано или поздно окажемся на станции, из которой нет других выходов, то есть на тупиковой).* 4. Выберем такую тупиковую станцию и закроем её. Так как к ней ведёт ровно один перегон, ни один маршрут между любыми двумя другими станциями не мог проходить через неё транзитом (попав на эту станцию, можно было только развернуться и поехать назад по тому же перегону). 5. Следовательно, при закрытии тупиковой станции все пути между остальными станциями сохраняются даже в упрощённой сети, а значит, и в исходной схеме метро сообщение между всеми оставшимися станциями не нарушится. Что и требовалось доказать.