В стране 15 городов, и каждый из них связан дорогами по крайней мере с 7 другими. Докажите, что из любого города можно проехать в любой другой по дорогам. Между двумя городами есть только одна дорога.
В стране 15 городов, и каждый из них связан дорогами по крайней мере с 7 другими. Докажите, что из любого города можно проехать в любой другой по дорогам. Между двумя городами есть только одна дорога.
Похожие вопросы
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Предположим обратное, то есть из некоторого города нельзя добраться до какого-то другого. Рассмотрим самый удаленный от него город, к которому нет дороги из исходного. Так как из каждого города есть по крайней мере 7 дорог, то он связан с 7 другими городами, и каждый из этих городов также связан с 7 другими городами и так далее.
Получается, что рассматриваемый нами город имеет подлинные дороги до всех городов, с которыми он соединен цепочкой дорог. А значит, изначальное предположение было неверным, и из любого города можно добраться до любого другого по дорогам.