Индукция в графах и теорема Турана
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
В стране 
городов. Между каждыми двумя из них проложена либо автомобильная, либо железная дорога. Турист хочет объехать страну,
побывав в каждом городе ровно один раз, и вернуться в город, с которого он начинал путешествие. Докажите, что турист может
выбрать город, с которого он начнет путешествие, и маршрут так, что ему придётся поменять вид транспорта не более одного
раза.
Источники:
Подсказка 1
Переформулируем задачу на языке графов. Нам дан полный граф с вершинами, рёбра которого покрашены в два цвета. Требуется доказать, что мы можем выделить в этом графе цикл, проходящий через все вершины, состоящий не более чем из двух одноцветных частей.
Подсказка 2
Понятно, что делать переход нужно от n+1 до n. Как «внедрить» в путь новую вершину после её удаления?
Подсказка 3
Внедрить её в путь в случае одноцветного пути несложно. А что делать с участком пути другого цвета?
Переформулируем задачу на языке графов. Нам дан полный граф с 
вершинами, рёбра которого покрашены в два цвета. Требуется
доказать, что мы можем выделить в этом графе цикл, проходящий через все вершины, состоящий не более чем из двух одноцветных частей.
Доказательство проведём по индукции.
База. Для полного графа с тремя вершинами утверждение очевидно.
Шаг индукции. Рассмотрим полный граф с 
вершиной. Удалим из рассмотрения одну вершину 
с выходящими из неё ребрами.
Для оставшегося графа с 
вершинами по предположению индукции существует цикл, проходящий через все вершины, состоящий не более
чем из двух одноцветных частей. Возможны два случая.
Все рёбра цикла окрашены в один цвет. Занумеруем вершины цикла по порядку 
Тогда, удалив ребро
и соединив вершину 
с вершинами 
и 
мы получим цикл, состоящий не более чем из двух одноцветных
частей.
2) Не все рёбра цикла окрашены в один цвет. Пусть в цикле есть две одноцветные части: 
(красная) и 
(синяя). Посмотрим на цвет ребра 
Если это ребро красное, то цикл 
— искомый, если же оно синее, то
искомым будет цикл 
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
