На головну

Визначення гамільтонова шляху в графі

  1. I. 4. Які типи хвиль існують в природі, техніці? Які хвилі називаються пружними? Дайте визначення поздовжніх і поперечних пружних хвиль.
  2. I. Визначення рівнянь лінійної регресії
  3. I. ПОСТАНОВКА ПРОБЛЕМИ І ВИЗНАЧЕННЯ МОВНИХ ЖАНРІВ 1 сторінка
  4. I. ПОСТАНОВКА ПРОБЛЕМИ І ВИЗНАЧЕННЯ МОВНИХ ЖАНРІВ 2 сторінка
  5. I. ПОСТАНОВКА ПРОБЛЕМИ І ВИЗНАЧЕННЯ МОВНИХ ЖАНРІВ 3 сторінка
  6. I. ПОСТАНОВКА ПРОБЛЕМИ І ВИЗНАЧЕННЯ МОВНИХ ЖАНРІВ 4 сторінка
  7. II етап - Запит котирувань і визначення переможця

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

Як приклад розглянемо задачу визначення черговості рішення на ЕОМ обчислювальної програми (алгоритму) А, що складається з п підпрограм Ai ; i= 1,2, ...,n, причому на порядок виконання підпрограм накладаються обмеження у вигляді

Ai > Aj , (4.1)

т. е. виконання підпрограми Ai передує виконання підпрограми Aj , i, j I {1,2, ...,n} або

Ai Aj , (4.2)

т. е. порядок виконання програм Ai и Aj байдужий.

Цю задачу зручно геометрично відобразити у вигляді графа, де кожної i вершині відповідає Ai - Підпрограма, а зв'язки між підпрограмами відповідають дугам або ребрах. Причому дуга відповідає зв'язку Ai > Aj , А ребро - зв'язку Ai Aj .

Якщо передбачається, що програма A буде виконана, коли виконані всі підпрограми Ai , i= 1,2, ...,n (Без повторень), то визначення черговості виконання підпрограм Aiзводиться до визначення на графі гамільтонова шляху. Очевидно, що це завдання можна вирішити перебором всіх можливих варіантів (n! в насиченому графі) з одночасною перевіркою виконання всіх умов (4.1), (4.2). при n = 2 максимально можливо лише два варіанти, при n = 3 - шість, при n= 10 існує більше трьох з половиною мільйонів можливих варіантів, з яких треба вибрати допустимі, що задовольняють умовам (4.1), (4.2).

Рішення поставленого завдання може бути полегшено, якщо скористатися алгоритмом Фаулкса, що дозволяє в багатьох випадках значно зменшити кількість розглянутих можливих варіантів [1].

Алгоритм Фаулкса. розглядається n операцій (вершини графа) A1, A2, ..., An , Між якими існують співвідношення:

Ai > Aj , Ai > Aj , i, j I {1,2, ...,n} (4.3)

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

Ідея обчислень, які необхідно виконати при використанні алгоритму Фаулкса, полягає в знаходженні матриці RN шляхом последовательногобулевого множення  матриці R1 досяжності не більше ніж за один крок саму на себеN раз (матриця R1 може бути отримана з матриці суміжності R в результаті підстановки одиниць на головній діагоналі).

 
 

 
 

 елементи rNij матриціRN, визначаються як

Обчислення слід припинити, якщо RN = RN-1 .

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

Порядок вирішення завдання:

1. Задаємо номер циклу обчислень N =1.

2. Використовуючи співвідношення (4.3), складаємо граф, вершини якого є операції, а спрямовані дуги графа визначаються заданими співвідношеннями між операціями.

3. Складаємо матрицю R1 графа, елементи r1ij якої можуть набувати значень 0 або 1. Якщо r1ij = 1, то це вказує на те, що операція (вершина) Aj повинна слідувати за операцією (вершиною) Ai . Отримана таким чином матриця R1 є булевої матрицею (кожен елемент може приймати значення 0 або 1). Вона є вихідною для всіх подальших обчислень.

4. Використовуючи матрицю RN (На першому циклі обчислень RN = R1), Длякаждого вершини графа (операції) перевіряємо приналежність її кначальной або кінцевої вершині ДП за такими правилами.

Вершина (операція) є початкової вершиною ДП, якщо у всьому рядку матриці стоять одиниці, а в усьому стовпці (за винятком їх перетину) - нулі. Вершина (операція) є кінцевої вершиною ДП, то у всьому рядку матриці стоять нулі (за винятком їх перетину), а в усьому стовпці - одиниці.

5. Спрощуємо матрицю RN графа, викреслюючи з неї рядки і стовпці, що відповідають початковій або (і) кінцевої вершині ДП. Отримуємо матрицю (RN)'.

6. Збільшуємо на одиницю номер циклу, т. Е. N=N+1.

7. Знаходимо матрицю (RN)', виконавши Булевой множення матриці (RN-1)' на матрицю (R1)' , Яка виходить з вихідної матриці R1 викреслюванням з неї рядків і стовпців, відповідних початковим і кінцевим вершин ДП, знайденим у всіх попередніх циклах обчислень. Булевой перемноження матриць проводиться за звичайними правилами множення, тільки замість множення використовується кон'юнкція, а замість складання - диз'юнкція.

8. Перевіряємо умову виконання рівності матриць (RN)' і (RN-1)'.

Якщо ця умова виконується, то переходимо до п. 10, Інакше - до п. 9.

9. Перевіряємо умову рівності всіх елементів матриці RN одиниці. Якщо ця умова виконується, то немає необхідності в подальших обчисленнях матриці (RN)', Так як очевидно, що (RN+1)'= (RN)', Переходимо до п. 10. Якщо немає - до п. 4.

10. Складаємо матрицю Rb , повертаючи в матрицю (RN)' , рядки і стовпці, викреслені в п. 5 у всіх циклах обчислень.

11. Складаємо матрицю Rc , Перегруповуючи одночасно рядки і стовпці матриці Rb таким чином, щоб всі нулі були розташовані під головною діагоналлю, а одиниці - над нею.

Квадратні матриці, що складаються з одиниць, що спираються на головну діагональ, утворюють класи еквівалентності вершин (Сукупності вершин графа, еквівалентних з точки зору черговості їх присутності в гамільтонових шляху).

Якщо для даного графа ми отрималиm класів еквівалентності (m ? n), тобто B1, ..., Bm , І в кожен клас еквівалентності Bd , d = 1,2, ...,m входять Sd вершин графа, то можна сказати, що вершини, що входять в клас еквівалентності Bd, Розташовані вище і лівіше класу еквівалентності Bl в матриці Rc передуватимуть в гамільтонових шляху вершин з класу еквівалентності Bl .

Знаходження Гамільтонових шляхів в цьому випадку значно спрощується. У відповідно до класів еквівалентності ми отримали впорядковані групи вершин. В якості початкової вибирається вершина з першого класу еквівалентності. Якщо їх в ньому кілька, то наступна вибирається з цього ж класу і так до тих пір, поки не будуть вичерпані всі вершини цього класу. Потім переходимо до вершин наступного класу і т. Д. Поки не будуть використані всі вершини графа і побудований ДП. Слід зауважити, що при виборі чергової вершини необхідно обов'язково перевіряти виконання умов (4.3). Якщо умови не виконуються, черговість проходження вершин з одного класу еквівалентності змінюється. Максимальне число можливих варіантів скорочується до твору B1 ! • B2 ! •,...,Bm !

приклад. нехай програма A складається з 6 операцій (підпрограм) A1, A2, ..., A6 , Між якими існують такі співвідношення:

A1 > A2 , A2 > A3 , A3 > A4 , A5 > A2 , A6 > A2 ,

A1 > A4, A2 > A4, A5 > A4 , A6 > A4 ,

A1 > A6, A2 > A5 , A6 > A5

A2 > A6 . (4.4)

Мета завдання полягає в знаходженні шляху, що проходить тільки один раз через всі операції (вершини графа) і задовольняє написаним співвідношенням. Без врахування обмежень (4.4) всього можливо 6! = 720 варіантів проходження вершин.

Для вирішення завдання скористаємося наведеними алгоритмом.

1. Задамо номер циклу N = 1.

2. Складемо граф (рис. 4.1), що відповідає співвідношенням (4.4).
 
 

Мал. 4.1

3. Складемо матрицю R1 досяжності не більше ніж за один крок.

4. Перевіримо матрицю R1 на наявність початкової або кінцевої вершин в графі.

Очевидно, що A4 є кінцева вершина кожного гамільтонова шляху, оскільки ніяка дуга не має цю вершину своїм початком, тоді як дуга, яка виходить із будь-якої іншої вершини, досягає вершину A4. Це властивість виражається наявністю одиниць у всьому стовпці A4 і нулів у всьому рядку A4 (За винятком їх перетину).

5. Викреслюємо стовпець і рядок A4. Отримуємо матрицю (R1)' .

6. N= 1 + 1 = 2.

7. Зробимо Булевой множення матриць) (R1)' A (R1)' = (R2)'.

Наявність 1 в матриці означає існування між відповідними вершинами шляхів довжиною меншою або дорівнює двом, а 0 - їх відсутність.

8. Перевіряємо умову рівності (R2) ' і (R1)' . Так як вони не рівні, переходимо до п. 9.

9. Перевіряємо умову рівності всіх елементів матриці одиниці. Так як воно не виконується, то повертаємося до п.4.

4. Розглянемо матрицю (R2) ' .

вершина A3 , є кінцевою вершиною гамільтонова шляху на даному циклі обчислень.

5. Викреслюємо стовпець і рядок A3. Частина, що залишилася матриця має вигляд

(R2) ' = .

6. N= 2 + 1 = 3.

7. Виробляємо множення (R2 )'A (R ' ) = (R3 )'.

(R 3) ' = .

8. (R3) ' ? (R2 ) '

9. Всі елементи (RN) ', дорівнюють одиниці. Очевидно, що матриці (R4) ' , (R5) ' і т. д. також будуть рівні, т. к. будуть мати всі елементи, рівні одиниці.

Переходимо до п.10.

10. Матрицю R b отримуємо поверненням рядків і стовпців, викреслених в п. 5.

 
 

 11. Перегруппіруем рядки і стовпці матриці R bтак, щоб всі нулі були розташовані під головною діагоналлю, а одиниці - над нею: Отримуємо матрицю R c

Таким чином, отримали три класи еквівалентності :,

- В перший клас входять вершини A1, A2, A5, A6;

- В другій - вершина A3;

- В третій - вершина A4.

Т. е. В гамільтонових шляху вершини A1, A2, A5, A6 передують вершині A3 , Яка, в свою чергу, передує вершині A4 . Всього можливо 4! • 1! • 1! = 24 варіантів проходження вершин.

З урахуванням необхідності виконання умов (4.4) визначення гамільтонова шляху стає досить простою справою. В даному прикладі отримаємо єдиний ДП: A1,A6,A5,A2,A3,A4 .

Алгоритм Фаулкса в загальному випадку не вирішує однозначно завдання визначення Гамильтонова шляху, він тільки частково впорядковує безліч вершин, знижуючи тим самим розмірність розв'язуваної задачі. У разі, коли в кожен клас еквівалентності входить тільки одна вершина, алгоритм Фаулкса визначає гамильтонов шлях однозначно.



Методичні вказівки | Визначення зв'язності графа

Робота 1. ДОСЛІДЖЕННЯ І ОПИС КІНЦЕВОГО АВТОМАТА | Методичні вказівки | Методичні вказівки | Лабораторні роботи з курсу: ДМ | Загальні відомості | Методичні вказівки | Вихідні дані (завжди апріорна інформація). | завдання | Визначення ейлерового шляху в графі | Знаходження сильних компонент, базового і домінуючого множин |

© um.co.ua - учбові матеріали та реферати