Обходи графів (реферат)

Реферат на тему:

Обходи графів

Початок теорії графів як розділу математики пов’язують із так званою задачею про кенігсберзькі мости. Сім мостів міста Кенігсберга були розташовані на річці Прегель так, як зображено на рис. 3.11,а.

а) б).

Рис. 3.11.

Задача полягає в тому, чи можна, починаючи з будь-якої точки (А, B, C або D), здійснити прогулянку (обхід) через усі мости так, щоб пройти кожен міст тільки один раз і повернутися у вихідну точку.

Оскільки суттєвими є тільки переходи через мости, то план міста можна зобразити у вигляді графа G (з так званими кратними ребрами), вершинами якого є береги і острови (точки А, В, С і D), а ребрами ости (див. рис. 3.11,б). Тоді задачу про кенігсберзькі мости можна мовою теорії графів сформулювати таким чином: чи існує в графі G цикл, який містить усі ребра цього графа? Інше відоме формулювання цієї проблеми виглядає так: чи можна намалювати фігуру, що зображає граф G, не відриваючи олівця від паперу і не повторюючи ліній двічі, почавши і закінчивши цю процедуру в одній з вершин фігури? Вперше відповідь на це питання дав Л. Ейлер у 1736 році. Робота Ейлера, яка містить цей розв’язок, вважається початком теорії графів.

Цикл, який містить усі ребра графа, називається ейлеровим циклом. Зв’язний граф, який має ейлерів цикл, називається ейлеровим графом.

Теорема 3.20 (теорема Ейлера). Зв’язний граф G є ейлеровим тоді і тільки тоді, коли степені всіх його вершин парні.

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

Достатність. Припустимо, що степені всіх вершин графа G =(V, E) парні. Візьмемо деяку вершину v1і розпочнемо з неї обхід графа, кожен раз обираючи ребро, яке раніше не використовувалось. Оскільки степінь кожної вершини парний і ненульовий, то цей шлях може закінчитися тільки у вершині v1, утворивши таким чином цикл Z1. Якщо в результаті описаного процесу використано всі ребра графа G, то шуканий ейлерів цикл побудовано. Якщо ж Z1 містить не всі ребра графа G, то вилучимо з G всі ребра, які входять у Z1. Одержимо граф G1 ідграф графа G, всі вершини якого також матимуть парні степені (це випливає з того, що і G, i Z1 мають вершини тільки парних степенів). Крім того, внаслідок зв’язності графа G Z1 i G1 мають принаймні одну спільну вершину v2. Відтак, починаючи з вершини v2, побудуємо цикл Z2 у графі G1. Позначимо через Z1астину циклу Z1 від v1 до v2, а через Z1 астину циклу Z1 від v2 до v1. Отримаємо новий цикл Z12, Z1, що веде з v1 у v1. Якщо цей цикл ейлерів роцес завершився. У противному разі продовжуємо аналогічні побудови ще раз і т.д. Цей процес завершиться побудовою шуканого ейлерового циклу.

Оскільки для графа G з рис. 3.11,б умови теореми Ейлера не виконуються, то в задачі про кенігсберзькі мости відповідь негативна.

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

Для знаходження деякого ейлерового циклу в ейлеровому графі G можна застосувати так званий алгоритм Фльорі. Фіксуємо довільну початкову вершину циклу. На кожному кроці процедури до шуканого циклу обираємо (доки це можливо) те ребро, після вилучення якого граф не розіб'ється на дві нетривіальні зв’язні компоненти. Кожне обране ребро вилучаємо з G. Процедура завершується, коли всі ребра буде вичерпано. Неважко обгрунтувати, що сформульований алгоритм будує ейлерів цикл графа G [2].

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

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

Зв’язок між ейлеровими і гамільтоновими циклами заданого графа G і відповідними циклами так званого реберного графа L (G) встановлюється за допомогою нижченаведених тверджень.

Множина V ершин графа L (G) рівнопотужна множині ребер E графа G, тобто існує бієкция E. Вершини v, w 'єднуються ребром у графі L (G), тоді й лише тоді, коли відповідні їм ребра) і) інцидентні одній і тій же вершині в графі G.

Теорема 3.21. Якщо граф G має ейлерів цикл, то граф L (G) має як ейлерів, так і гамільтонів цикли.

Теорема 3.22. Якщо граф G має гамільтонів цикл, то граф L (G) також має гамільтонів цикл.

Список літератури.

1. Харари Т. Теория графов.- М., 1973.

2. Лекции по теории графов / Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р.И.- М., 1990.

3. Зыков А. А. Основы теории графов.- М., 1987.

4. Оре О. Теория графов.- М., 1980.

5. Свами М., Тхуласираман К. Графы, сети, алгоритмы.- М., 1984.

6. Уилсон Р.

Введение

в теорию графов.- М., 1977.

7. Кристофидес Н. Теория графов. Алгоритмический подход.- М., 1978.

8. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы.-М., 1980.