Тема 5. Ейлерів та гамільтонів графи

Ейлерів та гамільтонів графи

Розглянемо ейлерові графи.

Під час дослідження будь-яких графів можна ставити задачу щодо наявності в них ейлерових шляхів, ейлерових циклів, і доведення того, що граф є ейлеровим.

Ейлерів шлях у неорієнтованому графі - це шлях, що проходить кожне ребро рівно один раз. Ейлерів цикл у графі – це цикл, що містить всі ребра графа. Граф, що має ейлеровий цикл, називається ейлеревим графом.

У дитинстві часто розв'язують такі головоломки: як, не відриваючи олівця від аркуша паперу, намалювати гео­метричну фігуру (наприклад, фігури на малюнку 1). Виявляється, що для деяких фігур ця задача може бути розв'язана, а для деяких - ні. Це пов'яза­но з тим, чи є задана фігура ейлеровим графом, тільки у цьому разі фігуру можна намалювати.

Ейлером було доведено, що задача пошуку ейлерового шля­ху має зміст тільки тоді, коли в графі є лише дві вершини з непарним степенем (k = 2) або коли всі вершини мають парний степінь {тоді кількість вершин з непарнпм степенем k = 0). У першому випадку будь-яка з дох вершин є стартовою при обході, а друга - кінцевою. У другому випадку ейлерів шлях існує і є замкненим, тобто утворює цикл, а обхід у ньому можна починати з будь-якої вершини.

Тобто, якщо у графі лише дві вершини з непарними степенями, то це означатиме, що існуючий ейлерів шлях дає змогу пройти через усі ребра цього графа.| Якщо ж у графі є парна кількість вершин з непарним степенем, то це означає, що їх можна розбити на пари і кожна така пара дасть змогу побудувати свій ейлерів шлях у даному графі, які не охопить усі ребра, однак це зроблять усі пари разом.

На малюнку 1 зображено три різних графи, в яких присутні ейлерові шляхи та цикли. У першому і третьому графах усі вершини мають парні степені, тому існує ейлерів цикл, який можна почати у будь-якій з вершин цих графів, обійти всі їх ребра по одному разу і повернутися у стартову вершину. Другий граф має дві вершини зі степенем 3, тому у ньому існує не цикл, а шлях, який можна почати з будь-якої з цих двох вершин з непарним степенем, обійти всі ребра графа по одному разу і завершити обхід другій вершині, що має непарний степінь.

Надалі будемо розглядати питання пошуку ейлерових шляхів у графі, оскільки пошук ейлерового циклу є його окремим випадком. Зупинимося на умові, що за наявності непарних вершин у графі їх налічується у ньому лише дві.

Алгоритм пошуку ейлерового шляху на графі можна сфсрмулювати таким чином:

1.      Для  кожної  вершини  графа  обчислити  степінь, перевірити наявність у ньому ейлерового шляху.

2.      У разі існування ейлерового шляху в заданому графі запам'ятати стартову вершину. Вважати її поточною.

3.      Якщо існують вершини, «видимі» з поточної вершини, продовжити пошук (перейти на п. 4). У протилежному випадку перейти на п. 5.

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

5.      Якщо для поточної вершини відсутні «видимі» вершини і усі ребра для неї знищені у процесі проходу по них, потрібно запам'ятати цю вершину як складову ейлерового шляху і повернутися до попередньої розглянутої вершини у разі, коли  така існує, надавши їй статус поточної, і перейти до п. 3.

6.      Процес припиняється тоді, коли буде вичерпано усі вершини у п. 5, тобто всі ребра, якими проходили, будуть знищені. Послідовність вершин, яка була зафіксована у процесі знищення ребер заданого графа, і є ейлеровим шляхом, або циклом.

Даний алгоритм ґрунтується на двох основних моментах:

-    методом проходження по графу в глибину з поточної вершини визначається ребро, яким можна пройти далі в наступну вершину, у результаті чого це ребро знищується;

-    у разі, коли для поточної вершини відсутні ребра, якими можна пройти по графу далі, ця вершина запам'ятовується, робиться відступ на один крок назад у послідовності розглянутих вершин, застосовується пошук у глибину для нової поточної вершини.

Перший зазначений пункт дає змогу відсікти всі можливі ребра, якими можна пройти від поточної вершини, і не використовувати їх надалі в побудові наступних шляхів. Таким чином, проходячи по графу методом руху в глибину, ми фактично «спалюємо за собою всі мости», щоб більше не мати змоги ними проходити.

У другому пункті, зазначеному вище, ми передбачаємо всі вання інших ходів у графі, які дають змогу нам пройти тими ребрами, що залишилися. Це відбудеться, якщо виникне ситуація, коли в поточної вершини всі ребра «спалені», тобто ми вже пройшлися усіма ребрами, що проходять через цю вершину. Тобто, можна включити до ейлерового шляху і продовжити пошук. А для цього в нас лишається тільки один вихід: повернутися крок назад у попередню вершину, в якій побували перед цим знайти таку можливість, рухаючись графом з неї. Якщо і в цій вершини всі ребра «спалені», то робимо ще один крок назад і т.д. Якщо в графі ще залишилося хоча б одне «неспалене» ребро, то це означає, що ми обов'язково знайдемо вершину, з якої можемо цим ребром пройти, включивши його до нашого шляху.

Лише в разі відсутності ребер у заданому графі можна зробити висновок, що ми пройшли кожним ребром один раз і послідовність вершин, якою проходили, утворює ейлерів шлях.

Розглянемо конкретний приклад і виконаємо його покроково, використовуючи наведений алгоритм. Для прикладу візьмемо граф та відповідну йому таблицю суміжності (малюнок 2). Аналіз цього графа показує, що в ньому існує ейлерів шлях, оскільки дві вершини 1 і 2 мають непарні степені.

Почнемо виконання нашого алгоритму, наприклад, з вершини 1. Запишемо номер цієї вершини в першу послідовність, де ми будемо фіксувати проходження графом.

З таблиці суміжності бачимо, що першою вершиною, у яку можемо попасти з вершини 1, є вершина 2. «Спалимо» peбро (1,2), замінивши у таблиці суміжності відповідні значення елементів на 0 (а[1,2] = а[2,1] = 0), і запишемо номер цієї вершини в нашу поточну послідовність.

Ми маємо ще другу послідовність, у якій будемо формувати результат, а саме ейлерів шлях, тобто будемо записувати туди номери тих вершин, для яких на по­точний момент «спалені» вже всі ребра. Поки що такої ситу­ації в нас ще не виникало. Перейдемо до другої вершини і подивимось по другому рядку таблиці суміжності, у яку вершину можна перейти на наступному кроці. Такою є вершина 3. Виконаємо такі ж дії, як на попередньому кроці: а[2,3] = а[3,2] = 0. Вершину 3запишемо у першу послідовність.

З вершини 3 ми бачимо вершину 1. Перейдемо до неї, записавши її наступною в послідовність і «спаливши» ребро ( а[3,1] = а[1,3] = 0).

Поки що тупикових ситуацій немає. З вершини 1 ми можемо перейти до вершини 4, що слідує з першого рядка таблиці суміжності. «Спалюємо» ребро (1,4) і записуємо в першу послідовність номер вершини 4.

Розглянемо вершину 4, тобто четвертий рядок таблиці суміжності. Бачимо, що не всі ребра цієї вершини «спалені» і ми можемо перейти до вершини 2.

Виникає колізія: переходячи до другого ряді таблиці суміжності, ми не маємо можливості далі кудись рухатися, усі ребра «спалені»! Таким чином ми визначили першу вершину з номером 2, для якої існує ейлерів шлях у заданої графі, що починається з вершини 1, але він не містить усіх ребер графа. Це означає, що пошук можна продовжувати далі. Переносимо номер вершини 2 у другу послідовність, а в першій послідовності повертаємося до попередньої вершини 4. Але й у вершині 4 немає жодного не «спаленого» ребра. Тоді запишемо і цю вершину в другу послідовність і зробимо один крок назад у першій послідовності.

Вихід знайдено: вершина 1 має ще не «спалені» ребра і вершина, у яку ми можемо перебратися, - це вершина 5. Запишемо номер цієї вершини в нашу першу послідовність після вершини 1 і спалимо ребро (1,5).

Перейдемо до вершини 5. З таблиці суміжності видно, що наступним ребром, яким можна рухатись, є ребро (5,6). Перейдемо у вершину 6 ребром (5,6).

З малюнка 3 видно, що в нас залишилося тільки одне «не-спалене» ребро, яким ми зараз і пройдемося. Продовжуємо виконувати описаний алгоритм: якщо на по­точному кроці відсутні «неспалені» ребра, то необхідно номер поточної вершини запам'ятовувати як фрагмент ейилерового шляху і повертатися до попередньої переглянутої вершинри. У нашому випадку запам'ятовуємо вершину 1 і переходимо до вершини 6.

Наступні кроки виконання алгоритму очевидні: оскільки в таблиці суміжності не залишилося жодного елемента зі значен­ням 1, тобто в заданому графі всі ребра «спалені», то автома­тично всі елементи першої послідовності у зворотному порядку перенесуться до другої, де і буде визначено ейлерів шлях у за­даному графі (малюнок 4).

Розглянувши детально алгоритм визначення ейлерового шляху в заданому графі, спробуємо його реалізувати на мові Pascal.

Спочатку визначимо, які структури даних потрібно застосувати для реалізації алгоритму. По-перше, це двовимірний масив для фіксації наявності ребер між заданими вершинами графа, елементами якого є значення 0 та 1. По-друге, одновимірний масив, у якому обробляються елементи з найбільшим індексом. Протягом виконання алгоритму цей індекс буде і збільшуватися, і зменшуватися. Ми використаємо таку структуру даних, що реалізує роботу з одновимірним масивом таким чином, - це стек. І ще один одновимірний масив, у якому дописуватимуться елементи - номери вершин заданого графа,  що формують ейлерів шлях у ньому.

Отже, можна запропонувати такий варіант реалізації алгоритму пошуку ейлерового шляху в заданому графі:

top := 1; rez__top := 0;

while top <> 0 do

  begin

   While (a[i, j] <> 1) and (j <= n) do inc(j); {Пошук існуючого ребра вершини і}

   if (j <= n)

      then begin

                           inc(top);stack[top]:=j;

                  a[I,j] := 0; a[j, i] := 0;

              end

     else begin

                   inc(rez_top); rez[rez_top] := stack[top];

                   dec(top)

              end;

   i:=stack[top];j:=1;

end;

Для визначення існування ейлерового шляху в заданому графі можна провести підрахунок степенів вершин цього графа під час введення початкових даних:

Count:=0;

for і := 1 to n do

 begin

St := 0;                                                {Ініціалізація визначення степеня вершини.}

for j := 1 to n do

    begin

     read( a[i, j]);                                  {Введення елементів таблиці суміжності.}

     if а[i, j] = 1 then inc(st)                    {Підрахунок степеня поточної вершини.}

  end;

  if o dd(st) then             {Якщо степінь поточної вершини непарний, то враховуємо}

                    begin inc(count); b := і end;       {цю вершину і запам'ятовуємо її номер.}

  end;

if count = 0 then Stack[top] := 1;        {Якщо всі вершини графа парні, то почи­наємо пошук із 1-ї вершини.}

if count = 2 then stack[top] := b;        {Якщо існує 2 непарні вершини, то почи­наємо пошук з однієї з них.}

Аналіз степенів вершин заданого графа може бути використаний для визначення, чи існує у цьому графі ейлеровий шлях: якщо кількість непарних вершин не відповідає умовам існування ей­лерового шляху, то і виконувати алгоритм немає потреби.

У наведеному прикладі графа отриманий ейлерів шлях не є єдиним. Наприклад, шлях 123165142 також є ейлеровим. Але ми й не ставили задачу знайти всі ейлерові шляхи, а визначали: чи існує такий шлях. Цю задачу ми розв'язали.

Оцінимо ефективність роботи алгоритму побудови ейле­рового циклу або шляху в графі з п вершинами і т ребрами. Оскільки протягом виконання цього алгоритму по кожному ребру проходять лише один раз, а вершини фактично не роз­глядаються, то оцінка цього алгоритму логічно буде О(т).

Тепер перейдемо до визначення гамільтонових шляхів у за­даних графах.

Гамільтоновим називається та­кий шлях у графі, який проходить по кожній вершині лише один раз. На сьогодні не існує необхідних і достатніх умов існування гамільтонового шляху у графі. Це питання ви­вчається вже понад сто років, і відповідь досі не знайдена. Це означає, що не існує оптимальних методів по­шуку гамільтонового шляху у графі, однак метод повного пере­бору завжди дасть правильну відповідь.

Для визначення існування чи відсутності гамільтонового шляху в заданому графі необхідно переглянути всі варіанти перестановок вершин цього графа. Одночасно з отриманням чергової перестановки цих вершин необхідно перевірити на­явність ребер між сусідніми вершинами у ній. У разі розв'я­зання задачі про наявність хоча б одного з таких шляхів на цьому можна завершити виконання алгоритму. Якщо треба визначити всі гамільтонові шляхи, то необхідно виконувати алгоритм до кінця перегляду всіх можливих перестановок вершин графа.

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

Алгоритм пошуку гамільтонового шляху в заданому графі можна сформулювати так.

1.      Згенерувати поточну перестановку вершин заданого графа.

2.      Розглянути першу пару послідовних вершин у перестановці.

3.      Якщо ребро між поточною парою вершин перестановки відсутнє, то перейти до п. 6.

4.      Якщо існує наступна пара послідовних вершин у графі, то перейти до п. 3.

5.      Якщо для всіх пар послідовних вершин існують ребро у графі, то перейти до п. 7.

6.      Якщо існує наступна перестановка вершин заданого графа, то перейти до п. 1. У протилежному випадку перейти де ...

7.      Вивести вміст перестановки вершин заданого графа, для якого існують усі ребра.

8.    Завершити алгоритм.

Описаний алгоритм реалізуємо у вигляді фрагмента Pascal-прoгpaми:

flag := false;

i:=1;

repeat

  j := 1;

  while (d[a[j],a[j+1]]=1) and )j<n) do inc(j);

 if j=n then                                             

              begin

    for j := 1 to n do write(a[j],’ ‘);

                  writeln; flag := true;

end;

   inc(i);

   perestanovka;                     {Визначення наступної перестановки вершин графа}

until (i>= n) or flag;      {Завершення пошуку: коли відповідь знайдена або відсутня}

Зауважимо, що змінна n містить значення кількості можливих перестановок вершин графа, і саме за допомогою лічильника і, який змінюється у межах від 1 до n, ми можемо визначити, чи існує в ньому хоча б один гамільтонів шлях. Окрім цього, у наведеному фрагменті використано звернення до процедури генерування перестановок.

Виконавши описаний вище алгоритм для графа, зображено­го на малюнку 2, отримаємо результат: 324156

Якщо дещо модифікувати наведений фрагмент програми і визначити всі можливі гамільтонові шляхи у розглянутому прикладі графа, то отримаємо таку відповідь:

324156 324165 423156 423165 61324 561423 651324 651423

Отже, наведений приклад графа є не тільки ейлеровим, а ще й гамільтоновим.

Алгоритм побудови гамільтонового шляху або циклу має оцінку ефективності його роботи як О(п).

Для тестування наведених алгоритмів необхідно поряд із зв'язними графами розглянути і незв'язні. Це дасть змогу пе­ревірити коректність розроблених алгоритмів щодо аналізу визначення ейлерових та гамільтонових шляхів. Серед зв'яз­них графів необхідно розглянути як повні графи, так і неповні.

Завдання

1.   Розробити та реалізувати у вигляді програми алгоритм ви­значення заданого графа як ейлерового.

2.   Розробити та реалізувати у вигляді програми алгоритм ви­значення ейлерового циклу у графі.

3.   Виконати завдання 1—2 для графа з кількістю вершин N <= 10, в якому всі вершини мають парні степені.

4.   Виконати завдання 1-2 для графа з кількістю вершин N <= 10, в якому є дві вершини з непарними степенями.

5.   Виконати завдання 1-2 для графа з кількістю вершин N = 100, в якому всі вершини мають парні степені.

6.    Виконати завдання 1-2 для графа з кількістю вершин N = 100, в якому є дві вершини з непарними степенями.

7.    Розробити та реалізувати у вигляді програми алгоритм визначення гамільтонового циклу у графі.

8.    Виконати завдання 7 для графа з кількістю вершин N =5.

9.     Виконати завдання 7 для графа з кількістю вершин N > 5.