Размещено на http://www.allbest.ru/

Поморського державного університету

ім. М.В. Ломоносова

Курсова робота

Ейлерові графи

Виконала студентка 4 курсу

42 групи математичного

факультету Катишева Н.Г.

Науковий керівник:

Токаревська С.А.

Архангельськ

2004

Зміст

Введення

Глава 1. Теоретична частина

1.1 Основні поняття теорії графів

1.2 Маршрути і зв'язність

1.3 Задача про кенігсберзькими мостах

1.4 Ейлерови графи

1.5 Оцінка числа ейлеровим графів

1.6 Алгоритм побудови Ейлера кола в цьому ейлеровим графі

Висновок

Література

Введення

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

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

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

теорія графа кенігсберзький ейлеровий

Глава 1. Теоретична частина

1.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) - називається тривіальним. Якщо елементом множини V може бути пара однакових елементів u, то такий елемент безлічі V називається петлею. [3]

Типи графів:

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

· Псевдограф, в ньому допускаються петлі і кратні ребра (рис.2).

Рис.1

Рис.2

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

Рис.3

Рис.4

· Спрямований граф - це орграф, що не має симетричних пар орієнтованих ребер (рис. 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]

1.2 Маршрути і зв'язність

Граф 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 ₀ і v _n і його можна позначити v ₀ v ₁ v ₂ ... v _n (Наявність ребер мається на увазі). Ця послідовність іноді називається (v ₀ - v _{n)-маршрутом.} Маршрут замкнутий, якщо v ₀ = v _n, і відкритий в іншому випадку. Маршрут називається ланцюгом, якщо всі його ребра різні, і простий ланцюгом, якщо всі вершини (а отже, і ребра) різні. Замкнута ланцюг називається циклом. Замкнуте маршрут називається простим циклом, якщо всі його n вершин різні і n і 3.

Граф G називається зв'язковим, якщо будь-яка пара його вершин з'єднана простий ланцюгом. [6]

1.3 Задача про кенігсберзькими мостах

Батьком теорії графів є Ейлер (1707-1782), який вирішив в 1736г. широко відому в той час завдання, що називалася проблемою Кенигсбергских мостів. У місті Кенігсберзі (нині Калінінград) було два острови, з'єднаних сімома мостами з берегами річки Преголя і один з одним так, як показано на малюнку 5. Завдання полягало в наступному: знайти маршрут проходження всіх чотирьох частин суші, який починався б з будь-якою з них, кінчався б на цій же частині і рівно один раз проходив по кожному мосту.

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

Для доказу того, що задача не має рішення, Ейлер позначив кожну частину суші точкою (вершиною), а кожен міст - лінією (ребром), що з'єднує відповідні точки. Вийшов "граф". Цей граф показаний на малюнку 6, де точки відзначені тими ж буквами, що й чотири частини суші на малюнку 5.

Рис.6.

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

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

1.4 Ейлерові графи

Рішення Ейлером задачі про Кенігсбергських мостах призвела до першої опублікованій роботі з теорії графів. Задачу про обхід мостів можна узагальнити і отримати таку задачу теорії графів: чи можна знайти в даному графі G цикл, у якому всі вершини і всі ребра? Граф, у якому це можливо, називається ейлеровим. Таким чином, Ейлером граф має Ейлером цикл - замкнутий ланцюг, що містить всі вершини і всі ребра. Ясно, що Ейлером граф повинен бути зв'язковим. [6]

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

Теорема 1 (критерій)

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

Доказ: Припустимо, що граф G має Ейлером цикл. Граф є зв'язковим, оскільки кожна вершина належить циклу. Для будь-якої вершини v графа G щоразу, коли Ейлером цикл проходить через v, він вносить 2 в ступінь v. Тому ступінь v парна.

Назад, потрібно показати, що кожен зв'язний граф, у якого ступеня вершин парні, має Ейлером цикл. Доведемо цю теорему, використовуючи індукцію за кількістю вершин. Оскільки теорема справедлива при n Ј 3, почнемо індукцію з n = 3. Припустимо, що кожен зв'язний граф, що має менш k вершин, і всі вершини якого мають парному ступенем, містить Ейлером цикл. Нехай G - зв'язний граф, що містить k вершин, ступеня яких парні. Припустимо, що v ₁ і   v ₂ - вершини графа G. Оскільки граф G - зв'язний, існує шлях з v ₁ в v _2. Оскільки ступінь v ₂ - парна, існує невикористане ребро, по якому можна продовжити шлях. Оскільки граф кінцевий, то шлях, в кінці кінців, повинен повернутися в v _1, і Ейлером цикл З ₁ можна вважати побудованим. Якщо С ₁ є ейлеровим циклом для G, тоді доказ закінчено. Якщо ні, то нехай G ^/ - під граф графа G, отриманий видаленням всіх ребер, що належать З _1. Оскільки З ₁ містить парне число ребер, інцидентних кожній вершині, кожна вершина під графа G ^/ має парну ступінь.

Нехай e - ребро графа G ^/, нехай G _e - компонента графа G ^/, що містить тобто Оскільки G ^/ має менше, ніж k, вершин, і в кожної вершини графа G ^/ парна ступінь, граф G ^/ має Ейлером цикл. Нехай З _2. Далі у С ₁ і С ₂ є загальна вершина, допустимо, а. Тепер можна продовжити Ейлером цикл, починаючи його в а, пройти З _1, повернутися в а, потім пройти С ₂ і повернутися в а. Якщо новий Ейлером цикл не є ейлеровим циклом для 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.5 Оцінка числа ейлеревими графами

Лема: У будь-якому графі число вершин непарної ступеня парне.

Доказ: За теоремою 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) ==  

Далі маємо:

| Е (р) | Ј | Е ^/ (p) | Ј | G (p-1) | = 2 ^{C (p -1,2)} = 2 ^{C (p, 2) - (p -1)} = | G (p) | 2 ^{- (p -1)}

, Звідки lim . [3]

1.6 Алгоритм побудови Ейлеревого кола в ейлеревім графі

Цей метод відомий під назвою алгоритму Флері.

Теорема 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. Андерсон, Джеймс А. Дискретна математика і комбінаторика: пров. з англ. - М.: Видавничий дім «Вільямс», 2003. - 960с.

2. Березіна Л. Ю. Графи і їхнє застосування. - М.: Просвещение, 1979.

3. Новіков С.А. Дискретна математика для програмістів - СПб.: Питер, 2001. - 304с.

4. Оре о. Графи і їхнє застосування. - М.: Світ, 1973.

5. Уілсон Р. Введення в теорію графів. - М.: Світ, 1977.

6. Харарі Ф. Теорія графів. - М.: Світ, 1973.

Размещено на Allbest.ru