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

задан 17 Ноя '14 0:27

перемечен 19 Ноя '14 23:20

EdwardTurJ's gravatar image


50179172

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

Отметим, что речь может идти только о незамкнутом пути (полугамильтоновом маршруте). Понятно, что если из одной вершины всё только выходит (или если все стрелки в какую-то вершину только входят), то замкнутого пути с нужным свойством уже не будет.

Здесь всё доказывается по индукции. Для двух вершин утверждение очевидно. Пусть $%n > 2$%. Берём маршрут $%v_1\to v_2\to\cdots\to v_{n-1}$% в подграфе. Если из $%v_n$% можно пройти в $%v_1$%, то всё ясно. Также всё ясно, если из $%v_{n-1}$% можно пройти в $%v_n$%. Поэтому предположим, что стрелка идёт из $%v_1$% в $%v_n$%, и из $%v_n$% в $%v_{n-1}$%. Назовём вершину $%v_i$% ($%1\le i < n$%) красной, если из неё идёт стрелка в $%v_n$%, и назовём её синей, если стрелка идёт в обратном направлении. У нас первая вершина красная, а последняя синяя. Значит, имеется хотя бы один момент смены цвета -- когда $%v_i$% красная, а $%v_{i+1}$% синяя. Тогда искомый маршрут получается вставкой $%v_n$% между $%v_i$% и $%v_{i+1}$%.

ссылка

отвечен 17 Ноя '14 1:01

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

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

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

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

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

отмечен:

×155

задан
17 Ноя '14 0:27

показан
565 раз

обновлен
19 Ноя '14 23:20

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

по почте:

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

по RSS:

Ответы

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

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