15.3 Приклади розв’язання типових завдань

1. Знайти ейлерів цикл у заданому графі (рис. 15.1).

Даний граф зв’язний. Знайдемо ступені вершин даного графа:

Ступені усіх його вершин парні, отже, цей граф містить ейлерів цикл.

Нехай – обрана нами довільна вершина. Присвоїмо ребру значення 1. Дотримуючись алгоритму Фльорі, пройдемо по графу, присвоюючи ребрам значення і звертаючи увагу на інструкції. В результаті обходу одержимо один з можливих циклів: (даний цикл виділено на рис. 15.2).

2. Знайти ейлерів ланцюг у графі (рис. 15.3).

Даний граф зв’язний. Знайдемо ступені вершин даного графа:

; ;

; ;

; .

;

Рисунок 15.1

Рисунок 15.2

Отже, маємо дві вершини з непарним ступенем і .

Звідси випливає, що даний граф має ейлерів ланцюг.

Нехай – обрана вершина з непарним ступенем. Присвоїмо ребру значення 1. Дотримуючись алгоритму, пройдемо по графу, присвоюючи ребрам значення. В результаті обходу одержимо один з можливих ланцюгів: (даний ланцюг відзначений на рис. 15.4).

Рисунок 15.3

Рисунок 15.4

3. Чи є графи, наведені на рис. 15.5, гамільтоновими?

Рисунок 15.5

Лівий граф на рис. 15.5 не є гамільтоновим тому, що він незв'язний. У ньому є дві компоненти зв'язності і . Правий граф на рис. 15.5 є гамільтоновим, оскільки він має гамільтонів цикл .

4. У заданому графі побудувати гамільтонів цикл, використовуючи метод перебору Робертса – Флореса (рис. 15.6).

Заповнюємо матрицю переходів згідно з алгоритмом:

Рисунок 15.6

За початкову вершину візьмемо вершину . Дотримуючись алгоритму, йдемо в першу можливу вершину – . Далі, дотримуючись умов алгоритму, виконуючи крок за кроком, знаходимо гамільтонів цикл: . Отже, знайдено один гамільтонів цикл. Аналогічно можна знайти всі гамільтонові цикли.

15.4 Контрольні запитання та завдання

1. Дайте визначення понять ланцюг і цикл. Який ланцюг називається ейлеровим?

2. Що відрізняється в умовах існування ейлерового ланцюга та ейлерового циклу?

3. Чи може граф містити декілька ейлерових ланцюгів (циклів)? Наведіть приклади.

4. Наведіть практичні приклади використання ейлерових ланцюгів і циклів.

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

а) парним ступенем;

б) непарним ступенем.

6. Які з графів правильних багатогранників мають гамільтонові ланцюги і цикли?

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

8. Які класичні задачі зводяться до побудови гамільтонових циклів? Наведіть їхню умову.

9. Назвіть необхідні і достатні умови існування гамільтонова циклу у графі.

10. Наведіть умову та формалізацію задачі комівояжера.