Курсовая работа: Основи теорії графів. Властивості ойлерових та гамільтонових графів

Рис. 2.7. Приклад напівойлерового графу до теореми 2.3

Доведення. Граф зображений на рисунку 2.7. є нпівойлеровим, оскільки

1. Степінь вершин А, F, C= 4(парні);

2. Степінь вершин B = 2(парна);

3. Степінь вершин E,D = 3(непарна);

4. Ось один з можливих варіантів обходу . Початковою точкою маршрута є точка , а кінцевою є точка .

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

Зауважимо , що згідно з «лемою про рукостискання» - число вершин непарного степеня є парним.

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

Доведемо, що існування вершин з непарним степенем є і достатньою умовою існування ланцюгів, які накривають граф.

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

Доведення. Позначимо вершини з непарними степенями

Якщо ми додамо до нашого графу ребра

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

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

Рис.2.8. Граф з непарним степенем вершин до теореми 2.4

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

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

Рис. 2.9. Ойлерів цикл в графі – «Шабля Магомета»

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

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

Рис.2.10. Застосування апарату ойлерових циклів при розв’язанні задач “маршрут виставки» [3]

Припустимо, що експонати розташовані з обох сторін шляху, який про-ходить територією виставки. Виявляється, що тоді, яким би не був відповідний граф ( або лишень він був зв’язний), можна провести відвідувача так, щоб кож-ний шлях був пройдений двічі-по одному разу в кожному напрямі (див.рис.2.10).