БІЛОРУСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ ІНФОРМАТИКИ І РАДІОЕЛЕКТРОНІКИ
Кафедра інформатики
РЕФЕРАТ
на тему:
В«Побудова ейлерова циклу. Алгоритм форда і Уоршелла В»
МІНСЬК, 2008
1. Ейлерови ланцюга і цикли
Розглянута задача є однією з найстаріших в теорії графів. У місті Кенігсберзі (нині Калінінград) було сім мостів, що з'єднують два береги річки Преголя, і два основа на ній один з одним (рис. 1а). Вимагається, почавши подорож з однієї точки міста пройти по всіх мостах по одному разу і повернутися у вихідну точку.
а) б)
Рис. 1.
Якщо поставити у відповідність мостам ребра, а ділянкам суші - вершини, то вийде граф (точніше псевдограф), в якому треба знайти простий цикл, що проходить через всі ребра. У загальному вигляді ця задача була вирішена Ейлером в 1736
Визначення 1. ейлеровим ланцюгом в неорієнтованому графі G називається проста ланцюг, що містить всі ребра графа G . ейлеровим циклом називається замкнута Ейлерова ланцюг. Аналогічно, Ейлером шлях в Орграф G - це простий шлях, що містить всі дуги графа G . Ейлера контур в Орграф G - це замкнутий Ейлером шлях. Граф, у якому існує Ейлером цикл, називається ейлеровим .
Простий критерій існування ейлерова циклу в зв'язкового графі дається наступною теоремою.
Теорема 1. (Ейлер) Ейлером цикл в зв'язковому неорієнтованому графі G ( X , E ) існує тільки тоді, коли всі його вершини мають парну ступінь.
Доказ. Необхідність. Нехай m - Ейлером цикл в зв'язному графі G , x - довільна вершина цього графа. Через вершину x Ейлером цикл проходить деяка кількість k ( k Ві 1) раз, причому кожне проходження, очевидно, включає два ребра, і ступінь цієї вершини дорівнює 2 k , тобто парна, так як x обрана довільно, то всі вершини в графі G мають парну ступінь.
Достатність. Скористаємося індукцією по числу m ребер графа. Ейлерови цикли для звичайних (не псевдо) графів можна побудувати починаючи з m = 3.Легко перевірити, що єдиний граф з m = 3, має всі вершини з парними ступенями, є граф K 3 (рис. 2). Існування ейлерова циклу в ньому очевидно. Таким чином, для m = 3 достатність умов доводити теореми має місце. Нехай тепер граф G має m > 3 ребер, і нехай твердження справедливе для всіх зв'язкових графів, що мають менше, ніж m ребер. Зафіксуємо довільну вершину a графа G і будемо шукати простий цикл, що йде з a в a . Нехай m ( a , x ) - проста ланцюг, що йде з a в деяку вершину x . Якщо x В№ a , то ланцюг m можна продовжити з вершини x в деякому напрямку. Через деякий число таких продовжень ми прийдемо в вершину z ГЋ X , з якої не можна продовжити отриману просту ланцюг. Легко бачити, що z = a так як з усіх інших вершин ланцюг може вийти (парні ступеня!); a в a вона починалася. Таким чином, нами побудовано цикл m, що йде з a в a . Припустимо, що побудований простий цикл не містить всіх ребер графа G . Видалимо ребра, що входять до циклу m, з графа G і розглянемо отриманий граф. У графі всі вершини мають парні ступеня. Нехай - компо-нен-ти зв'язності графа, що містять хоча б по одному ребру. Згідно з припущенням індукції всі ці компоненти володіють ейлеровим циклами m 1 , m 1 , ..., m k відповідно. Так як граф G пов'язаний, то ланцюг m зустрічає кожну з компонент. Нехай перші зустрічі циклу m з ком-понентами відбуваються відповідно в вершинах x 1 , x 2 , ..., x k . Тоді про-зграя ланцюг
n ( a , a ) = m ( a , x 1 ) U m 1 ( x 1 , x 1 ) U m ( x 1 , x 2 ) U ... U m k ( x k , x k ) U m ( x k , a )
є ейлеровим циклом в графі G . Теорема доведена.
Зауваження. Очевидно, що наведене доказ буде вірно і для псевдографов, що містять петлі і кратні ребра (Див. рис. 1, а).
Таким чином, задача про Кенигсбергских мости не має рішення, оскільки відповідний граф (див. рис. 1, б) не має ейлерова циклу через непарності ступенів все вершин.
Відзначимо, що з існування ейлерова циклу в неорієнтованому графі G не слід зв'язність цього графа. Наприклад, неорієнтовані граф G на рис. 3 має ейлеровим циклом і разом з тим несвязен.
Абсолютно також, як теорема 1, можуть бути доведені наступні два твердження.
Теорема 2. Зв'язний неорієнтований граф G володіє ейлеровой ланцюгом тоді і тільки тоді, коли число вершин непарного ступеня в ньому дорівнює 0 або 2, причому якщо це число дорівнює нулю, то ейлерова ланцюг буде і циклом.
Теорема 3. Сильно зв'язний орграф G ( X , E ) володіє ейлеровим контуром тоді і тільки тоді, коли для будь-якої вершини x ГЋ X виконується
.
Можна також узагальнити завдання, яку вирішував Ейлер наступним чином. Будемо говорити що безліч не перетинаються по ребрах простих ланцюгів графа G покриває його, якщо всі ребра графа G включені в ланцюзі m i . Потрібно знайти найменшу кількість таких ланцюгів, якими можна покрити заданий граф G .
Якщо граф G - Ейлером, то очевидно, що це число дорівнює 1. Нехай тепер G не є ейлеровим графом. Позначимо через k число його вер-шин непарній ступеня. По теоремі ... k парно. Очевидно, що кожна вершина непарній ступеня повинна бути кінцем хоча б однієї з покриваючих G ланцюгів m i . Отже, таких ланцюгів буде не менш ніж k /2. З іншого сто-ку, таким кількістю ланцюгів граф G покрити можна. Щоб переконатися в цьому, розширимо G до нового графа, додавши k /2 ребер, з'єднують різні пари вершин непарній ступеня. Тоді виявляється ейлеровим графом і має Ейлером цикл. Після видалення з ребер граф розкладеться на k /2 ланцюгів, що покривають G . Таким чином, доведена.
Теорема 4. Нехай G - зв'язний граф з k > 0 вершинами непарного ступеня. Тоді мінімальне число непересічних по ребрах простих ланцюгів, що покривають G , одно k /2.
Алгоритм побудови ейлерова циклу
Для початку зазначимо, що теорема 1 також дає метод побудови ейлерова циклу. Тут ми розглянемо дещо інший алгоритм.
Нехай G ( X , E ) - зв'язний неорентірованний граф, не має вершин непарній ступеня. Назвемо мостом таке ребро, видалення якого з зв'язкового графа розбиває цей граф на дві компоненти зв'язності, що мають хоча б по одному ребру.
1 В°. Нехай a - Довільна вершина графа G . Візьмемо будь ребро e 1 = ( a , x 1 ), інцидентне вершині a, і покладемо m = { e 1 }.
2 В°. Розглянемо підграф G 1 ( X , E m 1 ). Візьмемо як e 2 ребро, інцидентне вершині x 1 і неінцідентное вершині a , яке також не є мостом у підграфі G 1 (якщо таке ребро e 2 існує!). Отрима...
