Материал: 62_201

ному кроці. Такою є вершина 3. Виконаємо такі самі дії, що й на попередньому кроці: а[2,3] = а[3,2] = 0. Вершину 3 запише­ мо у першу послідовність (мал. 36, в).

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

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

Тепер наша увага переходить до вершини 4, тобто до четвер­ того рядка таблиці суміжності. Як бачимо, ще не всі ребра для цієї вершини «спалені» і ми можемо перейти до вершини 2. Зробимо це (мал. 36, є).

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

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

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

72

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

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

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

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

73

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

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

top := 1; rez_top := 0; while top <> Odo

begin

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

end;

І := Stack[top]; j := 1; {Продовжуємо пошук «неспалених» ребер із поточної вершини.} end;

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

74

c o u nt := 0; {Ініціалізація підрахунку кількості вершин графа непарного степеня.}

for і := 1 to n do begin

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

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

end;

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

Очевидно уважний читач помітив, що в наведеному прикладі графа отриманий ейлерів шлях не є єдиним. Наприклад, шлях 1 2 3 1 6 5 1 4 2 також є ейлеровим. Але ми й не ставили задачу знайти всі ейлерові шляхи, а визначалися зі стратегічним пи­ танням: чи існує такий шлях. І цю задачу ми розв'язали.

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

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

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

75

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

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

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

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

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

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

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

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

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

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

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

Описаний алгоритм досить очевидний, тому можна зразу пе­ рейти до його реалізації у вигляді фрагмента Pascal-програми:

until (І >= f) ОГ flag; {Завершення пошуку в разі, коли відповідь знайдена або відсутня.}

Зауважимо, що змінна / містить значення кількості всіх можливих перестановок вершин графа я!, і саме за допомогою

76