Простой путь, Гамильтонов путь, Гамильтонов цикл

Лемма. В сильно связном турнире существует гамильтонов цикл.

Доказательство. В сильно связном турнире есть циклы. Рассмотрим в нашем турнире максимальный простой цикл Предположим, что в него вошли не все вершины графа, пусть вершина не вошла в этот цикл. Пусть не все стрелки между и циклом ориентированы одинаково. Тогда существуют последовательные вершины цикла и такие, что В этом случае несложно удлинить максимальный цикл вставив вершину между и противоречие.

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

Вернемся к доказательству основной задачи. По лемме в есть гамильтонов цикл . Нумерация вершин — циклическая, то есть Пусть длина диагонали цикла — это остаток от деления на числа

Если количество вершин в равно или то почти транзитивен.

Далее Рассмотрим два случая. Будем говорить, что если в ребро между и направлено к

1. Для каждого выполняется

Тогда пусть состоит из всех вершин с нечётными номерами, — из и всех вершин с чётными номерами. Нетрудно видеть, что а индуцированные турниры и — сильно связные.

2. Существует диагональ

Не умаляя общности будем считать, что Докажем, что при диагональ Пусть это не так, тогда выберем диагональ где и — максимально. Понятно, что выполняется хотя бы одно из условий и Пусть (второй случай аналогичен). Тогда следовательно, для множеств и индуцированные турниры и сильно связны, В этом случае утверждение доказано.

Итак, при и мы имеем Осталось разобраться, как направлены стрелки, инцидентные Если существует такое что то множества

таковы, что турниры и сильно связны и В этом случае утверждение доказано.

Остаётся случай, когда для некоторого в нашем графе стрелки ориентированы таким образом:

При турнир почти транзитивен (с порядком ). При турнир почти транзитивен (с порядком ). Если же то Следовательно, множества и таковы, что и сильно связны и

Рассмотрим ориентированный граф, соответствующий условию задачи. Рассмотрим среди всех ацикличных подграфов нашего графа тот, в котором наибольшее количество рёбер. Пусть ребро не вошло в выбранный подграф. Поскольку его нельзя добавить, то среди выбранных рёбер есть путь, идущий из в Хорошо известно, что в графе нет циклов тогда и только тогда, когда его вершины можно занумеровать числами от до количества вершин так, чтобы рёбра шли только из вершин с меньшими номерами в вершины с большими номерами. Давайте возьмём такую нумерацию нашего подграфа, а все рёбра, не вошедшие в подграф, обратим. Заметим, что в новом графе существует путь наибольшей длины, не проходящий по перевёрнутым рёбрам, ведь каждое из них можно заменить на путь по неперевёрнутым: при это получится простой путь, так как номера вершин в полученном пути возрастает. Кроме того, в нём нет циклов. Значит, полученное обращение подходит.

Введем обозначения. Пусть — наибольшее количество вершин во всех возможных подграфах таких, что никакие две вершины не соединены ребром, — наименьшее количество вершин графа удаление которых приводит к потери связности

Так, исходная задача может быть переформулировано в следующем виде:

Пусть — граф, такой, что и Тогда — гамильтонов.

Перейдем к доказательству. Положим Предположим сначала, что в нет циклов. Поскольку и граф связный, а, значит, — это дерево. Т.к. то в есть хотя бы две несвязные висячие вершины, а, значит,

откуда в есть хотя бы один цикл. Пусть — самый длинный простой цикл в причем Удалим из все вершины, лежащие в и обозначим за любую связную компоненту в оставшемся графе. Определим Сразу ясно, что (действительно, связность могла нарушиться только из-за удаления ребер в Более того, не содержит для любого из множества (положим иначе в есть цикл, длиннее Все вышесказанное означает, что и а, значит, поскольку при удалении множество уже образует отдельную компоненту связности.

Определим — соседи всех из например, против часовой стрелки. Из рисунка выше следует, что пусто Заметим теперь, что независимое множество, иначе в опять-таки, есть цикл длиннее а, значит, откуда

Рассмотрим произвольную вершину и множество Поскольку то — тоже независимое множество, а, значит, — противоречие.

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

Оценка. Докажем, что, если Вася задаст всего любых вопросов, он может не найти ни одной пары карточек с соседними числами. Предположим противное, что задав некоторые вопросов он смог точно указать на пару карточек с соседними числами. Переведём задачу на язык теории графов. Карточки будем считать вершинами графа а заданные Васей вопросы – рёбрами (синими рёбрами), соединяющими соответствующие пары карточек. К этим рёбрам нужно добавить ещё одно, соответствующее той паре карточек, на которых написана пара соседних, по версии Васи, чисел. Теперь нужно доказать, что вершины могут быть занумерованы в таком порядке, что ни одно ребро не соединяет две вершины с соседними номерами. То есть, нужно дорисовать в графе путь из рёбер, проходящий последовательно по всем вершинам, и не содержащих ни одного из «Васиного» синего ребра. Это будет означать, что Васина догадка не верна. Назовём такой путь красным и будем строить его методом математической индукции по числу вершин графа

Предположим, что в любом графе с числом вершин в котором проведено не больше синих рёбер, существует красный путь по всем вершинам, не содержащий синих рёбер. Построим красный путь в

1) Пусть в есть «крайняя» вершина из которой выходит ровно одно ребро В графе полученном из удалением вершины и ребра число вершин равно а рёбер – не больше выполнено предположение индукции, поэтому в можно построить красный путь длины с началом в вершине и концом в вершине Тогда ребро не соединяет вершину с одной из или проведя красное ребро из в эту вершину, получим красный путь длины в

2) Пусть в нет вершин, из которых выходит ровно одно ребро. В таком случае все синие рёбра инцидентны в сумме вершинам степени не меньше каждая, следовательно, среди них не больше различных. Следовательно, в не меньше двух вершин из которых не выходит ни одного синего ребра. Удалим из вершины и два ребра, выходящие из некоторой четвёртой вершины (но не саму вершину). Полученный граф снова удовлетворяет предположению индукции и в нём можно построить красный путь длины с началом в вершине и концом в вершине Если он не проходит через или проходит, но не проходит через удалённые рёбра, соединим с и с и получим красный путь в длины 99. В оставшихся случаях, обозначим за и вторые концы удалённых рёбер. Если красный путь в проходит через заменим этот фрагмент на Если он проходит только через одно удалённое ребро, скажем, через заменим его на В обоих случаях получится красный путь в

База индукции - случаи графов с 3 и 4 вершинами - очевидна.

(a) Начертим граф возможных соседей. Рассмотрим три пары вершин в четырехугольниках на графе (они отмечены жирными точками), а именно: (2, 10), (1, 9) и (3, 11) – это вершины с наименьшей степенью (количеством соседей), равной 2. Предположим, от противного, что есть простой путь на графе (т.е. без повторения вершин), проходящий через все вершины. Тогда найдется такая пара вершин среди трех указанных пар, что путь не начинается и не кончается в вершинах из этой пары (такая пара есть, т.к. концов у пути – два, а пар – три). Таким образом, обе вершины этой пары – “проходны”, но если впервые будет пройдена одна вершина из этой пары, то вторая вершина станет изолированной («отрезанной»: в неё нельзя будет попасть потом). Противоречие.

(b) Пример перестановки: 2, 5, 10, 7, 12, 9, 4, 1, 6, 3, 8, 11. Граф (см. рисунок) помогает построить подобный пример.

Рассмотрим наименьший простой нечётный цикл и множество остальных вершин Такой найдется, так как граф гамильтонов. Так как нет треугольников, то Внутри цикла рёбер нет, так как он наименьший.

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

Осталось посчитать рёбра. Тогда из в вершины цикла ведёт не более рёбер. Тогда найдется вершина цикла степени не более, чем Значит есть вершина степени что и требовалось.

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

Таким образом, мы получили три простых цикла: Их длины равны и (не умаляя общности пусть ). Но если эти числа делятся на то также делится на которое по условию больше Пришли к противоречию.

Построим граф, вершины которого соответствуют городам, а ребра — дорогам. Выберем в этом графе самый длинный путь пусть вершины и — концы этого пути. Из условия задачи следует, что в пути не более вершин. Отметим, что концы пути — вершины и не могут быть смежны с вершинами не из (иначе путь можно удлинить). А в случае, когда вершины и смежны и наш путь замыкается в цикл, никакая вершина пути по аналогичным причинам не может быть смежна с вершиной не из

1) Рассмотрим случай, когда в не более вершин. В этом случае рассмотрим любые две вершины и не входящие в путь и концы пути и Среди этих четырех вершин должны быть проведены хотя бы два ребра. Так как ни ни не могут быть смежны с вершинами не из то концы пути и соединены ребром.

Таким образом, путь замыкается в цикл, и тогда ни одна из вершин пути не смежна с вершиной не из Рассмотрим четверку из любых двух вершин и пути и любых двух вершин и не входящих в Так как между этими четырьмя вершинами проведено хотя бы два ребра, то одно из них соединяет и а другое — и Таким образом, в рассматриваемом случае все вершины пути попарно смежны и все вершины не из также попарно смежны. Отсюда очевидно следует утверждение задачи. 2) Рассмотрим случай, когда вне пути лежит ровно одна вершина. Пусть это вершина Если не смежна ни с одной из вершин пути то рассмотрим и любые три вершины пути Поскольку среди этих четырех вершин проведено хотя бы два ребра, то среди любых трех вершин пути проведено хотя бы два ребра. Следовательно, для любой вершины из есть не более одной не смежной с ней вершины пути Поскольку вершин пути нельзя разбить на пары не соединенных ребром, то в должна быть вершина, смежная со всеми остальными вершинами Эта вершина в паре с удовлетворяет утверждению задачи.

Если концы максимального пути и смежны, то, как мы доказали, вершина не смежна ни с одной из вершин пути а этот случай уже разобран.

Остается рассмотреть последний случай, когда концы пути не смежны и вершина смежна хотя бы с одной из вершин пути Рассмотрим вершины и произвольную четвертую вершину (естественно, лежащую на пути ). Так как и попарно не смежны, то смежна хотя бы с двумя вершинами из и Пусть смежна с вершиной пути Одна из соседних с вершин пути не является концом пути. Можно считать, что это первая вершина лежащая на пути из в по ребрам Если смежна с то, пройдя от к по пути далее по ребрам и и затем по пути от к мы обойдем все вершины нашего графа ровно по одному разу, что невозможно по условию. Если же не смежна с то, как мы доказали, эта вершина смежна и с и с Тогда пройдем по ребру далее по пути от к по ребрам и и затем по пути от его конца до вершины, соседней с на пути — получился путь, проходящей по каждой вершине нашего графа ровно один раз, которого по условию не существует. Следовательно, и этот случай не возможен.

Таким образом, мы рассмотрели все случаи и в тех из них, которые возможны, убедились в справедливости утверждения задачи.

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

Предположим, что область содержит не все города. Тогда найдётся дорога, ведущая из города области (обозначим его через в город, ещё не принадлежащий автономной области (назовём его Рассмотрим несамопересекающийся путь (последовательность дорог), ведущий из в

Предположим, что на этом пути есть город лежащий в автономной области. Тогда из можно добраться до двумя несамопересекающимися путями: один путь идёт через а второй идёт только по городам области (такой путь существует, потому что для области выполнено условие задачи, как и для всей страны). Но это противоречит условию. Следовательно, путь из в не содержит других городов из области, кроме

Теперь присоединим все города на этом пути (включая к автономной области и отнесём их поочерёдно в те две губернии, в которые не входит. Все дороги, соединяющие два присоединённых города, — это дороги на пути из в иначе между ними было бы два пути. Аналогично все дороги, соединяющие присоединённый город с городом, уже имевшимся в области — это дорога из в и последняя дорога на пути из в Следовательно, область будет правильно разделена на губернии.

Два несамопересекающихся пути от одного города к другому по области невозможны, иначе бы вся страна не удовлетворяла условию. От каждого города области можно доехать (по области) до а от — до всех остальных, поэтому по крайней мере один путь от одного города области до другого всегда существует. Значит, новая область тоже удовлетворяет условию.

На каждом описанном шаге область увеличивается хотя бы на один город Следовательно, рано или поздно все города будут присоединены. В этот момент область совпадёт со всей страной и при этом будет разделена на губернии.