Материал: Diskretnaya_matematika

3.9.1. Эйлеровы маршруты

Эти понятия возникли в статье Эйлера в 1735 г., в которой он решал задачу о Кенигсбергских мостах и впервые ввел понятие графа. На рис. 3.39, а приведен план расположения семи мостов в Кенигсберге (ныне Калининграде). Задачасостоит в том, чтобы пройти каждый мост по одному разу и вер­нуться в исходную точку С. Поскольку в конце обхода нужно вернуться в исходную часть города, и на каждом мосту нужно побывать по одному разу, этот маршрут является простым циклом, содержащим все ребра графа. В дальнейшем такие циклы стали называть эйлеровыми, а графы, имеющие эйлеров цикл – эйлеровыми графами.

а) б)

Рис. 3.39. Схема Кенигсбергских мостов и соответствующий граф

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

Обнаружив, что в данном графе не существует циклических обходов, проходящих по всем ребрам по одному разу, Эйлер обра­тился к общей задаче: при каких условиях в графе можно найти та­кой цикл? Ответ на этот вопрос дает следующая теорема.

Теорема 1 (Эйлера). Конечный связный неориен­тиро­ванный мультиграф является эйлеровым графом тогда и только тогда, когдав нем отсутствуют вершины нечетной степени.

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

Для доказательства достаточности предположим, что всевершины графа имеют четные степени. Начнем цепь Р в произволь­ной вершине х_iграфаG(рис. 3.40, а), и будем продолжать ее, на­сколько возможно, все время через новые ребра. Так как в каждой вершине число ребер четно, этот процесс может закончиться тольков x_i. Если цикл Р содержит не все ребра графа G, то удалим из G часть, соответствующую циклу Р. Графы Р и G имеют четные степени всех вершин. То же долж­но быть справедливо и для оставшегося графа Р.

а) б)

Рис. 3.40. Иллюстрация доказательства теоремы Эйлера (а) и пример построения эйлерова цикла (б)

Так как граф Gсвязен, в циклеPдолжна найтись вершинаx_j,инцидентная также ребрам Р. Из х_j можно построить новую цепь Р', содержащую только ребра изР. И снова такая цепь может за­кончиться только при возвращении в х_j .

Процесс построения эйлерова цикла иллюстрирует рис. 3.40, б. Объединяя, например, циклы (x₁, х₂, х₃, х₄, х₅, х₆,x₁) и (х₃, х₇, х₈,x₃,x₅, x₁ x₃), получим эйлеров цикл (x₁, x₂, x₃, x₇, x₈, х₃, х₅, х₁, х₃, х₄, х₅, х₆, x₁).

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

Эйлеровой цепью называется цепь, включающая все ребра данного конечного неориентированного графаG(X), но имеющаяразличные начало x_i и конец x_j. Чтобы в графе существовала эйлеро­ва цепь, он должен быть связным и все вершины в нем, кроме х_i и x_j, долж­ны иметь четные степени. Степени вершин х_i и x_j должны быть не­четными, что естественно, так как из x_i мы лишний раз выходим, а в x_j мы лишний раз входим. Эти условия являются достаточными для существования эйлеровой цепи.

Важен также следующий вопрос: каково наименьшее количе­ство не пересекающихся по ребрам цепей, покрывающих конеч­ный связный граф G(X) (покрыть – значит включить все ребра графа в цепь)? На этот вопрос отвечает теорема 2.

Теорема 2.В конечном связном неориентированном графеG(X) сkвершинами нечетной степени минимальное число непере­секающихся по ребрам цепей, покрывающих G(X) равно k/2.

Доказательство. Пусть G(X) не является эйлеро­вым графом и k– число его вершин нечетной степени. Ранее было доказано, чтоkчетно. Каждая вершина нечетной степени должна быть концом хотя бы одной из покрывающих граф цепей. Следовательно, число такихцепей не меньше, чем k/2. Но можно показать, что и не больше. Со­единим попарно вершины нечетной степени k/2 ребрами. Тогда сте­пень каждой вершины увеличится на единицу и станет четной. По­лучится эйлеров граф, в котором существует эйлеров цикл. Теперь будем постепенно выбрасывать присоединенные ребра. При выбра­сывании первого ребра эйлеров цикл превратится в эйлерову цепь, апри выбрасывании каждого последующего ребра одна из возникших к этому моменту цепей разобьется на две части. Таким образом, об­щее число этих цепей равно k/2.

Следствие. Из теоремы 2 следует, что ес­ли в связном неориентированном мультиграфе имеются две вершины нечетной степени x_i и x_j, то сущест­вует эйлерова цепь, начинающаяся в х_i, и кончающаяся в x_j.

Вкачестве примера рассмот­рим граф на рис. 3.41. В нем х₁, х₂, х₃, х₅ – вершины нечет­­ной степени. Добавим два ребра: (х₂, х₅), (х₁ х₃) (штриховые линии). Получим эй­леров граф с эйлеровым циклом (x₁, x₂, х₃, х₄, х₅, х₂, x₅, х₆, х₁, х₃, х₁). Убрав (х₃, х₁), по­лу­чим эйле­рову цепь. Убрав (х₂, х₅), получим 2 по­крыва­ющих цепи: (x₁, х₂, х₃, х₄, х₅, х₂) и (х₅, х₆, х₁, х₃).

Рассмотрим теперь случай конечного ориентиро­ван­ного гра­фа. Чтобы в конечном ориентированном графе существовал эйлеров цикл(контур), необходимо и достаточно, чтобы полустепени исхо­да и захода вершин этого графа по входящим и исходящим дугам были равны:

m'(x_i) = m"(х_i),  x_i  X.

Доказательство то же, что и для неориентированного графа.

3.9.2. Гамильтоновы маршруты

Гамильтоновой цепью в неориентированном графе называет­ся цепь, проходящая через каждую его вершину один и только одинраз.

Гамильтоновым циклом в неориентированном графе назы­вается цикл, проходящий через каждую вершину один и только один раз за исключением начальной вершины, которая совпадает сконечной.

Гамильтоновым путем в ориентированном графе называетсяпуть S = (х₁, ..., х_n), проходящий через все вершины графа, притом только по одному разу.

Гамильтоновым контуром называется контур М=(х₀, х₁, ..., х_n,х₀) в ориентированном графе G(X), если он прохо­дит через все вер­шины графа по одному разу.

Существует следующая распространенная интерпре­тация зада­чи о гамильтоновых циклах. Обед накрыт на круглом столе. Среди гостей некоторые являются друзьями. При каких условиях можно рассадить всех так, чтобы по обе стороны от каждого из присутст­вующих сидели его друзья?

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

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

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

Теорема Кёнига. В полном конечном графе всегда существу­ет гамильтонов путь.

Если в графе G(X) с n вершинами для любой пары вершин x_i и x_j справедливо неравенство

m(х_i) + m(x_j)  n - 1,

где m(х_i), m(x_j) – степени вершин х_i и x_j, то граф G(X) имеет гамильтонову цепь.

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

3.10. Контрольные вопросы и упражнения

1. Покажите, что два графа на рис. 3.42 изоморфны.

Рис. 3.42. Граф к задаче 1

2. «Три дома и три колодца». Три поссорившихся соседа имеют три общих колодца. Можно ли провести непересекающиеся дорожки от каждого дома к каждому колодцу?

3. Найдите число частичных графов конечного графа с m ребрами.

4. Каково число ребер в полном неориентированном графе с n вер­шинами?

5. Пусть U – множество положительных целых чисел, на котором задано отношение «а есть делитель b». Постройте граф этого от­ношения для множества целых чисел от 1 до 20.

Рис.3.43. Граф к задаче 6

6. Задан граф отношения «быть сестрой» (рис. 3.43) на множестве студентов-родственников нашего фа-культета. Постройте по рис. 3.43 граф отношения «быть братом».

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

8. Для графа, изображенного на рис. 3.44, найдите:

а) матрицу смежности (вершин);

б) матрицу инциденций;

в) наибольшее внутренне устойчивое множество;

г) наименьшее внешне устойчивое множество;

д) матрицу отклонений;

е) вектор отклоненностей;

ж) центр и радиус графа.

9. 

   Рис. 2.48 - К задаче 9

   

   Рис. 2.48 - К задаче 9

   

   

   Постройте графы, для которых радиус равен 2, 3, и такие графы, для которых диаметр равен 2, 3.

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

11. Какие из из графов правильных многогранников имеют гамильтоновы цепи и циклы.