|
В стране конечное число городов. Они связаны дорогами с односторонним движением. Известно, что для любых двух городов от одного можно добраться до другого. Доказать, что найдется город, из которого можно добраться во все остальные. задан 14 Сен '18 9:27 
make78 |
|
Введём отношение ~ на множестве городов, полагая a ~ b, если можно добраться как из a в b, так и из b в a. Легко видеть, что это отношение эквивалентности. На множестве классов эквивалентности зададим отношение <=, полагая [x]<=[y], если из x можно добраться до y. Это отношение корректно, то есть не зависит от выбора представителя класса (если x заменить на x'~x, и y на y'~y, то из x' в y' также можно добраться). Отношение <= является (нестрогим) линейным порядком на множестве классов. Оно имеет наименьший элемент. Из любого города такого класса можно добраться до любого города страны. отвечен 14 Сен '18 9:37 
falcao @falcao а разве тут условие не говорит само за себя? "для любых двух городов от одного можно добраться до другого", зафискируем одну вершину графа, она состоит в отношении достижимости с остальными вершинами. Потому что из А1, по условию, можно приехать в А2, так же как и в А3, так же как и в любой другой Аi, где i>1. Тогда из этой вершины А1 можно добраться до остальных вершин.
(14 Сен '18 11:58)
pavel1076
А, заметил, что тут одностороннее движение. То есть если есть пара городов (Аy,Ax), то не факт, что из Ау можно добраться в Ах?
(14 Сен '18 12:00)
pavel1076
1
@falcao, верно ли такое рассуждение? Пусть в x1 можно добраться из х2, в х2 - из х3,... в х_(k-1) - из х_k (х1,..., х_k - все различные между собой города). Здесь х_k - город, в который нельзя добраться ни из одного нового города. Тогда из из х_k можно добраться во все остальные города, а также, очевидно, в х1,..., х_(k-1).
(14 Сен '18 14:04)
make78
1
@make78: я сначала не понял Вашего описания, но потом осознал, что Вы берёте "цепочку" x1<-x2<-...<-x_k справа налево, и тогда всё работает. Есть и другие варианты рассуждения. Известна теорема, что если имеется турнир (каждый сыграл с каждым, и в каждой паре кто-то выиграл), то участников можно перенумеровать так, что 1-й выиграл у 2-го, 2-й у 3-го, ... , (n-1)-й у n-го. Это доказывается по индукции. Тогда 1-й город -- искомый.
(14 Сен '18 17:25)
falcao
|