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

Розрізняють ейлерові цикли і ейлерові графи. Ейлеровий цикл можна вважати слідом ручки, що викреслює цей цикл, не відриваючись від паперу.

Умови, при яких граф є ейлеровим. Кінцевий неорієнтований граф G ейлеровий тоді і тільки тоді, коли він зв'язаний і ступені всіх його вершин парні.

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

У кожну вершину може входити декілька дуг за умови, що виходять вони щораз по інших дугах. Таким чином, їх повинно бути парне число.

Ейлерові ланцюги. Так називається ланцюг, що включає всі ребра даного кінцевого неорієнтованого графа G, але має різні початок (U') і кінець (U").

Щоб у графі існував ейлеровий ланцюг, необхідна його зв'язність і парність ступенів усіх вершин, крім початкової і кінцевої. Останні дві вершини повинні мати непарні ступені: із U' ми зайвий раз виходимо, а в U" зайвий раз входимо. Ці умови достатні для існування ейлерового ланцюга.

Розглянемо випадок кінцевого орієнтованого графа.

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

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

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

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

а)

Рис. 2.10. Приклади графів б)

а - гамільтоновий цикл існує; б - гамільтоновий цикл не існує.

Незважаючи на зовнішню подібність, задачі розпізнавання ейлеровості і гамільтоновості графа принципово різноманітні. Правило визначення ейлеровості наведено вище. Що ж стосується гамільтоновості графа, то відповідь на це питання дає така теорема, що наводиться без доказу: граф із степеневою послідовністю d₁ £ d₂ £... £ d_n є гамільтоновим, якщо для всякого k, що задовольняє нерівностям 1 £ k < n/2, істинна імплікація (відповідність):

(d_k £ k) Þ (d_n-k ³ n - k).

Існують і інші, як більш сильні, так і більш слабкі теореми й умови визначення гамільтоновості графів.

Дата добавления: 2014-11-29