КУРСОВА РОБОТА
з дисципліни
„Алгебра та теорія чисел”
за темою
„Основи теорії графів.
Властивостіойлерових та гамільтонових графів”
ЗМІСТ
ВСТУП
РОЗДІЛ І ВВЕДЕННЯ В ТЕОРІЮ ГРАФІВ
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(xi,xj) рукостискання 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. В зв’язномуграфі існує орієнтований цикл, який проходить через ребро по одному разу вкожному з двох напрямів.
Доведення.
Сформулюємозагальне правило побудови ланцюга, який проходить взовж всіх ребер графа вточності по одному разу в кожному напрямі. Розпоч-немо з довільної вершини /> і пройдемо вздовж />, відзначивши це ребромаленькою стрілкою в точці />, якапоказує вибраний напрям. Потім перехо-димо послідовно до інших вершин. Одній йті ж вершини можна відвідувати і декілька раз. Кожного разу, потрапивши вякусь вершину, ми будемо ставити на відповідному ребрі стрілку, яка вказуєнапрям прибуття. Крім того, потрап-ляючи в якусь вершину вперше, ми як-небудьвідзначимо вхідне ребро, щоб потім його можна було відрізнити від інших.
А1
А0 />
Рис.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 с.