Страница 67 номер 87, ГДЗ по алгебре за 10 класс к учебнику Бунимовича. Математика вероятность и статистика
В стране 13 городов, каждый из которых соединён авиасообщением с 6 другими. Докажите, что из любого города можно добраться в любой другой (возможно, с пересадками).
Города — вершины, авиалинии — рёбра; степень каждой вершины равна 6.
Пусть граф несвязный — он распадается не меньше чем на две компоненты. Возьмём в любой компоненте город \(X\): все 6 городов, с которыми он соединён, лежат в той же компоненте, значит, в ней не меньше \(1 + 6 = 7\) городов. То же верно про каждую компоненту, поэтому городов не меньше \(2 \cdot 7 = 14\).
Но городов 13, и \(13 < 14\) — противоречие, граф связный.
Ответ: сеть связна: каждая её часть содержала бы не меньше 7 городов, а на две такие части 13 городов не хватает, поэтому часть одна и из любого города можно долететь в любой другой, возможно, с пересадками.
В стране 13 городов, каждый из которых соединён авиасообщением с 6 другими. Докажите, что из любого города можно добраться в любой другой (возможно, с пересадками).
Города — вершины графа, авиалинии — рёбра; степень каждой вершины равна 6.
Предположим противное: граф несвязный. Тогда он распадается не меньше чем на две компоненты связности.
Возьмём любую компоненту и любой город \(X\) в ней. Все 6 городов, с которыми \(X\) соединён, лежат в той же компоненте — они соединены с \(X\) ребром. Значит, в компоненте не меньше \(1 + 6 = 7\) городов. То же верно про каждую компоненту, поэтому городов в стране не меньше \(2 \cdot 7 = 14\).
Но городов 13, и \(13 < 14\) — противоречие. Значит, граф связный, и между любыми двумя городами есть путь.
Ответ: сеть связна: каждая её часть содержала бы не меньше 7 городов, а на две такие части 13 городов не хватает, поэтому часть одна и из любого города можно долететь в любой другой, возможно, с пересадками.
