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

КУРСОВА РОБОТА

з дисципліни

„Алгебра та теорія чисел”

за темою

„Основи теорії графів.

Властивості ойлерових та гамільтонових графів”

ЗМІСТ

ВСТУП

РОЗДІЛ І ВВЕДЕННЯ В ТЕОРІЮ ГРАФІВ

1.1 Основні поняття та означення

1.2 Лема про рукостискання

1.3 Оцінки для числа ребер з компонентами зв `язності

1.4 Орієнтовані графи, графи з петлями, графи з паралельними дугами

РОЗДІЛ ІІ ОЙЛЕРОВІ ГРАФИ

2.1 Ойлерова ломиголовка «Кенігзберзьких мостів»

2.2 Основні поняття та означення ойлерових графів

2.3 Приклади ойлерових графів

РОЗДІЛ ІІІ ГАМІЛЬТОНОВІ ГРАФИ

3.1 Сутність гамільтонових графів

3.2 Основні поняття та означення

3.3 Приклади гамільтонових графів

ВИСНОВКИ

СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ

ВСТУП

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

Отримання дальших суттєвих результатів у цій галузі датують серединою ХIХ століття. Однак початок проведення активних систематичних досліджень та становлення теорії графів як окремішного авторитетного розділу сучасної математики відбулося ще майже 100 років по тому, тобто в середині ХХ століття. Саме з цього часу граф стає однією з найпоширеніших і найпопулярніших математичних моделей у багатьох сферах науки і техніки. Картинка у вигляді набору точок на площині та ліній, проведених між деякими з них, стала зручною і наочною формою зображення найрізноманітніших об'єктів, процесів та явищ.

Великою мірою це пов'язано з виникненням, бурхливим розвитком та поширенням електронних обчислювальних машин і, як наслідок, значним зростанням ролі задач дискретного характеру. Математика від "обслуговування" переважно фізики переходить до проникнення своїх методів у інші сфери людської діяльності. Одним з потужних інструментів такого проникнення є граф.

Із суто формальної точки зору граф можна розглядати як один з різновидів алгебраїчної системи (а саме, як модель), а отже, і всю теорію графів як розділ сучасної алгебри. Справді, результати та методи алгебри широко використовуються в теорії графів. Однак за останні півстоліття активного інтенсивного та екстенсивного розвитку теорія графів виробила свою достатньо специфічну власну проблематику і методологію. На сьогодні теорія графів є однією зі складових математичного апарату кібернетики, важливим розділом дискретної математики.

В курсові роботі досліджені властивості ойлерових та гамільтонових ланцюгів та циклів в теорії графів, а також наведені приклади графів.

РОЗДІЛ І ВВЕДЕННЯ В ТЕОРІЮ ГРАФІВ

1.1 Основні поняття та означення

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

Сполучення цих елементів визначає поняття: неорієнтований граф, орієнтований граф та змішаний граф [6].

Рис.1.1. Основні елементи графу (вершина, ребро, дуга)

Неорієнтований граф (неограф) -- це граф (рис.1.2), для кожного ребра якого несуттєвий порядок двох його кінцевих вершин.

Рис.1.2. Неорієнтований граф (вершини та ребра)

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

Рис. 1.3. Орієнтований граф

Рис. 1.4. Змішаний граф

Змішаний граф (рис.1.4) - це граф, що містить як орієнтовані, так і неорієнтовані ребра. Кожної з перерахованих видів графа може містити одне або кілька ребер, у яких обидва кінці сходяться в одній вершині, такі ребра називаються петлями (рис.1.5).



Рис. 1.5. Змішаний граф з петлями

Рис. 1.6. Загальний випадок графа

У загальному випадку множина ребер може складатися із трьох непересічних підмножин: підмножини ланок, підмножини дуг і підмножини петель (рис.1.6).

Рис.1.7. Сутність геометричної конфігурації графа, в якому всі вершини можна обійти за маршрутом без перетинання ребер графу

Наочно граф можна уявляти як геометричну конфігурацію ( див. рис.1.7), яка складається з точок (вершин графу 1,2,3,4,5,6) і ребер (ліній або відрізків №1(1-3), №2(3-4), №3(4-5), №4(3-5), №5(2-3), №6(2-5), №7(5-6), №8(6-2), №9(2-1), які сполучають деякі точки (вершини) за вибраним алгоритмом обходу вершин графу) [5].

Дамо формальне математичне означення графа згідно [11].

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

Означення 1.1.

Граф - пара множин. Множина -це множина вер-шин, множина -це множина ребер. Якщо , то ми говоримо, що ребро сполучає вершину з вершиною ; інша термінологія - ребро і вершини та - інцидентні.

Означення 1.2.

Граф називається повним , якщо , тобто граф складається з максимально можливої кількості ребер, які попарно з'єднують точки його вершин (див.рис.1.8). Якщо множина містить вершин, то, очевидно , число ребер повного графа дорівнює .

Рис.1.8. Приклади повних графів

Означення 1.3.

Граф називається порожнім, якщо , тобто граф не має ребер (див.рис.1.9).

Рис.1.9. Приклад побудови 3-х вершинного графу з різною кількістю ребер (заповнення графу від «порожнього» до «повного»)

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

Теорема 1.1.

Число усіх різних графів з вершинами дорівнює (табл.1.1):

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

Таблиця 1.1

Зображення повних графів з кількістю вершин від 5 до 11 [3]

Означення 1.4.

Вершини та графа інцидентні, якщо .

Означення 1.5.

Степенем вершини графа називається число вершин , які інцидентні вершині ( число відрізків які виходять з вершини ) - див.рис.1.10.

Рис.1.10. Визначення степенів вершин графу по кількості ребер, що виходять із вершин

Означення 1.6.

Якщо , то вершина називається кінцевою вершиною графа . Якщо , то вершини називається ізольованою(див рис. 1.11)

Рис.1.11. Визначення кінцевих та ізольованих вершин графа

1.2 Лема про рукостискання

Формулювання цієї леми просте - „кількість рук, що приймають участь у рукостисканні N-пар людей, дорівнює 2*N”. Лему можна представити у формі графу, де N вершин з'єднані ребрами d(x_i,x_j) рукостискання i та j - вершин (див. рис.1.12), виконавши наступне доведення.



Рис.1.12. „Лема про рукостискання” 5 осіб у вигляді графу „взаємно-простягнутих рук” (10 пар рук для повної множини рукостискань) [3]

Нехай граф з множиною верщин . Тоді

(1.1)

Доведення. Зауважимо,що кожне ребро графа в сумі враховується двічі (див. рис.1.5), і тому спараведива рівність (1.1). Зауважимо, що сума сту-пенів усіх вершин у графі (або мультіграфі без петель) повинна бути парною. Це випливає з того, що якщо взяти вершини, взагалі не пов'язані одна з одною, то сума ступенів цих вершин дорівнює нулю. Додаючи будь-яке ребро, що пов'язує дві вершини, збільшуємо суму всіх ступенів на 2 одиниці. Таким чи-ном, сума всіх ступенів вершин парна. З рівності 1.1 випливає такє твердження: число вершин непарного степеня в графі обовязково є парним числом.

Для визначення матриці суміжності, розглянемо граф . Нехай

Означення 1.7.

Матриця називається матрицею суміжності ( інцидентності) графа .

Матриця суміжності - це симетрична матриця, елементи якої до-рівнюють нулеві або одиниці ( діагональні елементи дорівнюють нулеві) і така, що сума чисел в будь-якому рядку і будь-якому стовпці дорівнює степені від-повідної вершини. Так, для графу, наведеного на рис.1.13, матриця суміжності побудується у вигляді:

Рис.1.13. До побудови матриці суміжності 3-х вершинного графу

Означення 1.8.

Послідовність ребер, в якій сусідні ребра інцидентні одній і тій же вершині називаються ланцюгом. Ланцюг називається простим, якщо всі вершини, належні йому (крім, можливо, першої і останньої), різні; число в цьому випадку називають довжиною ланцюга.

Якщо , то ланцюг називається циклом. Цикл, в якому всі вершини різні, називається простим. Приклади простих ланцюгів та простих циклів наведені на рис.1.14:

(1,3), (3,4), (4,6) - простий ланцюг;

(1,2), (2,5), (5,6) - простий ланцюг;

(1,3), (3,4), (4,6), (6,5), (5,2)Ю (2,1) - простий цикл.



Рис 1.14. Приклад графа з простими ланцюгами та простими циклами

Означення 1.9.

Граф є підграфом графа , якщо .Якщо , то підграф називається остовним підграфом.

Означення 1.10.

Граф є сумою графів , якщо

ця сума називається прямою, якщо ,

1.3 Оцінки для числа ребер з компонентами зв `язності

Означення 1.11.

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

Теорема 1.2.

Кожен граф є прямою сумою зв язних графів.

Доведення. На множині вершин граф визначимо відношення

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

 (1.2)

є прямою сумою зв'язних графів.

Ці графи називаються компонентами зв'язності.

Розглянемо оцінки для числа ребер з компонентами зв'язності.

Теорема 1.3.

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

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

компонентами зв'язності. Викреслимо максимальне можливе число ребер так, щоб не змінювалося число компонент зв'язностя. Число ребер в отриманому графі позначемо .

Розглянемо для прикладу граф, зображений на рисунку (1.15)

Рис. 1.15. Приклад 1 графу для оцінки зв'язності

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



Рис. 1.16. Приклад 1 графу для оцінки зв'язності

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

Для доведення верхньої оцінки в нерівності (1.3) замінимо кожну компо-ненту повним графом. Нехай та два повних, отриманих з компонент зв' язності та , а та число ребер в цих компонентах . Замінемо на повний граф, додавши одну вершину, а замінемо на повний граф, віднявши одну вершину. Тоді загальне число вершин не змінеться, а число ребер збільшиться на додатню величину

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

З нерівності (1.3) випливає такий наслідок.

Наслідок. Будь-який граф з і більше ніж ребрами є зв'язним.

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

Найти компоненти сильної зв'язності графу на рис.1.17.

Відповіді

Рис.1.17. 7-ми вершинний граф для обчислення компонентів зв'язності [10]

1.4 Орієнтовані графи, графи з петлями, графи з паралельними дугами

Дамо означення орієнтованих графів, графів з петлями та графів з пара-лельними дугами.

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

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

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

Рис.1.18. Види орієнтованих графів

Означення 1.12.

Нехай множина вершин , - множина впорядкованих пар елементів з ( будемо називати їх дугами).Орієнтованим графом називатимемо пару множин , де .

Дуга називається дугою з в (див.рис.1.19).



Рис. 1.19. Орієнтований 3-х вершинний граф (,

.)

Теорема 1.4. Число усіх орієнтованих графів з вершинами дорівнює .

Доведення . Справді , число впорядкованих пар елементів з дорівнює , тому число всіх можливих множин дуг дорівнює .

Означення 1.13.

Нехай -множина вершин. Орієнтованим графом з петлями будемо називати пару множин , де (див.рис.1.20).

Рис.1.20. Орієнтований граф з петлями в якому ,

Теорема 1.5. Число орієнтованих графів з петлями , які мають вершин, дорівнює .

Доведення. Справді, число різних множин (підмножин множини ) дорівнює .

Якщо розглядається одночасно декілька типів графів, то графи які описуються означення (1.1), будемо називати простими графами.

Якщо в означенні (1.1) до множини невпорядкованих пар приєднати ще множину всіх пар виду , то відповідний граф називається простим графом з петлями.

З теореми 1.5 випливає довід теореми 1.6 про прості графи.

Теорема 6. Число всіх простих графів з вершинами і петлями дорівнює

Надалі, ми будемо розглядати прості графи.

РОЗДІЛ ІІ ОЙЛЕРОВІ ГРАФИ

2.1 Ойлерова ломиголовка «Кенігзберзьких мостів»

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

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

Перша робота з теорії графів належить Леонарду Ойлеру. Вона з'явилась в публикаціях Санкт-Петербургзської Академії наук у 1736 році.

Праця Ойлера розпочиналася з розгляду однієї ломиголовки так званої „задачі про кенігзберзькі мости”

Місто Кенігзберг (нині Калінінград) розташоване на берегах річки Прегель і двох островах. Різні частини міста сполучені сімома мостами. Щонеділі жителі міста любили здійснювати прогулянки по місту. Ойлер поставив питання: чи можна здійснити прогулянку, вийшовши з дому і повернувшись до нього , таку , щоб по кожному мосту пройти рівно один раз.

Сформулюємо задачу, як задачу теорії графів. Схематична карта міста зображена на рисунку 2.1..

Рис. 2.1. Схема мостів в Кенігзберзі [11]

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

Рис. 2.2. Граф «Кенігзберзьких мостів» в ломи головці Ойлера

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

Виклавши розв язання задачі про кенігзберзькі мости , Ойлер в своїй праці поставив питання : на яких графах можна знайти цикл, який містить всі ребра графа, при чому кожне ребро зустрічається в циклі рівно один раз?

Це дало початок системному математичному підходу до побудови та вивчення властивості графів.

2.2 Основні поняття та означення ойлерових графів

Означення 2.1

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



Рис.2.3. Структура вершин та ребер в неорієнтованому ойлеровому графі (* - означено точку входу ойлерового ланцюга - циклу)

Означення 2.2

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

Рис.2.4. Структура вершин та ребер в неорієнтованому напівойлеровому графі (* - означено точку початку та кінця ойлерового ланцюгу)

Рис.2.5. Приклад неойлерового графу

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

Лема 2.1

Якщо степінь кожної вершини графа не менше двох , то граф містить цикл.

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

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

Лема доведена.

Теорема 2.1 Для зв'язного графа наступні умови еквівалентні:

1. - ойлерів граф;

2. кожна вершина має парний степінь;

3. множину ребер графа можна розбити на прості цикли.

Доведення.

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

Оскільки - зв'язний граф , степінь кожної вершини дорівнює принаймні 2; тому в силу леми 2.1 містить простий цикл . Виключимо ребра циклу , отримаємо остовний підграф , в якому кожна вершина має парний степінь. Якщо немає ребер , то (3) доведено. В протилеж-ному випадку застосуємо проведені вище міркування до , отримаємо граф , в якому степені всіх вершин є парними і так далі. Одночасно з порожнім графом , отримаємо розбиття множини ребер на циклів

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

З теореми 2.1 випливає наступна теорема.

Теорема 2.2. Зв'язний граф є ойлеровим тоді і тільки тоді, коли кожна його вершина має парний степінь.

.

Рис.2.6. Приклад ойлерового графу в теоремі 2.2

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

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

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

3. Множина ребер цього графа є об' єднання двох простих циклів

і .

Теорема 2.3. Зв'язний граф є напівойлеровим тоді і тільки тоді , коли в ньому не більше двох вершин непарного степеня.

Рис. 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).

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

Доведення.

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

Рис.2.11. Граф до теореми 2.5 [3]

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

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

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

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

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

2.3 Приклади ойлерових графів

Приклад 2.1.Задача про призначення на посаду

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

Чи можна кожному з цих людей надати одну з тих посад, які йому підло-дять?

Ми можемо знову проілюструвати цю задачу за допомогою деякого графа, що в даному випадку виглядає особливо. Як уже сказано, є певна група людей, яку ми позначимо як М і деяка множина посад, Р. Будуємо граф, проводячи ребра (м,р), що з'єднує кожну людину м з тими посадами р, які він може зайняти. На цьому графі не буде ребер, що з'єднують між собою дві вершини М чи Р, тому такий граф має вигляд, наведений на рис.2.12:

Рис.2.12. Граф для рішення задачі про призначення на посаду

Завжди знайти підходяще місце для кожного претендента ми не можемо: для цього необхідно, щоб посад було не менше ніж претендентів. Але цього недостатньо.

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

Припустимо, що загальна кількість претендентів - N. Для виконання задачі повинна виконуватись наступна умова:

Яку б групу із k чоловік, k=1,2,...,N, ми не взяли, повинно бути принаймні k посад, кожну з яких може займати хоча б один із наших претендентів.

Наприклад, якщо один з людей є столяром, а другий - одночасно і столя-ром і сантехніка і якщо є два місця сантехніка, то наша умова виконується при k=2, але не виконується при k=1, тому вказані люди не можуть одночасно влаштуватися на роботу.

Виділену умову ми коротко назвемо умовою різноманітності.

Висновок: вищенаведена задача може використовуватись працівниками служби зайнятості для правильного розміщення працівників на посади.

Приклад 2.2. Інші формулювання

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

Припустимо, наприклад, що у нас є група із k хлопців і k дівчат. Дехто з них уже знайомі між собою, і виникає питання: в якому випадку можна розбити цих молодих людей не пари для танців так, щоб всі хлопці танцювали зі знайо-мими дівчатами?

Можна також змінити цю задачу: в маленькому селі є однакова кількість дорослих хлопців і дівчат; звичаєм не допускається, щоб хлопець одружувався на близькій родичці - сестрі, названій сестрі або двоюрідній сестрі. За якої умо-ви для хлопця знайдеться наречена з цього села? Знову ми можемо розв'язати цю задачу за допомогою дводольного графа - в цьому випадку його вершини будуть з'єднані ребрами лише тоді, коли відповідні люди не є родичами.

А ось іще один варіант цієї задачі. В нашій школі є кілька гуртків: C1,C2,…,CN. Кожен із цих гуртків повинен мати старосту.

Для того щоб виключити перевантаження учнів, була поставлена умова, щоб жоден учень не був старостою більш, ніж одного гуртка. За якої умови це можливо?

Зрозуміло, що це можливо не завжди; якщо кількість гуртків в порівняно невеликій школі дужу велика, то це неможливо.

Щоб розв'язати цю задачу, ми знову звернемось до дводольного графа.

В цьому випадку одна множина вершин графа складатиметься із N гуртків,

А інша множина вершин P - це множина всіх учнів школи. Ми проводимо ребро від гуртка С1 до учня р в тому випадку, якщо р є членом С1. При цьому умова різноманітності перетворюється в наступне: кожна група із k гуртків (при k = 1, 2,..., N) повинна включати щонайменше k різних учнів. Згідно вище вказаному - це та умова за якої гуртки можуть мати різних старост.

Якщо кількість гуртків занадто велика, не завжди легко довести спра-ведливість умови різноманітності. Тому поставимо питання: Чи можна вказати яке-небудь просте правило формування гуртків, що гарантує можливість вибо-ру для них різних старост?

Це дійсно можливо. Для того щоб показати, що ми маємо на увазі, припустимо, що кожен гурток складається принаймні з п'яти учнів. Тоді на відповідному графі із кожної вершини множини С буде виходити принаймні 5 ребер. Для групи із k гуртків буде не менше 5k ребер, що виходять із відповідних вершин С до вершин із Р (додаток 2, де k = 4).

Рис.2.13. Граф для вирішення задачі вибору

Тепер, якщо нам буде потрібно, щоб кожен учень брав участь не більше, ніж в п'яти гуртках, це означатиме, що ребра від k гуртків повинні йти при-наймні до k вершин із Р, і, відповідно, умова різноманітності буде виконана.

Ці думки є повністю загальними, тож ми можемо сформулювати наступний результат.

РОЗДІЛ ІІІ ГАМІЛЬТОНОВІ ГРАФИ

3.1 Сутність гамільтонових графів

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

Назва гамільтонів граф виникла у зв язку з тим , що в 1859 році відомий ірландський математик сер Вільям Гамільтон випустив до продажу своєрідну іграшкову головоломку . ЇЇ основою частиною був правильний додекаедр, зроблений з дерева (рис.3.1). Це один з так званих правильних багатогранників: його граням є 12 правильних п'ятикутників, в кожній з його вершин сходиться три ребра. Кожна з вершин гамільтонового додекаедра була позначена назвою одного з крупних міст Земної кулі -Брюсель, Кантон, Делі, Лондон і так далі. Задача полягає в знаходженні шляху вздовж ребер додекаедра, який проходить через кожне місто в точності один раз. Гамільтонів цикл на додекаедрі не пок-риває, звичайно, всіх ребер додекаедра, бо в кожній вершині він проходить в точності по двох ребрах.

Рис.3.1. Гамільтонів цикл у додекаедрі [4]

3.2 Основні поняття та означення

Означення 3.1.

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

Означення.3.2 .

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

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

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

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

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

Встановлено різні достатні умови гамільтоновості графа . Сформулюємо дві з них.

Теорема 3.1.( О.Оре , 1960). Якщо для будь-якої пари і несуміжних вершин графа з вершинами має місце нерівніть

(3.1)

то граф гамільтонів.

Нагадаємо , що степінь вершини , тобто число ребер , які виходять з вершини .

Доведення.

Будемо доводити від супротивного. Припустимо , що існує негамільтонів граф з вершинами, в якому для будь-якої пари несуміжних вершин і виконується умова (3.1). Додавання до графа нових ребер не порушує умову (3.1). Позначимо через максимальний негамільтонів граф , тобто таrий граф , приєднання до якого нового ребра перетворює граф на гамільтонів. Вочевидь, не може бути повним графом, бо повний граф гамільтонів. Тому в існує пара несуміжних вершин і . Приєднання до ребра перетворює граф на гамільтонів в силу максимальної негамільтоновості . Таким чином , існує гамільтонів ланцюг. який сполучає і , він проходить через всі вершини ( рисунок 3.2)

Рис. 3.2. Гамільтонів ланцюг (1)

Оточимо кожну з , які суміжні з , кружечком, і вершину , яка лежить лівіше, квадратиком так, як зображено на рисунку, поданому нижче:

Рис. 3.3. Гамільтонів ланцюг(2)

з цих вершин оточені кружечком;

з цих вершин оточені квардатиком;

- не оточені квадратиком.

Зазначимо , що в силу умови теореми

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

Рис.3.4. Гамільтонів ланцюг(3)

Отже прийшли до суперечності . Теорема доведена.

З теореми 3.1 випливає наступна теорема.

Теорема 3.2 (Г.Дірака, 1952) Якщо для будь-якої вершини графа з вершинами виконується нерівність , то граф гамільтонів.

Доведення. Від супротивного. Нехай -- не гамільтонів. Додамо до мінімальну кількість нових вершин , … ,, з'єднуючи їх з усіма вершинами так, щоб := + + … + був гамільтонів.

Нехай , , , … ,-- гамільтонів цикл у графі , причому , , . Така пари вершин і у гамільтоновому циклі обов'язково знайдеться, інакше граф був би гамільтонов. Тоді , {,…,},інакше вершина була б не потрібна. Більше того, вершина несуміжна з вершиною , інакше вершина була б не потрібна.

Далі, якщо в циклі , , , … ,,, … , є вершина , суміжна з вершиною w, те вершина v' несуміжна з вершиною v, тому що інакше можна було б побудувати гамільтонов цикл ,, … ,,, … , без вершини , взявши послідовність вершин , … , у зворотному порядку. Звідси треба, що число вершин графа , не суміжних з , не менш числа вершин, суміжних з . Але для будь-якої вершини графа d() ? p/2+n по побудові, у тому числі d() p/2+n. Загальне число вершин (суміжних і не суміжних з ) становить n+ p-1. Таким чином, маємо:

n+ p-1 = d(v)+d(V) ? d(w)+d(v) ? p/2+n+p/2+n = 2n+p.

Отже, 0 n+1, що суперечить тому, що n > 0. Теорема доведена.

3.3 Приклади гамільтонових графів

Приклад 3.1. Знайти всі гамільтонові цикли для графа, наведеного на рис.3. 5 [10]

Рис.3.5. Пошук всіх гамільтонових циклів для орієнтованого графа

Таблиця 3.1

Результати пошуку гамільтонових циклів

Приклад 3.2. Знайти найкоротший гамільтонов цикл в задачі «комівояжера» для 6 -міст, розташованих згідно графу на рис.3.6 [10]

Рис.3.6. Графи при вирішенні задачі «комівояжера» [ ]

Результати розрахунків довжини «гамільтонових циклів» в задачі «комівояжера» (рис.3.6) наведені в табл.3.2

Таблиця 3.2

Результати розрахунків довжини «гамільтонових циклів»

Приклад 3.3. Покажіть, що граф, зображений на рисунку 3.7 , не є гамільтоновим [11].

Рис. 3.7. Приклад не гамільтонового графа

Розв'язання.

Припустимо, що в зв'язному графі знайдеться гамільтонов цикл. Кожна вершина v включается в гамільтонів цикл С вибором двох інцидентних з нею ребер, а значить, степінь кожної вершини в гамільтоновому циклі (після вида-лення зайвих ребер) дорівнює 2. Степень вершин даного графа -- 2 чи 3. Вер-шини степеня 2 входять в цикл разом з обома інцидентними з ними ребрами. Отже,ребра аb, ае, cd, cb, hi, hg и ij у тім або іншому порядку входять в гаміль-тонов цикл С (див. рис. 3.8).

Ребро bf не може бути частиною циклу С, оскільки кожна вершина

Такого циклу повинна мати ступінь 2. Значить, ребра fj і fg зобов'язані входити в цикл С, щоб включити в нього вершину f . Але тоді ребра je и gd ніяк не мо-жуть належати циклу С, оскільки у противному випадку у ньому з'являться вершини степеня три. Це змушує нас включити в цикл ребро ed, що приводить нас до протиріччя: ребра, котрі ми були змушені вибрати, утворюють два незв'язних цикла, а не один, існування котрого ми припускали. Висновок: граф, зображений на рисунку 3.8, не є гамільтоновим

Рис.3.8. До доведення негамільтоновості графа

ВИСНОВКИ

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

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

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

Наприклад, у вигляді графа можуть бути зображені:

електричні і транспортні мережі;

інформаційні і комп'ютерні мережі;

карти автомобільних, залізничних і повітряних шляхів, газо- і нафтопроводів;

моделі кристалів;

структури молекул хімічних речовин;

моделі ігор;

різні математичні об'єкти (відношення, частково впорядковані множини, решітки, автомати, ланцюги Маркова, алгоритми і програми тощо);

лабіринти;

плани діяльності або плани виконання певних робіт (розклади);

генеалогічні дерева тощо.

Приклади застосування теорії графів:

пошук зв'язних компонентів у комунікаційних мережах;

пошук найкоротших, “найдешевших” та “найдорожчих” шляхів у комунікаційних мережах;

побудова кістякового дерева: зв'язність з найменшою можливою кількістю ребер;

пошук максимальної течії для транспортної мережі, в якій визначено вхідні та вихідні вершини та пропускні спроможності ребер;

ізоморфізм графів: ідентичність структур молекул (ізометрія);

знаходження циклів графів:

гамільтонів цикл: обійти всі вершини графа, побувавши в кожній з них лише один раз (задача комівояжера);

ейлерів цикл: обійти всі ребра (контроль дієздатності мережі);

розфарбування графів: розфарбування географічних карт, укладання розкладів, розміщення ресурсів тощо;

планарність графів: проектування друкованих електронних та електричних схем, транспортних розв'язок тощо;

знаходження центрів графа: вершин, максимальна відстань від яких до всіх інших вершин графа є мінімальною (“столиць”).

СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ

1. Белов В.В. и др. Теория графов:учебное пособие для втузов.- М.: „Высшая школа”,1976. - 392 с.

2. Березина Л.Ю. Графы и их применение. - М.: Просвещение, 1979. - 143 с.

3. Гервер М. Трехзначные числа и орграфы // Журнал «Квант», Москва, МЦНМО, 1987, №2

4. Кузнецов О.П. Дискретная математика для инженеров. / О.П. Кузнецов, Г.М. Адельсон-Вельский - 2-е изд., перераб. и доп. - М.: Энергоатомиздат, 1988 - 400 с.: ил.

5. Мелихов А.Н. применение графов для проектирования дискретных устройств. / А.Н. Мелихов, Л.С. Бернштейн, В.М. Курейчик - М.: Наука, 1974. 304 с.: ил.

6. Уилсон Р. Введение в теорію графов. - М.: Мир, 1777. - 208 с.

7. Оре О. Графы и их применение. - М.: Изд-во „Мир”, 1965.- 174 с.

8. Оре О. Теория графов. -2-е изд.- М.: „Наука”, 1980.- 205 с.

9. Уилсон Р. Введение в теорію графов. - М.: Мир, 1777. - 208 с.

10. Хаггарти Р Дискретная математика для программистов. - М.: «Техносфера», 2003. - 320 с.

11. Ядренко М.Й. Дискретна математика : навчальний посібник. - К.: Вид. - поліграф.центр „Експрес”, 2003. - 244 с.