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

задан 14 Сен '18 9:27

10|600 символов нужно символов осталось
1

Введём отношение ~ на множестве городов, полагая a ~ b, если можно добраться как из a в b, так и из b в a. Легко видеть, что это отношение эквивалентности. На множестве классов эквивалентности зададим отношение <=, полагая [x]<=[y], если из x можно добраться до y. Это отношение корректно, то есть не зависит от выбора представителя класса (если x заменить на x'~x, и y на y'~y, то из x' в y' также можно добраться).

Отношение <= является (нестрогим) линейным порядком на множестве классов. Оно имеет наименьший элемент. Из любого города такого класса можно добраться до любого города страны.

ссылка

отвечен 14 Сен '18 9:37

@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

@falcao, благодарю за пояснения!

(15 Сен '18 9:56) make78
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×560

задан
14 Сен '18 9:27

показан
325 раз

обновлен
15 Сен '18 9:56

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru