Задача 31088

Темы:    [ Ориентированные графы ] [ Принцип крайнего (прочее) ] [ Принцип Дирихле (прочее) ]

Сложность: 3+ Классы: 6,7,8

Условие

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

Подсказка

Это город, из которого выходит наибольшее число дорог.

Решение

Рассмотрим город A, из которого выходит наибольшее число дороги, и произвольный город B. Если дорога ведёт из A в B, то всё в порядке. Если же дорога ведёт из B в A, то, поскольку из B выходит не больше дорог, чем из A, найдётся город C, в который ведёт дорога из A, но не ведёт дорога из B. Тогда можно из A попасть в B по маршруту ACB.

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

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