Материал: 62_201

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

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

3 2 4 1 5 6 Якщо дещо модифікувати наведений фрагмент програми і

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

3241 56

324165

423156

423165

561 324

561423

651324

651423

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

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

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

Завдання

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

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

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

вякому всі вершини мають парні степені. Результат вико­ нання програми вивести у файл.

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

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

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

вякому всі вершини мають парні степені. Результат вико­ нання програми вивести у файл.

77

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

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

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

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

УЗапитання для самоконтролю

1.Які питання вивчає теорія графів? Розділом якої науки вона є?

2.Чим відрізняються задачі, для розв'язання яких можна застосу­ вати оптимізаційні методи від задач, розв'язок яких - повний перебір усіх можливих варіантів?

3.Які задачі, що розглядалися нами раніше, можна віднести до теорії графів?

4.Що називається графом? З яких елементів він складається?

5.Поясніть такі поняття: інцидентність, суміжність, петля, нуль-граф.

6.Які графи називаються повними, плоскими, просторовими?

7.Як визначається степінь вершини?

8.Коли можна стверджувати, що існує шлях між двома заданими вершинами? Як визначається довжина шляху?

9.Які вершини називаються зв'язними? Який граф називається зв'язним?

10.Який шлях називається циклом? Який цикл називається прос­ тим? Наведіть приклади.

11.Який граф називається деревом, а який лісом?

12.Які графи називаються орієнтованими, зваженими? Наведіть приклади.

13.Які графи називаються ейлеровими, гамільтоновими? Наведіть приклади.

14.Які є способи представлення графів? Наведіть приклади різних графів та їх представлення. Порівняйте ці способи.

15.Який пошуковий метод називається пошуком у ширину в графі? По­ ясніть покроково роботу цього методу на конкретному прикладі.

16.Які структури даних необхідно використати під час реалізації у вигляді програми алгоритму пошуку в ширину?

17.Якими є ознаки визначення наявності і відсутності шляху між двома вершинами в заданому графі під час пошуку в ширину?

18.Яким чином можна визначити шлях від однієї вершини до іншої у заданому графі під час пошуку в ширину?

19.Опишіть алгоритм пошуку в ширину у словесній формі.

20.Запропонуйте варіант реалізації алгоритму пошуку в ширину у вигляді Pascal-програми.

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

22.Чим відрізняється стратегія організації пошуку в глибину від по­ шуку в ширину?

78

23.Прокоментуйте роботу алгоритму пошуку в глибину в покроковому режимі виконання на конкретному прикладі.

24.Якими є ознаки існування і відсутності шляху між двома верши­ нами заданого графа в алгоритмі пошуку в глибину?

25.Сформулюйте словесний алгоритм пошуку в глибину.

26.Запропонуйте свій варіант реалізації алгоритму пошуку в глиби­ ну у вигляді фрагмента Pascal-програми.

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

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

29.Які існують критерії наявності ейлерового шляху в заданому графі? Наведіть приклади ейлерових графів.

30.Сформулюйте алгоритм пошуку ейлерового шляху в заданому графі і обґрунтуйте його основні моменти.

31. Покроково виконайте алгоритм пошуку ейлерового шляху або циклу в графі на власному прикладі.

32.Які структури даних необхідно використати для реалізації алго­ ритму пошуку ейлерового шляху в заданому графі у вигляді Pascal-програми?

33.Запишіть фрагмент Pascal-програми, що реалізує алгоритм по­ шуку ейлерового шляху в заданому графі.

34.Як визначити наявність ейлерового шляху в заданому графі? За­ пишіть фрагмент Pascal-програми.

35.Яким є алгоритм пошуку гамільтонового шляху в заданому графі?

36.До якого класу задач можна віднести задачу пошуку гамільтоно­ вого шляху в заданому графі? Обґрунтуйте свою відповідь.

37.Запишіть реалізацію алгоритму пошуку гамільтонового шляху в заданому графі у вигляді фрагмента Pascal-програми.

Топологічне сортування

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

Під топологічним сортуванням будь-якого орієнтованого

графа розуміють таку послідовність його вершин fc,, t2,..., tn, у якій кожна вершина з номером t- є нащадком будь-якої верши­ ни з номером tt, де і < j. Або ще кажуть, що для послідовності вершин заданого графа, яка є результатом їхнього топологічно­ го сортування, існують лише ребра (tt, t), де і < j.

Наприклад, розглянемо граф, зображений на малюнку 39, а. У ньому вершини 1, 2 і 6 є нащадками вершини 3, а вершина 5, у свою чергу, є нащадком вершини 6. Тому в топологічній по­ слідовності вершин цього графа спочатку має йти вершина З, потім вершини 1, 2, 6, а за ними вершина 5. Чи можна вибуду­ вати таку послідовність для графа, зображеного на малюн­ ку 39, б? Мабуть, ні, оскільки, з одного боку, вершина 6 є на­ щадком вершини 3, а з іншого боку, вершина 3 є нащадком

79

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

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

У яких задачах необхідно використовувати топологічне сор­ тування? Можна навести такі приклади: виконання плану на­ вчального закладу вимагає певної послідовності у викладанні навчальних курсів; великі проекти часто розбивають на су­ купність менших задач, які виконуються у певному порядку, і тільки таким чином забезпечують повне виконання завершен­ ня всього проекту; збираючись уранці на заняття, необхідно враховувати послідовність одягання окремих елементів одягу.

На чому базується алгоритм топологічного сортування? Ви­ являється, що на алгоритмі пошуку в глибину. Нагадаємо його основні моменти, узагальнивши попередньо розглянутий варіант. Тобто не будемо шукати задану вершину, а поставимо за мету переглянути всі вершини графа. Використовуючи для цього стек, ми фактично врешті-решт повернемося в його поча­ ток. Протягом виконання алгоритму ми періодично будемо по­ трапляти в тупик: це означатиме, що з деякої вершини k нашого графа ми вже не можемо «побачити» нових вершин і записати їх у стек. Результатом розв'язання цієї проблеми є повернення

устеку на один крок назад, тобто до вершини, яка передує вер­ шині k. Фактично наявність тупика у вершині k говорить про те, що ми з неї вже побачили і відвідали всі вершини, які є її на­ щадками. Саме тому можна стверджувати, що вершина k може бути виведена на початок списку вершин, які слідували за нею

устеку, а також той факт, що між вершиною k та її вершинаминащадками існує топологічна відповідність.

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

80

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

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

Подібна ситуація може виникнути і під час перегляду вер­ шин орієнтованого графа, що не містить окремих підграфів. Наприклад, починаючи перегляд вершин з вершини 1 у графі, зображеному на малюнку 39, а, ми перейдемо до вершин 6 і 5. Оскільки нових вершин з них не видно, то ми врешті-решт по­ вернемося до стартової вершини 1, що знаходиться на початку стеку. Однак залишилися непереглянуті вершини 2,3,4. Якщо ми далі продовжимо з вершини 2, то, перейшовши у вершину 4, знову попадемо у тупик, і стек далі не буде заповнюватися. Завершимо перегляд вершин цього графа вершиною 3. Таким чином, протягом виконання такого обходу вершин орієнтова­ ного графа (мал. 39, а) тричі буде спорожнюватися стек.

Ми повністю готові до формулювання алгоритму топо­ логічного сортування орієнтованого графа.

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

2.Якщо послідовність вершин, що «переглянуті», не по­ рожня та існує ребро (і, j), де вершина/ ще не переглядалася, то перейти до неї, записавши її наступною в послідовність вер­ шин; перейти до п. 2.

3.Якщо не існує ребра (і, /), де вершина у ще не перегляда­ лася, визначити вершину і як наступну вершину в топологіч­ ній упорядкованій послідовності та перейти до попередньої вершини в послідовності вершин, що переглядаються.

4.Якщо послідовність вершин, що переглядаються, порож­ ня і не всі вершини заданого графа переглянуті, то перейти до п. 1.

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

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

Почнемо перегляд вершин графа з вершини номер 1 і запи­ шемо її в послідовність переглянутих вершин - перший рядок

81