Задача 30825

Темы:    [ Ориентированные графы ] [ Индукция (прочее) ]

Сложность: 4- Классы: 8,9

Условие

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

Решение

  Индукция по числу городов. База очевидна.
  Шаг индукции. Удалим один из городов. В силу предположения индукции есть город А с требуемым свойством. Вспомним теперь про удалённый город. Если в него ведёт хотя бы одна дорога, то город А – искомый. В противном случае сам удалённый город удовлетворяет требуемому свойству.

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

книга
Автор	Генкин С.А., Итенберг И.В., Фомин Д.В.
Год издания	1994
Название	Ленинградские математические кружки
Издательство	Киров: "АСА"
Издание	1
глава
Номер	13
Название	Графы-2
Тема	Теория графов
задача
Номер	047