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

задан 3 Ноя '14 20:26

изменен 3 Ноя '14 22:00

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

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

Будем рассуждать на языке графов. Имеется полный граф с $%n$% вершинами, на каждом из рёбер имеется стрелка. Требуется доказать, что существует город, из которого можно добраться до любого другого, проходя по одному или двум рёбрам в направлении стрелок. При $%n\le2$% это очевидно. Пусть $%n > 2$%. Рассуждая по индукции, считаем, что для $%n-1$% города утверждение доказано. Выберем город $%A$%, из которого исходит минимально возможное число стрелок. Удалим этот город вместе с рёбрами, для которых $%A$% служит вершиной. Тогда по предположению индукции в подграфе с $%n-1$% вершиной найдётся город $%B$%, для которого условие задачи выполнено. Если из $%B$% в $%A$% идёт стрелка, то всё доказано. Если нет, то из вершины $%B$% исходит равное число стрелок как во всём графе, так и в подграфе. Пусть оно равно $%k$%. Тогда из $%A$% выходит не более $%k$% стрелок, откуда следует, что из $%A$% не может выходить $%k+1$% стрелка в город $%B$%, а также во все города, в которые идёт стрелка из $%B$%. Значит, из одного такого города стрелка входит в $%A$%, то есть в него можно добраться из $%B$%, проходя одну или две стрелки.

ссылка

отвечен 3 Ноя '14 20:47

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×149

задан
3 Ноя '14 20:26

показан
1481 раз

обновлен
4 Ноя '14 11:01

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

по почте:

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

по RSS:

Ответы

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

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