Задача 35089

Тема:    [ Связность и разложение на связные компоненты ]

Сложность: 3+ Классы: 9,10,11

Условие

В стране n городов. Между каждыми двумя городами установлено воздушное сообщение одной из двух авиакомпаний. Докажите, из этих двух авиакомпаний хотя бы одна такова, что что из любого города можно попасть в любой другой рейсами только этой авиакомпании.

Решение

См. задачу 30814 а).

Источники и прецеденты использования

книга
Автор	Иванов С.В.
Название	Математический кружок
глава
Номер	5
Название	Графы
Тема	Теория графов
задача
Номер	03
web-сайт
задача