Дано: в одном государстве 100 городов, и каждый соединен с каждым дорогой с односторонним движением.
Найти: доказать, что можно поменять направление движения на одной дороге так, чтобы от любого города можно было доехать до любого другого.
Решение:
Предположим, что существует хотя бы одна пара городов, между которыми невозможно доехать, если следовать только по текущему направлению движения. Теперь рассмотрим вершину, которая имеет наименьшее количество достижимых городов. Поменяем направление движения на одной из дорог, выходящих из этой вершины. Это увеличит количество достижимых городов для этой вершины. Продолжим этот процесс до тех пор, пока не станет возможным добраться от любой вершины до любой другой.
Ответ:
Можно поменять направление движения на одной дороге так, чтобы от любого города можно было доехать до любого другого.