Лекция 19

ТЕМА: ЭЙЛЕРОВЫ И ГАМИЛЬТОНОВЫ ЦЕПИ И ЦИКЛЫ

ПЛАН:

1. Эйлеровы цепи и циклы

2. Гамильтоновы циклы и цепи

Главная

1. Эйлеровы цепи и циклы

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

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

Пусть G(V, X) – псевдограф. Цепь (цикл) в G(V, X) называется эйлеровой (эйлеровым), если она (он) проходит по одному разу через каждое ребро графа G(V, X).

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

V₁

V₂

V₃

V₄

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

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

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

Доказательство проведем по индукции.

Пусть G содержит только одно ребро, тогда это ребро – петля, т.к. нет висячих вершин, а петля – это простой цикл.

v

x

Пусть G содержит два ребра, тогда это кратные ребра. И, следовательно, простым циклом является v x₁ w x₂ v:

Пусть граф не содержит кратных ребер, т.е G – граф и v₁ , v₂ – произвольные смежные вершины графа. Рассмотрим последовательность v₁, v₂, v₃…вершин графа G такую, что для любого i  3 вершины v_i , v _i-1 смежны и v_i  v_i-2 :

v_i-2 v_i-1 v_i

Поскольку в графе нет висячих вершин, то такую последовательность можно продолжать неограниченно. Используя конечность множества вершин графа, получаем, что обязательно произойдет совпадение v_i = v_j , где 1 i < j – 2. Пусть это будет первое совпадение, т.е. совпадение с наименьшим номером j. Тогда последовательность v_i v _i+1 v _i+2…v_j – простой цикл в графе.

Введем обозначения: если ₁ и ₂ – циклы псевдографа G , имеющие хотя бы одну общую вершину и не имеющие общих ребер, то, очевидно, существует цикл, проходящий через все ребра , входящие в ₁ и ₂ . Обозначим ₁ + ₂ любой из таких циклов. Для любого цикла обозначим V() и X() соответственно множество вершин и множество ребер, входящих в .

Пусть  - цикл без петель. Тогда для v  V() количество ребер в Х(), инцидентных v , четно.

Поскольку в цикле  отсутствуют петли и все ребра попарно различны, то с каждым новым вхождением в  вершины v в этот цикл войдут также два новых инцидентных ей ребра, а следовательно, общее число ребер в Х() инцидентных v , четно.

Следствие. Если вершина входит в некоторый цикл. То она не может быть висячей.

Теперь сформулируем и докажем теорему о существовании в графе эйлерова цикла.

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

Необходимость. Пусть G обладает эйлеровым циклом.

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

Достаточность. Пусть m – количество ребер в G.

При m = 1 связный псевдорграф G с вершинами четной степени может выглядить только следующим образом: G(V, X), где V = {v}, X = {x = {v, v}}. Значит, G(V, X) – петля, а петля – это эйлеров цикл.

Предположим , что для некоторого целого m  2 достаточность доказана для всякого псевдографа с m -1 ребрами. Докажем справедливость для псевдографа с m ребрами.

Пусть в связном псевдографе G c m ребрами степени вершин четны. В силу утверждения 1 в G имеется простой цикл ₀ . Если ₀ содержит все ребра из G , то эйлеров цикл найден. В противном случае удаляем из G все ребра , содержащиеся в ₀. в результате получим псевдограф G' , каждая компонента связности которогоявляется либо изолированной вершиной, либо псевдографом, степень каждой вершины которого четна. Пусть G_i , где i = 1, 2, …р – компоненты связности графа G',отличные от изолированных вершин. По предположеню, для каждого псевдографа G_i можно построить эйлеров цикл _I . В силу связности G цикл ₀ имеет общие вершины с любым из циклов _i , где i = 1, 2, …р. Тогда искомым эйлеровым циклом в G является цикл :

 = (…((₀ + ₁ ) + ₂) + …+ _р).

Сформулируем и докажем теорему о существовании эйлеровой цепи в графе.

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

Необходимость. Пусть G имеет эйлерову цепь, соединяющую v и w. Добавим к G дополнительное ребро {v, w}. Получим псевдограф G', обладающий эйлеровым циклом, а следовательно, степени вершин графа G' четны. Но тогда четны и степени вершин псевдографа G, за исключением вершин v и w.

Достаточность. Пусть G имеет ровно две вершины v и w нечетной степени. Добавим к G новое ребро {v, w}. Получим связный псевдограф G' со всеми вершинами четной степени. Тогда в графе G' существует эйлеров цикл. Исключив из этого цикла ребро {v, w}, получим эйлерову цепь , соединяющуя вершины v и w.

Замечание. Эйлерова цепь соединяет вершины нечетной степени. Вернемся к задаче о Кенигсбергских мостах. Необходимое условие существования эйлерова цикла или эйлеровой цепи выполняется, т.к граф связный. Найдем степени вершин графа: (v₁) = (v₂) = (v₄) = 3, (v₃) =5. Значит, граф не обладает ни эйлеровым циклом , ни эйлеровой цепью.

Познакомимся с алгоритмами выделения эйлерова цикла и эйлеровой цепи.

Алгоритм 1 выделения эйлерова цикла в связном мультиграфе G(V,X), где Х  и степени вершин четны..

1. Выделить из G цикл ₁. Положить k = 1 (k - число циклов), G' = G.

2. Удалить из G' ребра, принадлежащие множеству Х(_k). Полученный псевдограф снова обозначить G'. Если в G' отсутствуют ребра, то переходим к шагу 4. В противном случае выделяем из G' цикл _k+1 и перейти к шагу 3.

3. Присвоить k: = k + 1 и перейти к шагу 2.

4. По построению ₁ , …, _k – циклы. Если k = 1, то ₁ – искомый эйлеров цикл, работа алгоритма заканчивается. В противном случае находим цикл _i такой, что V(_i)  V(₁) , где 2  i  k. Перейти к шагу 5.

5. Присвоить к: = i – 1, ₁ : ₁ + _i , _j : _j+1 , j = I, …, k. Перейти к шагу 4.

Применим этот алгоритм для выделения эйлерового цикла для псевдографа с четными степенями вершин..

Удалим из G петли. Получим связный мультиграф G’, степени которого четны. Пусть в G’ имеется хотя бы одно ребро. Тогда, применяя к G' приведенный алгоритм, найдем эйлеров цикл в графе G'. Добавляем в этот цикл удаленные петли, получим эйлеров цикл в G.

Рассмотрим теперь применения этого алгоритма для выделения эйлеровой цепи в связном псевдографе, имеящим ровно две вершины v, w нечетной степени., где Х . Добавляя к G ребро {v, w}, получим псевдограф G' с четными степенями вершин. Выделив в G' эйлеров цикл и удалив из него ребро {v, w} , получим эйлерову цепь.

Алгоритм 2 выделения эйлерова цикла в связном мультиграфе G(V,X), где Х  и степени вершин четны.

1. Выбрать произвольно некоторую вершину v.

2. Выбрать произвольно некоторое ребро х, инцидентное v , и присвоить ему номер 1.

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

4. Находясь в вершине v_i , не выбирать ребра, соединяющего v_i с v, если есть возможность другого выбора.

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

6. После того, как в графе будут занумерованы все ребра, цикл , образованный ребрами с номерами от 1 до n, где n – число ребер в графе, есть эйлеров цикл.

Для использования этого алгоритма для построения эйлеровой цепи первый пункт будет таким: выбрать вершину с нечетной степенью. Остальные шаги не изменятся.

Пример. Построить эйлеров цикл, используя оба алгоритма.

Применим первый алгоритм.

Данный псевдограф - связный. Найдем степени вершин: (v₁) = 4, (v₂) = 4, (v₃) = 6, (v₄) = 4, (v₅) = 4. Все степени вершин четные, следовательно, граф обладает эйлеровым циклом. Построим его.

Используем первый алгоритм.

Удалим петли х₁₀ и х₁₁. Получим мультиграф. Выделим цикл v₃x₄x₂x₅v₃ – обозначим ₁. Удалим ребра x_4, x_2, x₅ . Снова выделяем цикл v₃x₃x₁x₆v₃ - ₂ . V(₁)V(₂) = {v₁, v₂, v₃}. Удалим ребра. Выделяем цикл v₃x₇x₉x₈v₃ - ₃. V(₂)V(₃) = {v₃}. В мультиграфе построили эйлеров цикл _{1 +} ₂ + ₃ . Добавим удаленные петли и получим цикл в заданном графе: v₃x₄x₂x₅ x₃x₁x₆ x₇ x₁₀ x₉ x₁₁ x₈v₃.

Используем второй алгоритм.

Как и в первом алгоритме, удалим петли , получим мультиграф. Выберем любую вершину, например, v₃. Выберем инцидентное ей ребро, например, х₇ . Присвоим ему номер 1, т.е. х₇₁ и вычеркнем. Выбираем инцидентное ребро вершине v₄ – это ребро х₉, присвоим ему номер 2 – х₉₂ , вычеркнем. Выбираем инцидентное ребро вершине v₅ – это ребро х₈, присвоим ему номер 3 – х₈₃ , вычеркнем. Далее аналогичным образом выбираем ребра х₄, х₂, х₅ и х₃, х₁, х₆. В мультиграфе эйлеров цикл построен. Добавим в него удаленные петли. Окончательно получим эйлеров цикл в данном графе: v₃x₇x₁₀x₉ x₁₁x₈x₄ x₂ x₅ x₃ x₁ x₆v₃.