Поморського державного університету
ім. М.В. Ломоносова
Курсова робота
Ейлерови ГРАФИВиконала студентка 4 курсу
42 групи математичного
факультету Катишева Н.Г.
Науковий керівник:
Токаревська С.А.
Архангельськ
2004
Зміст
"1-2"
Введення ................................................. ............................................ 3
Глава 1. Теоретична частина ................................................ ............ 4
Основні поняття теорії графів .............................................. ....... 4
Маршрути і зв'язність ............................................... ....................... 6
Задача про кенігсберзькими мостах .............................................. ...... 7
Ейлерови графи ................................................ ............................... 9
Оцінка числа ейлеровим графів .............................................. ...... 13
Алгоритм побудови Ейлера кола в цьому ейлеровим графі. 14
Глава 2. Практична частина ................................................ ........... 15
Висновок ................................................. ...................................... 24
Література ................................................. ...................................... 25
Введення
Перша робота з теорії графів, що належить відомому швейцарському математику Л. Ейлера, з'явилася в 1736г. Спочатку теорія графів здавалася досить незначним розділом математики, так як вона мала справу в основному з математичними розвагами й головоломками. Однак подальший розвиток математики і особливо її додатків дало сильний поштовх розвитку теорії графів. Вже в XIX столітті графи використовувалися при побудові схем.
В даний час ця теорія знаходить численне застосування в різноманітних практичних питаннях: при встановленні різного роду відповідностей, при вирішенні транспортних задач, задач про рух інформації у мережі нафтопроводів, в програмуванні та теорії ігор, теорії передачі повідомлень. Теорія графів тепер застосовується і в таких областях, як економіка, психологія і біологія.
У цій роботі ми докладніше розглянемо Ейлерови графи, основні відомості і теореми, пов'язані з цим поняттям. А також завдання, які вирішуються за допомогою ейлеровим графів.
Глава 1. Теоретична частина.
Основні поняття теорії графів
Граф G - пара (V, X), де V кінцеве непорожнє безліч, що містить p вершин, а безліч Х містить q невпорядкованих пар різних вершин з V.Кожну пару X = {u, v} вершин у Х називають ребром графа G і кажуть, що Х з'єднує u і v. Ми будемо писати X = uv і говорити, що u і v - суміжні вершини. Вершина u і ребро Х інцидентних, так само як v і Х. Якщо два різних ребра X і Y інцидентних однієї і тієї ж вершині, то вони називаються суміжними. Граф з р вершинами і q ребрами називається (p; q) - графом. Граф (1,0) - називається тривіальним. [6]
Якщо елементом множини V може бути пара однакових елементів u, то такий елемент безлічі V називається петлею. [3]
Типи графів:
· Мультіграф, в ньому не допускаються петлі, але пари вершин можуть з'єднуватися більш ніж одним ребром, ці ребра називаються кратними (рис.1).
· Псевдограф, в ньому допускаються петлі і кратні ребра (рис.2).
Рис.1 Рис.2
· Орієнтований граф, або орграф, складається з кінцевого непорожньої безлічі V вершин і заданого набору Х впорядкованих пар різних вершин. Елементи з Х називаються орієнтованими ребрами, або дугами. Ні петель і кратних дуг (рис. 3).
|
| |||||||
· Спрямований граф - це орграф, що не має симетричних пар орієнтованих ребер (рис. 4).
· Помічені графи (або перенумеровані), якщо його вершини відрізняються одна від одної будь-якими позначками. Як позначок зазвичай використовуються букви або цілі числа. [6]
Ступенем вершини v i у графі G називається число ребер, інцидентних v i , Позначається d i. [6] Для орграфа вводяться поняття ступеня входу і виходу. Ступенем виходу вершини v називається кількість ребер, для яких v є початковою вершиною, позначається outdeg (v). Ступенем входу вершини v називається кількість ребер, для яких v є кінцевою вершиною, позначається indeg (v). Якщо indeg (v) = 0, то вершина v називається джерелом. Якщо outdeg (v) = 0, то вершина v називається стоком. [1]
Маршрути і зв'язність
Граф G / (U /, V /) називається подграфом графа G (U, V), якщо U / ÌU і V / ÌV. Позначення: G / ÌG.Якщо V / = V, то G / називається остовних подграфом G. [3]
Маршрутом у графі G називається чергується послідовність вершин і ребер v 0, x 1, v 1, ... v n -1, x n, v n; ця послідовність починається і закінчується вершиною, і кожне ребро послідовності інцидентне двом вершин, одна з яких безпосередньо передує йому, а інша безпосередньо слідує за ним. Зазначений маршрут з'єднує вершини v 0 і v n і його можна позначити v 0 v 1 v 2 ... v n (Наявність ребер мається на увазі). Ця послідовність іноді називається (v 0 - v n)-маршрутом. Маршрут замкнутий, якщо v 0 = v n, і відкритий в іншому випадку. Маршрут називається ланцюгом, якщо всі його ребра різні, і простий ланцюгом, якщо всі вершини (а отже, і ребра) різні. Замкнута ланцюг називається циклом. Замкнуте маршрут називається простим циклом, якщо всі його n вершин різні і n ³ 3.
Граф G називається зв'язковим, якщо будь-яка пара його вершин з'єднана простий ланцюгом. [6]
Задача про кенігсберзькими мостах.
Батьком теорії графів є Ейлер (1707-1782), який вирішив в 1736г. широко відому в той час завдання, що називалася проблемою Кенигсбергских мостів. У місті Кенігсберзі (нині Калінінград) було два острови, з'єднаних сімома мостами з берегами річки Преголя і один з одним так, як показано на малюнку 5. Завдання полягало в наступному: знайти маршрут проходження всіх чотирьох частин суші, який починався б з будь-якою з них, кінчався б на цій же частині і рівно один раз проходив по кожному мосту.Рис.5.
Легко, звичайно спробувати вирішити цю задачу емпірично, виробляючи перебір всіх маршрутів, але всі спроби закінчаться невдачею. Винятковий внесок Ейлера у вирішення цього завдання полягає в тому, що він довів неможливість такого маршруту.Для доказу того, що задача не має рішення, Ейлер позначив кожну частину суші точкою (вершиною), а кожен міст - лінією (ребром), що з'єднує відповідні точки. Вийшов "граф". Цей граф показаний на малюнку 6, де точки відзначені тими ж буквами, що й чотири частини суші на малюнку 5.
Рис.6.
Твердження про не існування "позитивного" рішення у цієї задачі еквівалентно твердженням про неможливість обійти спеціальним чином граф, представлений на малюнку 6.
Вирушаючи від цього окремого випадку Ейлер узагальнив постановку задачі і знайшов критерій існування обходу у даного графа, а саме граф повинен бути зв'язковим і кожна його вершина має бути инцидентна четному числа ребер. [6]
Ейлерови графи
Рішення Ейлером задачі про Кенигсбергских мостах призвела до першої опублікованій роботі з теорії графів. Задачу про обхід мостів можна узагальнити і отримати таку задачу теорії графів: чи можна знайти в даному графі G цикл, у якому всі вершини і всі ребра? Граф, у якому це можливо, називається ейлеровим. Таким чином, Ейлером граф має Ейлером цикл - замкнутий ланцюг, що містить всі вершини і всі ребра. Ясно, що Ейлером граф повинен бути зв'язковим. [6]Якщо зняти обмеження на замкнутість ланцюга, то граф називається полуейлеровим.
Теорема 1 (критерій):
Граф з більш ніж однією вершиною має Ейлером цикл тоді і тільки тоді, коли він зв'язний і кожна його вершина має парну ступінь.
Доказ: Припустимо, що граф G має Ейлером цикл. Граф є зв'язковим, оскільки кожна вершина належить циклу. Для будь-якої вершини v графа G щоразу, коли Ейлером цикл проходить через v, він вносить 2 в ступінь v. Тому ступінь v парна.
Назад, потрібно показати, що кожен зв'язний граф, у якого ступеня вершин парні, має Ейлером цикл. Доведемо цю теорему, використовуючи індукцію за кількістю вершин. Оскільки теорема тривіально справедлива при n £ 3, почнемо індукцію з n = 3. Припустимо, що кожен зв'язний граф, що має менш k вершин, і всі вершини якого мають парному ступенем, містить Ейлером цикл. Нехай G - зв'язний граф, що містить k вершин, ступеня яких парні. Припустимо, що v 1 і v 2 - вершини графа G. Оскільки граф G - зв'язний, існує шлях з v 1 в v 2. Оскільки ступінь v 2 - парна, існує невикористане ребро, по якому можна продовжити шлях. Оскільки граф кінцевий, то шлях, в кінці кінців, повинен повернутися в v 1, і Ейлером цикл З 1 можна вважати побудованим. Якщо С 1 є ейлеровим циклом для G, тоді доказ закінчено. Якщо ні, то нехай G / - підграф графа G, отриманий видаленням всіх ребер, що належать З 1. Оскільки З 1 містить парне число ребер, інцидентних кожній вершині, кожна вершина подграфа G / має парну ступінь.
Нехай e - ребро графа G /, нехай G e - компонента графа G /, що містить тобто Оскільки G / має менше, ніж k, вершин, і в кожної вершини графа G / парна ступінь, граф G / має Ейлером цикл. Нехай З 2. Далі у С 1 і С 2 є загальна вершина, допустимо, а. Тепер можна продовжити Ейлером цикл, починаючи його в а, пройти З 1, повернутися в а, потім пройти С 2 і повернутися в а. Якщо новий Ейлером цикл не є ейлеровим циклом для G , Продовжуємо використовувати цей процес, розширюючи наш Ейлером цикл, поки, до кінці кінців, не отримаємо Ейлером цикл для G [1].
З теореми 1 випливає, що якщо в зв'язковому графі G немає вершин з непарними ступенями, то в G є замкнута ланцюг, що містить всі вершини і всі ребра графа G. Аналогічний результат справедливий для зв'язних графів, що мають деяке число вершин з непарними ступенями.
Слідство 1 (а): Нехай G-зв'язний граф, в якому 2n вершин мають непарні ступеня, n> 1. Тоді безліч ребер графа G можна розбити на n відкритих ланцюгів.
Слідство 1 (б): Нехай G-зв'язний граф, в якому дві вершини мають непарні ступеня. Тоді в G є відкрита ланцюг, що містить всі вершини і всі ребра графа G (і починається в одній з вершин з непарної ступенем, а кончающаяся в іншій). [6]
Ейлеровим шляхом у графі називається шлях, який містить всі ребра графа. Ейлеров шлях називається власним, якщо він не є ейлеровим циклом. [1]
Теорема 2: Якщо граф G має ейлеровим шляхом з кінцями А і В (А не збігається з В), то граф G зв'язний і А і В - єдині непарні його вершини.
Доказ: Зв'язність графа випливає з визначення ейлерова шляху. Якщо шлях починається в А, а закінчується в іншій вершині, то і А і В - непарні навіть якщо шлях неодноразово проходив через А і В. У будь-яку іншу вершину графа шлях повинен був привести і вивести з неї, то є всі інші вершини повинні бути парними.
Теорема 3: (зворотнє) Якщо граф G зв'язний і А і В єдині непарні вершини його, то граф G має ейлеровим шляхом з кінцями А і В.
Доказ: Вершини А і В можуть бути з'єднані ребром у графі, а можуть бути поєднані.
Якщо А і В з'єднані ребром, то видалимо його, і стануть всі вершини стануть парними. Новий граф (по теоремі 1) має ейлеровим циклом, початком і кінцем якого може служити будь-яка вершина. Почнемо Ейлером шлях у вершині А і закінчимо його у вершині А. Додамо ребро (А, В) і отримаємо Ейлером шлях з початком в А і кінцем у В.
Якщо А і В не з'єднані ребром, то до графа додамо нове ребро (А, В), тоді всі вершини його стануть парними. Новий граф (по теоремі 1) має ейлеровим циклом. Почнемо його з вершини А по ребру (А, В). Закінчується шлях теж у вершині А. Якщо видалити тепер з отриманого циклу ребро (А, В), то залишиться Ейлером шлях з початком у В і кінцем в А чи початком в А і кінцем В.
Таким чином, будь-яку замкнуту фігуру, що має в точності дві непарні вершини, можна накреслити одним розчерком без повторень, почавши в одній з непарних вершин, а скінчивши в іншій.
Теорема 4: Якщо зв'язний граф G має 2k непарних вершин, то знайдеться сімейство з k шляхів, які в сукупності містять всі ребра графа в точності по одному разу.
Доказ: Половину непарних вершин позначимо А 1, А 2, ..., А k, іншу половину В 1, В 2, ..., У k (рис.7). Якщо вершини А i і В i (1 <i <k) з'єднані ребром, то видалимо з графа G ребро (А i, У i). Якщо вершини А і В не з'єднані ребром, то додамо до G ребро (А i, У i). Усі вершини нового графа будуть парними, тобто в новому графі знайдеться Ейлером цикл. При відновленні графа G цикл розіб'ється на k окремих шляхів, що містять всі ребра графа. [2]
Рис.7
Нехай G = (V, E) - орієнтований граф. Орієнтованим циклом називається орієнтований шлях ненульовий довжини з вершини в ту ж вершину без повторення ребер.
Нехай G = (V, E) - орієнтований граф. Орієнтований цикл, який включає всі ребра і вершини графа G, називається ейлеровим циклом. Кажуть, що орієнтований граф G має Ейлером цикл.
Теорема 5: Орієнтований граф має Ейлером цикл тоді і тільки тоді, коли він зв'язний і ступінь входу кожної вершини дорівнює ступеня виходу. [1]
Оцінка числа ейлеровим графів
Лемма: У будь-якому графі число вершин непарної ступеня парне.
Доказ: За теоремою 1 сума ступенів усіх вершин число парне. Сума ступенів вершин парному ступеня парна, значить, сума ступенів вершин непарної мірою також парна, значить, їх парне число.
Нехай G (p) - множина всіх графів з р вершинами, а Е (р) - безліч ейлеровим графів з р вершинами.
Теорема 6: Ейлерови графів майже немає, тобто
lim
Доказ: Нехай E / (р) - безліч графів з р вершинами і парними ступенями. Тоді за теореме1 Е (р) ÌЕ / (p) і | Е (р) | £ | Е / (p) |. У будь-якому графі число вершин непарної ступеня парне, отже, будь-граф з Е / (p) можна отримати з деякого графа G (p-1), якщо додати нову вершину і з'єднати її з усіма старими вершинами непарної ступеня. Отже, | Е / (p) | £ | G (p-1) |. Але | G (p) | = 2 C (p, 2). Зауважимо, що
С (k, 2)-C (k-1, 2) = lim
Доказ: Нехай E / (р) - безліч графів з р вершинами і парними ступенями. Тоді за теореме1 Е (р) ÌЕ / (p) і | Е (р) | £ | Е / (p) |. У будь-якому графі число вершин непарної ступеня парне, отже, будь-граф з Е / (p) можна отримати з деякого графа G (p-1), якщо додати нову вершину і з'єднати її з усіма старими вершинами непарної ступеня. Отже, | Е / (p) | £ | G (p-1) |. Але | G (p) | = 2 C (p, 2). Зауважимо, що
=
Далі маємо:
| Е (р) | £ | Е / (p) | £ | G (p-1) | = 2 C (p -1,2) = 2 C (p, 2) - (p -1) = | G (p) | 2 - (p -1)
і
Алгоритм побудови Ейлера кола в цьому ейлеровим графі.
Цей метод відомий під назвою алгоритму Флері.Теорема 7: Нехай G - Ейлером граф, тоді наступна процедура завжди можлива і призводить до Ейлера ланцюга графа G. Виходячи з довільної вершини і, йдемо по ребрах графа довільним чином, дотримуючись лише наступні правила:
1) стираємо ребра по мірі їх проходження і стираємо також ізольовані вершини, які при цьому утворюються;
2) на кожному етапі йдемо по мосту тільки тоді, коли немає інших можливостей.
Доказ: Покажемо спочатку, що вказана процедура може бути виконана на кожному етапі. Припустимо, що ми досягли певної вершини V; тоді якщо V ¹ U, то залишився підграф H зв'язний і містить рівно дві вершини непарної ступеня, а саме U і V. Згідно з теоремою 3 та визначення полуейлеровим графа, граф H містить полуейлеровим ланцюг P з V в U. Оскільки видалення першого ребра ланцюга Р не порушує зв'язності графа Н, то описане в теоремі побудова (Т 1б)) можливо на кожному етапі. Якщо ж V = U, то доказ залишається тим же самим до тих пір, поки є ще ребра, інцидентних вершині U.
Залишилося тільки показати, що дана процедура завжди призводить до повної Ейлера ланцюга. Але це очевидно, тому що в G не може бути ребер, що залишилися не пройденими після використання останнього ребра, інцидентне U. В іншому випадку видалення деякого ребра, суміжного одному з решти, призвело б до незв'язною графу, що суперечить умові 2). [5]
1. Чи існує Ейлером цикл в графі G. Якщо існує, знайдіть його. [2]
Рішення:
А) Так як кожна вершина має парну ступінь, то за критерієм в цьому графі існує Ейлером цикл: 1,4,6,9,10,8,5,3,2,4,7,10,11,8,6, 5,2,1
Б) У цьому графі також кожна вершина має парну ступінь, значить, існує і Ейлером цикл: 1,2,3,4,5,3,1,4,5,2,1
В) Тут кожна вершина має ступінь 5, тобто непарну, отже, в цьому графі (за критерієм) немає ейлерова циклу.
2. Де на виставці слід було б зробити вхід і вихід (рис.8), щоб можна було провести екскурсію по всіх залах, побувавши у кожному з них в точності один раз? [2]
Рис.8
Рішення:
У цьому графі вершини А і В мають ступінь 3, тобто непарну, отже, в ньому існує Ейлером шлях з початком в одній з цих вершин і кінцем в інший. Значить, вхід і вихід слід встановити у вершинах А і В.
3. Серед наведених нижче графів знайдіть ті, які мають Ейлером цикл. [1]
Рішення:
а) Оскільки цей граф зв'язний і кожна його вершина має парну ступінь, то за критерієм ейлерова графа, даний граф має Ейлером цикл:
abejifcbdhjgfacdehgia
б) Цей граф зв'язний, але оскільки всі його вершини мають непарну ступінь, то він не має ейлерова циклу.
в) Цей граф зв'язний, але оскільки всі його вершини мають ступінь 3, тобто непарну, то він не має ейлерова циклу.
г) Даний граф зв'язний, ступеня вершин а і з мають непарну ступінь, значить, цей граф не має ейлерова циклу.
4. Серед наведених нижче графів знайдіть ті, які мають Ейлером цикл. [1]
Рішення:
а) Граф не є зв'язковим, тобто не виконується перша умова критерію, значить, він не має ейлерова циклу.
б) Цей граф є зв'язним і всі його вершини мають парну ступінь, значить, за критерієм ейлерова графа, він має Ейлером цикл:
acfh I jkgdcbf I ljgeda
в) Даний граф зв'язний, але ступеня вершин а і е непарні, отже за критерієм, цей граф не має ейлерова циклу.
г) Граф є зв'язковим, але так як всі його вершини мають непарну ступінь, то граф не має ейлерова циклу.
5. Серед наведених нижче графів знайдіть ті, які мають власний Ейлером шлях. [1]
Рішення:
а) Граф зв'язний, і тільки дві його вершини (a і f) мають непарну ступінь, отже, то згідно теореми 3, граф має власний Ейлером шлях.
б) Граф зв'язний; deg (a) = 3, deg (b) = 3, deg (c) = 3, тобто більше двох вершин мають непарну ступінь, значить, не має ейлерова шляху.
в) Цей граф зв'язний і тільки дві вершини (с і j) мають непарну ступінь, значить, граф має власний Ейлером шлях.
г) Граф зв'язний; deg (a) = 3, deg (b) = 4, deg (c) = 1, deg (d) = 3, тобто більше двох вершин мають непарну ступінь, отже, в цьому графі немає ейлерова шляху .
6. Серед наведених нижче графів знайдіть ті, які мають власний Ейлером цикл. [1]
Рішення:
а) Даний граф зв'язний; deg (a) = 3, deg (b) = 2, deg (c) = 3, deg (d) = 2, deg (e) = 2. Рівно два вершини мають непарну ступінь, значить, по теоремі 3, граф має власний Ейлером шлях.
б) Граф є зв'язковим і рівно дві його вершини (е і f) мають непарну ступінь, значить, даний граф має власний Ейлером шлях.
в) Граф зв'язний, знайдемо ступеня вершин: deg (d) = 5, deg (b) = 5, deg (e) = 5, знайшлися три вершини, ступінь яких непарна, значить, граф не має ейлерова шляху.
г) Даний граф зв'язний і тільки дві його вершини (а і b) мають непарну ступінь, значить, цей граф має власний Ейлером шлях.
7. Які з наступних орієнтованих графів мають ейлерову циклу? [1]
Рішення:
а) Граф зв'язний, знайдемо ступеня входу і виходу вершин (по теоремі 5 ступеня входу і виходу кожної вершини повинні збігатися):
indeg (a) = 2, outdeg (a) = 1, тобто знайшлася вершина, у якої не збігаються ступеня входу і виходу, значить, граф не має ейлерова циклу.
б) Граф зв'язний, знайдемо ступеня вершин:
indeg (a) = 2 outdeg (a) = 2
indeg (b) = 2 outdeg (b) = 2
indeg (c) = 2 outdeg (c) = 2
indeg (d) = 2 outdeg (d) = 2
indeg (e) = 2 outdeg (e) = 2
Отже, за теоремою 5, граф має Ейлером цикл.
в) Граф зв'язний, знайдемо ступеня вершин:
indeg (a) = 2 outdeg (a) = 2
indeg (b) = 1 outdeg (b) = 1
indeg (c) = 3 outdeg (c) = 1
Умови теореми 5 не виконуються, значить, граф не має ейлерова циклу.
г)) Граф зв'язний, знайдемо ступеня вершин:
indeg (a) = 2 outdeg (a) = 1
Отже, тому що умови теореми 5 не виконуються то, граф не має ейлерова циклу.
8. Які з наступних орієнтованих графів мають ейлерову циклу? [1]
Рішення:
а) Граф зв'язний, знайдемо ступеня вершин:
indeg (a) = 1 outdeg (a) = 1
indeg (b) = 5 outdeg (b) = 1
Оскільки друга умова теореми 5 не виконується, значить, граф не має ейлерова циклу.
б) Граф не зв'язний, тобто перша умова теореми 5 не виконується. Значить, граф не має ейлерова циклу.
в) Граф зв'язний, знайдемо ступеня вершин:
indeg (a) = 2 outdeg (a) = 1
Друга умова теореми 5 не виконується, значить, граф не має ейлерова циклу.
г) Граф зв'язний, знайдемо ступеня вершин:
indeg (a) = 2 outdeg (a) = 2
indeg (b) = 3 outdeg (b) = 1
Граф не має ейлерова циклу, тому що не виконується друга умова теореми 5.
9. На малюнку план підземелля, в одній з кімнат якого приховані багатства лицаря. Після смерті лицаря його спадкоємці знайшли заповіт, в якому було сказано, що для відшукання скарбів досить увійти в одну з крайніх кімнат підземелля, пройти через усі двері, причому в точності по одному разу через кожну; скарби сховані за тими дверима, яка буде пройдена останньої . У якій кімнаті були сховані скарби?
Побудуємо граф, вершинами якого є кімнати підземелля, а ребрами - двері. Потім знайдемо такий шлях, щоб пройти по всіх ребрах (через усі двері) в точності по одному разу.
Даний граф має Ейлером шлях, тому що тільки дві вершини мають непарну ступінь, це вершини 6 і 18. Значить, вхід і вихід можуть бути лише у вершинах 6 і 18.
Так як кімната 6 є крайньою, то в ній буде вхід, значить, останньої кімнатою буде 18-а, отже скарби сховані в цій кімнаті.
Відомо, що Ейлерови графи отримали широке розповсюдження і популярність завдяки тому, що багато головоломки і завдання можна вирішити з використанням знань теорії графів. Приватні приклади таких головоломок і сюжетних завдань були приведені в практичній частині. Задачі на відшукання шляхів через лабіринти, близькі до завдань на Ейлерови графи, знаходять застосування в сучасній психології і при конструюванні обчислювальних машин. Також з практичної точки зору, зараз графи застосовують у багатьох інших областях науки таких як: програмування, фізика, хімія, біологія, економіка і т.д.
2. Березіна Л. Ю. Графи і їхнє застосування. - М.: Просвещение, 1979.
3. Новіков С.А. Дискретна математика для програмістів - СПб.: Питер, 2001. - 304с.
4. Оре о. Графи і їхнє застосування. - М.: Світ, 1973.
5. Уілсон Р. Введення в теорію графів. - М.: Світ, 1977.
6. Харарі Ф. Теорія графів. - М.: Світ, 1973.
2) на кожному етапі йдемо по мосту тільки тоді, коли немає інших можливостей.
Доказ: Покажемо спочатку, що вказана процедура може бути виконана на кожному етапі. Припустимо, що ми досягли певної вершини V; тоді якщо V ¹ U, то залишився підграф H зв'язний і містить рівно дві вершини непарної ступеня, а саме U і V. Згідно з теоремою 3 та визначення полуейлеровим графа, граф H містить полуейлеровим ланцюг P з V в U. Оскільки видалення першого ребра ланцюга Р не порушує зв'язності графа Н, то описане в теоремі побудова (Т 1б)) можливо на кожному етапі. Якщо ж V = U, то доказ залишається тим же самим до тих пір, поки є ще ребра, інцидентних вершині U.
Залишилося тільки показати, що дана процедура завжди призводить до повної Ейлера ланцюга. Але це очевидно, тому що в G не може бути ребер, що залишилися не пройденими після використання останнього ребра, інцидентне U. В іншому випадку видалення деякого ребра, суміжного одному з решти, призвело б до незв'язною графу, що суперечить умові 2). [5]
Глава 2. Практична частина
Завдання:1. Чи існує Ейлером цикл в графі G. Якщо існує, знайдіть його. [2]
А) |
В) |
Б) |
Рішення:
А) Так як кожна вершина має парну ступінь, то за критерієм в цьому графі існує Ейлером цикл: 1,4,6,9,10,8,5,3,2,4,7,10,11,8,6, 5,2,1
Б) У цьому графі також кожна вершина має парну ступінь, значить, існує і Ейлером цикл: 1,2,3,4,5,3,1,4,5,2,1
В) Тут кожна вершина має ступінь 5, тобто непарну, отже, в цьому графі (за критерієм) немає ейлерова циклу.
2. Де на виставці слід було б зробити вхід і вихід (рис.8), щоб можна було провести екскурсію по всіх залах, побувавши у кожному з них в точності один раз? [2]
Рис.8
Рішення:
У цьому графі вершини А і В мають ступінь 3, тобто непарну, отже, в ньому існує Ейлером шлях з початком в одній з цих вершин і кінцем в інший. Значить, вхід і вихід слід встановити у вершинах А і В.
3. Серед наведених нижче графів знайдіть ті, які мають Ейлером цикл. [1]
Рішення:
а) Оскільки цей граф зв'язний і кожна його вершина має парну ступінь, то за критерієм ейлерова графа, даний граф має Ейлером цикл:
abejifcbdhjgfacdehgia
б) Цей граф зв'язний, але оскільки всі його вершини мають непарну ступінь, то він не має ейлерова циклу.
в) Цей граф зв'язний, але оскільки всі його вершини мають ступінь 3, тобто непарну, то він не має ейлерова циклу.
г) Даний граф зв'язний, ступеня вершин а і з мають непарну ступінь, значить, цей граф не має ейлерова циклу.
4. Серед наведених нижче графів знайдіть ті, які мають Ейлером цикл. [1]
Рішення:
а) Граф не є зв'язковим, тобто не виконується перша умова критерію, значить, він не має ейлерова циклу.
б) Цей граф є зв'язним і всі його вершини мають парну ступінь, значить, за критерієм ейлерова графа, він має Ейлером цикл:
acfh I jkgdcbf I ljgeda
в) Даний граф зв'язний, але ступеня вершин а і е непарні, отже за критерієм, цей граф не має ейлерова циклу.
г) Граф є зв'язковим, але так як всі його вершини мають непарну ступінь, то граф не має ейлерова циклу.
5. Серед наведених нижче графів знайдіть ті, які мають власний Ейлером шлях. [1]
Рішення:
а) Граф зв'язний, і тільки дві його вершини (a і f) мають непарну ступінь, отже, то згідно теореми 3, граф має власний Ейлером шлях.
б) Граф зв'язний; deg (a) = 3, deg (b) = 3, deg (c) = 3, тобто більше двох вершин мають непарну ступінь, значить, не має ейлерова шляху.
в) Цей граф зв'язний і тільки дві вершини (с і j) мають непарну ступінь, значить, граф має власний Ейлером шлях.
г) Граф зв'язний; deg (a) = 3, deg (b) = 4, deg (c) = 1, deg (d) = 3, тобто більше двох вершин мають непарну ступінь, отже, в цьому графі немає ейлерова шляху .
6. Серед наведених нижче графів знайдіть ті, які мають власний Ейлером цикл. [1]
Рішення:
а) Даний граф зв'язний; deg (a) = 3, deg (b) = 2, deg (c) = 3, deg (d) = 2, deg (e) = 2. Рівно два вершини мають непарну ступінь, значить, по теоремі 3, граф має власний Ейлером шлях.
б) Граф є зв'язковим і рівно дві його вершини (е і f) мають непарну ступінь, значить, даний граф має власний Ейлером шлях.
в) Граф зв'язний, знайдемо ступеня вершин: deg (d) = 5, deg (b) = 5, deg (e) = 5, знайшлися три вершини, ступінь яких непарна, значить, граф не має ейлерова шляху.
г) Даний граф зв'язний і тільки дві його вершини (а і b) мають непарну ступінь, значить, цей граф має власний Ейлером шлях.
7. Які з наступних орієнтованих графів мають ейлерову циклу? [1]
Рішення:
а) Граф зв'язний, знайдемо ступеня входу і виходу вершин (по теоремі 5 ступеня входу і виходу кожної вершини повинні збігатися):
indeg (a) = 2, outdeg (a) = 1, тобто знайшлася вершина, у якої не збігаються ступеня входу і виходу, значить, граф не має ейлерова циклу.
б) Граф зв'язний, знайдемо ступеня вершин:
indeg (a) = 2 outdeg (a) = 2
indeg (b) = 2 outdeg (b) = 2
indeg (c) = 2 outdeg (c) = 2
indeg (d) = 2 outdeg (d) = 2
indeg (e) = 2 outdeg (e) = 2
Отже, за теоремою 5, граф має Ейлером цикл.
в) Граф зв'язний, знайдемо ступеня вершин:
indeg (a) = 2 outdeg (a) = 2
indeg (b) = 1 outdeg (b) = 1
indeg (c) = 3 outdeg (c) = 1
Умови теореми 5 не виконуються, значить, граф не має ейлерова циклу.
г)) Граф зв'язний, знайдемо ступеня вершин:
indeg (a) = 2 outdeg (a) = 1
Отже, тому що умови теореми 5 не виконуються то, граф не має ейлерова циклу.
8. Які з наступних орієнтованих графів мають ейлерову циклу? [1]
Рішення:
а) Граф зв'язний, знайдемо ступеня вершин:
indeg (a) = 1 outdeg (a) = 1
indeg (b) = 5 outdeg (b) = 1
Оскільки друга умова теореми 5 не виконується, значить, граф не має ейлерова циклу.
б) Граф не зв'язний, тобто перша умова теореми 5 не виконується. Значить, граф не має ейлерова циклу.
в) Граф зв'язний, знайдемо ступеня вершин:
indeg (a) = 2 outdeg (a) = 1
Друга умова теореми 5 не виконується, значить, граф не має ейлерова циклу.
г) Граф зв'язний, знайдемо ступеня вершин:
indeg (a) = 2 outdeg (a) = 2
indeg (b) = 3 outdeg (b) = 1
Граф не має ейлерова циклу, тому що не виконується друга умова теореми 5.
9. На малюнку план підземелля, в одній з кімнат якого приховані багатства лицаря. Після смерті лицаря його спадкоємці знайшли заповіт, в якому було сказано, що для відшукання скарбів досить увійти в одну з крайніх кімнат підземелля, пройти через усі двері, причому в точності по одному разу через кожну; скарби сховані за тими дверима, яка буде пройдена останньої . У якій кімнаті були сховані скарби?
| 2 | |||||
| 4 | 5 | 6 | |||
| 8 | 9 | 10 | |||
| 12 | 13 | 14 | 15 | ||
| 17 | 18 | 19 | |||
| 21 | |||||
Даний граф має Ейлером шлях, тому що тільки дві вершини мають непарну ступінь, це вершини 6 і 18. Значить, вхід і вихід можуть бути лише у вершинах 6 і 18.
Так як кімната 6 є крайньою, то в ній буде вхід, значить, останньої кімнатою буде 18-а, отже скарби сховані в цій кімнаті.
Висновок
У даній роботі були розглянуті основні поняття теорії графів, їх види. Велику увагу приділили питанню існування в них ейлеровим ланцюгів і циклів, розглянули ряд теорем і властивостей. Описали алгоритм знаходження ейлерова циклу в довільному графі, а в практичній частині показали його застосування на конкретних прикладах.Відомо, що Ейлерови графи отримали широке розповсюдження і популярність завдяки тому, що багато головоломки і завдання можна вирішити з використанням знань теорії графів. Приватні приклади таких головоломок і сюжетних завдань були приведені в практичній частині. Задачі на відшукання шляхів через лабіринти, близькі до завдань на Ейлерови графи, знаходять застосування в сучасній психології і при конструюванні обчислювальних машин. Також з практичної точки зору, зараз графи застосовують у багатьох інших областях науки таких як: програмування, фізика, хімія, біологія, економіка і т.д.
Література
1. Андерсон, Джеймс А. Дискретна математика і комбінаторика: пров. з англ. - М.: Видавничий дім «Вільямс», 2003. - 960с.2. Березіна Л. Ю. Графи і їхнє застосування. - М.: Просвещение, 1979.
3. Новіков С.А. Дискретна математика для програмістів - СПб.: Питер, 2001. - 304с.
4. Оре о. Графи і їхнє застосування. - М.: Світ, 1973.
5. Уілсон Р. Введення в теорію графів. - М.: Світ, 1977.
6. Харарі Ф. Теорія графів. - М.: Світ, 1973.