Эйлеровы графы

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

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

Нарисуем граф ходов коня, получится, что кони стоят по циклу и не могут друг “сквозь” друга пройти, следовательно, свой порядок они не изменят.

С пунктом 1) все просто: это легко сделать, если начать из нижней вершины. А вот в пункте 2) ничего не получается. Действительно ли это невозможно, или мы просто плохо стараемся? Оказывается, невозможно, и доказать это можно так.

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

Рассмотрим граф с вершинами в узлах сетки и ребрами — отрезочками между узлами. Заметим, что в графе есть 8 вершин нечетной степени (по 2 на каждой стороне). Заметим, что как минимум в 6 из них наш маршрут не начинается и не заканчивается. А значит, мы входили в эти вершины столько же раз, сколько и выходили из них. То есть для каждой такой вершины одно из ее ребер было пройдено дважды. Отметим для каждой из наших вершин такое ребро. Заметим, что одно и то же ребро может быть отмечено не более 2 раз (по одному раз для каждого конца). Поэтому мы прошли дважды хотя бы по 3 ребрам. Поэтому длина нашего пути не меньше, чем метров.

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

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

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

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

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

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

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

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

Рассмотрим граф, вершинами которого являются пары цифр (упорядоченные). Количество таких пар (каждое из 2 чисел можно выбрать 10 способами). Будем проводить стрелочку из вершины в вершину , если второе число равно первому числу . Заметим, что из каждой вершины выходит 10 ребер и входит 10 ребер. Если мы сотрем ориентацию на ребрах, то легко видеть, что полученный граф будет связным. Тогда также как и во второй задаче найдем ориентированный цикл, содержащий все ребра. Заметим, что каждой последовательности из 3 чисел соответствует ровно 1 ребро (между первыми двумя числами и последними двумя числами). Выпишем сначала произвольную пару чисел, а затем будем дописывать следующую согласно нашему циклу (то есть, если мы выписали числа из вершины , а следующей в нашем цикле является вершина , то допишем на доску последнюю цифру и так далее). Поскольку мы прошли по всем ребрам ровно 1 раз, у нас встретятся все комбинации из 3 чисел, причем ровно по 1 разу, что и требовалось.

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

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

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

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

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

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

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

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

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

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

Связный граф эйлеров, если в нём 0 или 2 вершины нечетной степени. В противном случае, граф будет неэйлеровым.

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

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

А если и, наоборот, - нечётно, то - чётно, и поэтому у нас все вершины чётной степени, значит, такой граф эйлеров (очевидно, он связен).