Гуляем по графу

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

Допустим теперь, что и находятся на разных дугах. В этом случае наш цикл распадается на два:

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

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

Ориентированный граф ациклический, а значит, мы можем расположить вершины в таком порядке, чтобы ребро шло из вершины с меньшим номером в вершину с большим номером. Запустим процесс. Будем идти по вершинам, начиная с первой, и закидывать их в группу с минимальным номером, чтобы требуемые условия выполнялись. Пусть мы дошли до -й вершины и не смогли её добавить ни в одну из групп. Это значит, что в -й группе есть вершина с некоторым номером из которой идёт ребро в А почему не получилось поместить вершину в группу? Потому что в ней есть некоторая вершина из которой идёт ребро в Продолжая такие рассуждения для всех групп, получим путь длины которого по условию быть не должно, пришли к противоречию.

Занумеруем города числами 0, 1, 2, …, 29 так, чтобы изначально у нас был цикл Добавим 9 авиалиний …, (а 10-ю авиалинию добавим какую угодно).

Покажем, что условие выполняется. Возьмем любые два города и От можно не более чем за 1 перелёт добраться до города с номером, кратным 3. Аналогично, от можно не более чем за 1 перелёт добраться до города с номером, кратным 3. А между городами и либо есть путь не более, чем из двух перелётов, так как все города с номерами, кратными 3, соединены с городом номер 0.

(a) Покажем, что каждая компонента связности графа является простым циклом. Тогда разбиение на компоненты связности будет искомым.

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

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

(b) Аналогично пункту (a) будем считать граф связным и запустим покраску. Если есть вершина степени 0, то весь граф состоит только из неё. сама по себе образует цепочку. Если в графе нет вершин степени 1, то по пункту (a) мы найдём простой цикл. Если же есть вершина степени 1, то начнём покраску из неё. Граф конечен, поэтому процесс остановится, причём вернуться в уже посещенную вершину нельзя. Значит, мы закончим в другой вершине степени 1. Тогда получилась цепочка. Аналогично циклу, мы обошли весь граф.

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

Возможны всего три случая: закрыли прямую дорогу на пути закрыли дорогу на пути закрыли дорогу

Разберём первый случай: закрыли прямую дорогу В графе после удаления ребра найдется путь между и пусть это дорога

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

Разберёмся со вторым случаем: на закрыли дорогу В графе после удаления ребра есть какая-то дорога от до пусть это дорога

В исходном графе был путь из в Заметим, что этот путь не мог проходить через удаленное ребро, ведь это ребро не может быть ни первым в пути, ни последним, а ребер всего два. Тогда можно пройти из в а потом по этому пути.

Третий случай: на закрыли дорогу В графе после удаления ребра есть какая-то дорога от до пусть это дорога

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

Начнём из произвольной точки двигаться по рёбрам, не посещая точки, в которых мы уже были. Пусть мы прошли вершин и дальше не можем продолжить движение. Это значит, что все рёбра идут в вершины Этих рёбер хотя бы значит и есть вершина с индексом не большим которая соединена с Заметим, что цикл подходит.

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

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

Покажем, что не является максимальным по включению.

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

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

Пусть — число всех ребер в путях из на шаге данного алгоритма, — число общих ребер в путях из и на шаге данного алгоритма. Рассмотрим величину

на шаге данного алгоритма. Поскольку количество общих ребер увеличивается на число большее, чем количество ребер в перестраиваемом пути

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

1.

имеют общий конец с каким-то путем из

2.

не имеют общих вершин с любым путем из

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

Давайте начнем “гулять” по графу, пока можем попадать в новую вершину. В силу конечного количества вершин в какой-то момент мы остановимся. Пусть мы остановились в вершине Тогда все ребра из точно ведут в этот путь. Этих ребер хотя бы два. Пусть эти ребра ведут в вершины и Заметим, что образовалось хотя бы три цикла. Путь из в и ребро путь из в и ребро путь из в и ребра и Тогда путь из в и путь из в имеют четную длину, но тогда путь из в тоже четной длины. Следовательно, цикл содержащий ребра и путь из в — четный.

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

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

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

1.

Между любыми двумя вершинами нет ребра при Если это не так, то мы сможем выбрать цикл меньшей длины на ребрах в котором участвует ребро

2.

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

Удалим из все вершины, которые лежат в и все ребра, которые им инцидентны. Тем самым мы удалили ребро цикла, 0 ребер внутри цикла и не более ребер между вершинами и то есть суммарно не более ребер. Тем самым, в графе осталось не более вершин (потому что в цикле по условию хотя бы вершин) и хотя бы рёбер.

Повторим наш алогритм еще раза. После применения c номером мы имеем граф, в котором не более вершин и хотя бы ребер.

Наконец, перед последней итерацией, мы получим граф, в котором не более вершин и хотя бы ребер, в котором найдем последний цикл.

Пусть на ремонт закрыли дорогу из города в город .

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

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

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

В итоге путь имеет длину не больше трёх.

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

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

Пусть вершины “туда” шли в порядке Если в минимальном маршруте ровно стрелок, то в маршруте “обратно” снова есть вершина Выехав из к администрации, мы не можем попасть в вершины – так как должен быть путь в по двум стрелкам, что противоречит минимальности маршрута “туда”. Следовательно, администрация находится на стрелке При этом не может альтернативного пути из двух стрелок кроме т.к. “туда” опять будет не минимальным. Таким образом, маршрут имеет вид где — какая-то вершина среди первых семи. Но из неё можно попасть в по двум стрелкам — снова противоречие.

Итак, мы доказали, что в кратчайшем маршруте “обратно” нет вершины Следовательно, весь маршрут содержит менее вершин и менее стрелок.

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

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

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

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

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

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

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

Итак, не умаляя общности будем считать, что все вершины различны, причем и Рассмотрим три случая.

(а) Тогда проведем перестройку в графе (это возможно, так как ) и получим граф с По предположению, можно получить из перестройками, значит, можно получить и

(b) . Тогда — чередующийся цикл, меньший чем противоречие.

(c) Тогда проведем перестройку в графе (это возможно, так как и получим граф с По предположению, можно получить из перестройками, значит, можно получить и

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

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

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