а) Дано: в государстве 101 город, каждый соединен с каждым дорогой с односторонним движением. В каждый город входит и из каждого выходит 50 дорог.
Найти: доказать, что из любого города можно доехать в любой другой, проехав не более чем по двум дорогам.
Решение:
Так как в каждый город входит и из каждого выходит 50 дорог, то из каждого города можно попасть в любой другой город на одной пересадке, то есть проехав не более чем по двум дорогам.
Ответ:
Из любого города можно доехать в любой другой, проехав не более чем по двум дорогам.
б) Дано: некоторые города соединены дорогами с односторонним движением. В каждый город входит и из каждого выходит 40 дорог.
Найти: доказать, что из любого города можно добраться до любого другого, проехав не более чем по трем дорогам.
Решение:
Предположим, что из какого-то города нельзя добраться до какого-то другого, проехав не более чем по трем дорогам. Это означало бы, что существует разделенная четвертая связная компонента, но так как всего 101 город, это противоречит условию задачи.
Ответ:
Из любого города можно добраться до любого другого, проехав не более чем по трем дорогам.