Основи теорії графів. Властивості ойлерових та гамільтонових графів
Курсовой проект - Математика и статистика
Другие курсовые по предмету Математика и статистика
лі рівно один раз?
Це дало початок системному математичному підходу до побудови та вивчення властивості графів.
2.2 Основні поняття та означення ойлерових графів
Означення 2.1
Зв яний граф називається ойлеровим графом, якщо існує замкнений ланцюг, який проходить через кожне ребро.Такий ланцюг будемо називати ойлеровим ланцюгом, або ойлеровим циклом (див.рис.2.3)
Рис.2.3. Структура вершин та ребер в неорієнтованому ойлеровому графі (* - означено точку входу ойлерового ланцюга - циклу)
Означення 2.2
Граф називається напівойлеровим, якщо існує ланцюг , який проходить через кожне його ребро рівно один раз (див рис.2.4).
Рис.2.4. Структура вершин та ребер в неорієнтованому напівойлеровому графі (* - означено точку початку та кінця ойлерового ланцюгу)
Рис.2.5. Приклад неойлерового графу
Дослідивши структуру неойлерового графу, наведеного на рис.2.5, розг-лянемо необхідні і достатні умови для того, щоб граф був ойлеровим. Доведемо лему, яка далі буде грати істотну роль.
Лема 2.1
Якщо степінь кожної вершини графа не менше двох , то граф містить цикл.
Доведення. Якщо в графі є петлі або кратні дуги, то твердження леми оче-видне. Тому надалі будемо припускати , що є простим графом. Нехай довільна вершина графа . Побудуємо по індукції маршрут
обираючи вершину , суміжну з , а при обираючи вершину , суміж-ну з і відмінну від (існування такої вершини випливає з умови леми). Оскільки має скінченне число вершин, то врешті-решт ми прийдемо до вершини , з якої вийшли. Отримаємо цикл
Лема доведена.
Теорема 2.1 Для звязного графа наступні умови еквівалентні:
- ойлерів граф;
- кожна вершина
має парний степінь;
- множину ребер графа
можна розбити на прості цикли.
Доведення.
Нехай - ойлерів цикл графа . Будемо рухатись по циклу . Проходження кожної вершини збільшує степінь кожної вершини на 2, і оскільки кожне ребро входить в рівно раз , то будь-яка вершина має парний степінь .
Оскільки - звязний граф , степінь кожної вершини дорівнює принаймні 2; тому в силу леми 2.1 містить простий цикл . Виключимо ребра циклу , отримаємо остовний підграф , в якому кожна вершина має парний степінь. Якщо немає ребер , то (3) доведено. В протилеж-ному випадку застосуємо проведені вище міркування до , отримаємо граф , в якому степені всіх вершин є парними і так далі. Одночасно з порожнім графом , отримаємо розбиття множини ребер на циклів
Нехай множину ребер можна розбити на прості цикли. Нехай один з простих циклів. Якщо складається тільки з цього циклу , то -ойлерів граф. В протилежному випадку існує інший простий цикл, який має вершину , спільну з . Ланцюг, який розпочинається з і складається з циклу і наступного за ним циклу , є замкненим ланцюгом, який містить всі ребра графа , кожне один раз . Отже , - ойлерів граф.
З теореми 2.1 випливає наступна теорема.
Теорема 2.2. Звязний граф є ойлеровим тоді і тільки тоді, коли кожна його вершина має парний степінь.
.
Рис.2.6. Приклад ойлерового графу в теоремі 2.2
Доведення. Граф зображений на рисунку 2.6. є ойлеровим, оскільки
- Степінь вершин А, F, D, C, Q = 4(парні);
- Степінь вершин B, E = 2(парні);
- Множина ребер цього графа є об єднання двох простих циклів
і .
Теорема 2.3. Звязний граф є напівойлеровим тоді і тільки тоді , коли в ньому не більше двох вершин непарного степеня.
Рис. 2.7. Приклад напівойлерового графу до теореми 2.3
Доведення. Граф зображений на рисунку 2.7. є нпівойлеровим, оскільки
- Степінь вершин А, F, C = 4(парні);
- Степінь вершин B = 2(парна);
- Степінь вершин E,D = 3(непарна);
- Ось один з можливих варіантів обходу
. Початковою точкою маршрута є точка , а кінцевою є точка .
Якщо граф має дві вершини з непарними степенями (див.рис.2.7), то для будь-якого напіойлерового ланцюга одна з цих вершин буде початковою, а дру-га кінцевою. Для доведення досить сполучити відрізком вершини з непарними степенями.
Зауважимо , що згідно з лемою про рукостискання - число вершин непарного степеня є парним.
Спробуємо для довільного графа вказати найменше число ланцюгів та-ких, що жодні два не мають спільних ребер і всі вони повністю накривають ра-зом весь граф. Очевидно, якщо на графі є таке сімейство ланцюгів , то кожна вершина непарного степеня повинна бути або початковою, або кінцевою вер-шиною якогось ланцюга. Загальне число вершин з непарним степенем згідно з лемою про рукостискання є парним, скажімо рівним . Таким чином, кожне сімейство ланцюгів, які накривають граф , повинно містити принаймні лан-цюгів.
Доведемо, що існування вершин з непарним степенем є і достатньою умовою існування ланцюгів, які накривають граф.
Теорема 2.4. На будь-якому звязному графі з вершинами непарного степеня існує сімейство ланцюгів, які в сукупності містять всі ребра графа в точності один раз кожне.
Доведення. Позначимо вершини з непарними степенями
Якщо ми додамо до нашого графу ребра
то всі вершини отриманого графа будуть парними і на ньому знайдеться ойле-рів цикл . При відкиданні доданих ребер цикл розпадеться на окремих ланцюгів , які містять всі ребра графа.
Граф , зображений на рисунку 2.8 має чотири вершини з непарним степе-нем і накривається двома ланцюгами і
Рис.2.8. Граф з непарним степенем вершин до теореми 2.4
В розважальній математиці ось уже впро?/p>