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

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

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

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

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

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

Нарисуем граф: вершины — имена, а ребро между вершинами означает, что в соответствующих именах есть одинаковая буква.

Тогда от Глеба отходит всего два ребра: к Андрею и Пете. Тогда Глеб точно сидит рядом с Андреем и Петей.

Аналогично от Даши отходи два ребра: к Андрею и Васе. Тогда Даша сидит именно рядом с Андреем и Васей. Уже получили рассадку пяти ребят:

Петя — Глеб — Андрей — Даша — Вася

От Тимура тоже отходит ровно два ребра: к Мите и Пете. Получаем цепочку:

Митя — Тимур — Петя — Глеб — Андрей — Даша — Вася

На оставшееся место посадим Соню, она как раз соединена с Митей и Васей.

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

2) Рассмотрим картинку как граф: вершины — точки пересечения отрезков, ребра — отрезки между точками (ближайшими на отрезке). И, следовательно, нам нужно найти эйлеров путь в таком графе, чтобы нарисовать картинку, не отрывая руки. Но в нашем графе ровно 4 вершины нечетной степени (а именно третьей), значит, в таком графе нет эйлерова пути (по нашей лемме).

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

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

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

Сначала попробуем нарисовать так две пересекающихся окружности. Сделать это несложно.

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

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

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

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

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

Если же мы попали в Б и еще остались какие-то ребра, то хотя бы одно оставшееся ребро связано с нашим пройденным путем (так как граф связный). Тогда у вершины, которая соединена этим ребром с вершиной из нашего пути (назовем вершину из пути С), степень нечетна (если вершина не А и не Б) или четна (если это вершина А или Б), то есть из нее можно выйти. Идем далее по этим ребрам из С (по новым каждый раз и не из пути), как и раньше делали с путем. Тогда мы всегда можем идти дальше, пока не вернемся обратно в С. Теперь просто вставим этот участок в наш путь.

Таким образом мы сформируем путь по всем ребрам (так как их конечное число).

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

Если четное, то у нас есть много (больше двух при ) вершин с нечетными степенями, следовательно, эйлерова пути точно нет.

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

Рассмотрим граф с вершинами в узлах сетки и ребрами — отрезочками между узлами. Заметим, что в графе есть 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 разобьются на пучки, что и требовалось.

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

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

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

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

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