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

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

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

СХІДНОЄВРОПЕЙСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ

ІМЕНІ ЛЕСІ УКРАЇНКИ

Кафедра математичного аналізу, алгебри і геометрії

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

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

Виконала студентка 21 групи

Матвіюк Юлія Ігорівна

Науковий керівник доцент кафедри

геометрії і алгебри Швай Ольга Леонідівна

ЛУЦЬК 2016

Зміст

граф матриця ейлеровий алгоритм

Вступ

1. Введення в теорію графів

1.1 Основні означення та властивості графів

1.2 Способи подання графів

1.2.1 Матриця інцидентності

1.2.2 Матриця суміжності

1.2.3 Подання графа списком пар (списком ребер)

1.2.4 Подання графа списком суміжності

1.3 Зв'язність графів

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

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

2.2 Ейлерові цикли у графі

2.3 Ейлерові ланцюги у графі

2.4 Алгоритм Флері побудови ейлерового циклу

Висновки

Список використаних джерел

Додатки

Додаток А

Додаток Б

Вступ

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

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

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

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

Наведені вище міркування підтверджують актуальність вибраної роботи.

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

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

Об'єкт дослідження - ейлерові графи.

Для досягнення поставленої мети необхідно виконати наступні завдання:

- розглянути основні означення та властивості графів;

- ввести способи подання графів;

- розглянути поняття зв'язності графів;

- довести теорему Ейлера про існування циклічного маршруту у зв'язному графі;

- обгрунтувати алгоритм Флері побудови ейлерового циклу;

- розв'язати вправи.

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

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

1. Введення в теорію графів

1.1 Основні означення та властивості графів

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

Рис. 1.1

Нехай V -- довільна множина, U-- деяка сукупність пар вигляду (v_i,, v_j), де v_i, v_j єV . Термін сукупність означає можливість наявності однакових пар вигляду (v_i,, v_j) і пар вигляду (v_i,, v_i).

Упорядковану пару G = (V, U), що складається з множини V та сукупності U, називається графом із множиною вершин V і множиною ребер U. Графи зручно зображувати графічно, що і зумовило появу їхньої назви (рис. 1.2). При цьому елементи множини V зображають крапками на площині, а ребра (v_i,, v_j) -- відрізками (прямолінійними або криволінійними), які з'єднують точки v_i, та v_j. Граф називається скінченним, якщо множини його вершин і ребер є скінченними. Множину вершин графа G позначають V(G), а множину ребер -- Е(G). Кількість вершин графа n(G)=, а кількість ребер m(G)=. Кількість вершин n(G) графа називають його порядком.

Кількість ребер графа, інцидентних деякій вершині v називається локальним степенем, або просто степенем, вершини v і позначається с(v). Якщо e=(v, w) є E(G) то кажуть:

вершини v та w суміжні;

вершини v і w є кінцями ребра e;

вершини v та w -- інцидентні ребру е;

ребро е -- інцидентне вершинам v і w [2, с.243-244].

Рис. 1.2

Вершина називається непарною, якщо її степінь непарний, парною - якщо степінь парний.

Лема. Сума степенів усіх вершин графа є парним числом.

Отже, у будь-якому графі число вершин непарного степеня - число парне [4, с.95].

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

Множина ребер U може бути порожньою (рис. 1.2, а). Такий граф називається нуль-графом і позначається Ш. Якщо ж множина вершин V-- порожня, то порожньою є також множина U. Такий граф називається порожнім. Лінії, що зображають ребра графа, можуть перетинатися, але точки перетину не є вершинами (рис. 1.2, в); різні ребра можуть бути інцидентними одній тій самій парі вершин (рис. 1.2, г), такі ребра називаються кратними. Цей випадок відповідає наявності кількох однакових пар (v_i, v_j) є E(G). Граф, що містить кратні ребра, називається мультиграфом. Ребро може з'єднувати деяку вершину саму з собою (рис. 1.2, д), таке ребро називається петлею. Цей випадок відповідає наявності в множині U пар вигляду (v, v). Граф із петлями та кратними ребрами називається псевдографом.

Фрагмент нескінченного графа зображено на рис. 1.2, б. Його вершини - це точки площини з цілими координатами (x, y), а ребра, що з'єднують їх, - горизонтальні й вертикальні відрізки [2, с.244].

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

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

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

Граф називається двочастинним, якщо існує таке розбиття множини його вершин на два класи, при якому кінці кожного ребра лежать у різних класах. Якщо ж у двочастинному графі довільні дві вершини з різних класів - суміжні, то граф називається повним двочастинним. Позначається так: K_n,m де n, m - кількість вершин графа першого і другого класів відповідно.

Повний двочастинний граф К_{1, 5} називається зірковим [4, с.95-96].

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

Якщо пари (v, w) є Е вважаються впорядкованими, то граф є орієнтованим. Інакше граф, називаємся неорієнтованим. Ребра орієнтованого графа прийнято називали дугами та зображати напрямленими відрізками, як на рис. 1.3.

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

Рис. 1.3

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

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

Про дугу (v, w) кажуть, що вона виходить із вершини v та входить у вершину w. Іноді вершини v та w називають відповідно початком та кінцем дуги (v, w) [2, с.244-245].

1.2 Способи подання графів

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

Розглянемо декілька інших способів подання графів для двох найважливіших типів графів: простого (рис. 1.4.1) й орієнтованого (рис. 1.4.2).

Рис. 1.4.1 Рис. 1.4.2

Матрицю, кожний елемент якої дорівнює 0 чи 1, називають булевою.

1.2.1 Матриця інцидентності

Нехай G=(V, E) -- простий граф із множиною вершин V={v₁, v₂,..., v_n} і

множиною ребер Е = {е₁, е₂,..., е_m}.

Матрицею інцидентності графа G, яка відповідає заданій нумерації вершин і ребер, називають булеву nЧm матрицю М з елементами m_ij (і= 1,..., n; j= 1,..., m), де

Приклад 1.1. Для графа, зображеного на рис. 1.4.1, матриця інцидентності має вигляд

Отже, для простого графа в матриці інцидентності в кожному стовпці точно дві одиниці, і немає однакових стовпців. Матрицю інцидентності можна

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

За допомогою матриці інцидентності можна подавати й орієнтовані графи. Для таких графів вона також не булева. Нехай G=(V,E) -- орієнтований граф із множиною вершин V={v₁, v₂,..., v_n} і множиною дуг Е = {е₁, е₂,..., е_m}.

Матрицею інцидентності орієнтованого графа G, яка відповідає заданій

нумерації вершин і дуг, називають nЧm матрицю М з елементами m_ij (і= 1,..., n; j= 1,..., m), де

Приклад 1.2. Для графа, зображеного на рис. 1.4.2, матриця інцидентності має вигляд

З алгоритмічного погляду матриця інцидентності -- це, мабуть, найгірший спосіб подання графа, який тільки можна собі уявити. По-перше, для цього потрібно nm комірок пам'яті, більшість із яких зайняті нулями. По-друге, доcтуп до інформації незручний. Щоб отримати відповідь на елементарні питання (наприклад, чи існує дуга (v_i, v_j), до яких вершин ведуть дуги з v_i), у найгіршому випадку потрібно перебрати всі стовпці матриці, тобто виконати m кроків.

1.2.2 Матриця суміжності

Нехай G=(V,E) -- простий граф, . Припустимо, що вершини графа G занумеровані: v₁, v₂,..., v_n. Матрицею суміжності графа G (яка відповідає даній нумерації вершин) називають булеву nЧm матрицю А з елементами a_ij (i, j= 1,..., п), де

Приклад 1.3. Матриця суміжності для графа, зображеного на рис.1.4.1, має вигляд

Цілком очевидно, що для неорiєнтоваггого графа а_ij=а_ji, тобто матриця

суміжності симетрична. Більше того, позаяк у простому графі немає петель, то для нього в матриці суміжності a_ii = 0 (i= 1,..., n).

Матрицю суміжності можна використовувати також для подання псевдографа. Тоді це не булева матриця: елемент а_ij дорівнює кількості ребер, що з'єднують v_i та v_j. Петлю у вершині v_i подають значенням діагонального елемента a_ii=1.

Для подання орієнтованих графів також використовують матрицю суміжності. Це булева nЧm матриця А з елементами a_ij (i, j= 1,..., п), де

Приклад 1.4. Матриця суміжності для графа, зображеного на рис. 1.4.2, має вигляд

Зазначимо, що матриця суміжності орієнтованого графа, загалом кажучи, несиметрична.

Матрицю суміжності можна використовувати й для подання орієнтованого мультиграфа. У такому разі це не булева матриця: елемент a_ij дорівнює кількості дуг, які мають v_i початковою вершиною, a v_j -- кінцевою.

Велика перевага матриці суміжності як способу подання графа -- швидкий доступ до інформації: за один крок можна одержати відповідь на питання, чи існує ребро (дуга) з v_i у v_j. Вада полягає в тому, що незалежно від кількості ребер обсяг пам'яті становить n² комірок.

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

1.2.3 Подання графа списком пар (списком ребер)

Метод зображення графа списком пар, які відповідають його ребрам (або дугам), значно економніший щодо пам'яті, особливо якщо m (кількість ребер) значно менша, ніж n² (n -- кількість вершин). Пара [u, v] відповідає ребру {u, v}, якщо граф неорієнтований, і дузі (u, v), якщо граф орієнтований.

Для графів, зображених на рис. 1.4.1 та 1.4.2, списки пар подані відповідно на рис. 1.5, а та 1.5, б.



Рис. 1.5

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

1.2.4 Подання графа списком суміжності

Орієнтований граф G (без кратних дуг, але, можливо, з петлями) можна подати зазначивши скінченну непорожню множину вершин V та відповідність Г, котра показує, як зв'язані між собою вершини. Відповідність Г - багатозначне відображення множини V у V. Граф у такому разі позначають парою G=(V, Г).

Приклад 1.5. Для орієнтованого графа, зображеного на рис. 4.2, відповідність Г задано табл. 1.1.

Таблиця 1.1

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

Приклад 1.6. Для простого графа, зображеного на рис. 1.4.1 відповідність Г задано табл. 1.2.

Таблиця 1.2

Якщо відображення Г діє не на одну вершину, а на множину вершин А = {v_i1, v_i2,..., v_ip}, то під Г(A) розуміють об'єднання множин

Розглянемо спосіб комп'ютерного подання графа списками суміжності. Для цього використовують масив Аdj із списків -- по одному на кожну вершину. Для кожної вершини u є V список Adj[u] містить у довільному порядку покажчики на всі вершини множини Г(u).

Приклад 1.7. На рис. 1.6 зображено неорієнтований граф з рис. 1.4.1 за допомогою списків суміжності. Аналогічне зображення для орієнтованого графа з рис. 1.4.2 показано на рис. 1.7.

Рис. 1.6

Рис. 1.7

Для орієнтованого графа сума довжин усіх списків суміжних вершин дорівнює загальній кількості дуг: дузі (u, v) відповідає елемент v зі списку Adj[u]. Для неорієнтованого графа ця сума дорівнює подвоєній кількості ребер, бо ребро {u, v} породжує елемент у списку суміжних вершин як для вершини u, так і для вершини v[3, с.95--100].

1.3 Зв'язність графів і компоненти зв'язності

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

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

Рис. 1. 8 Рис. 1. 9

На рис. 1.8 та 1.9 зображено два графи. Граф на рис. 1.8 зв'язний, тому що для сполучення будь-яких його ребер існує маршрут. Натомість, на рис. 1.9 зображено незв'язний граф, тому що не існує шляху, який би сполучив вершини x, y, z з вершинами u, v, w.

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

Орграф називається слабо зв'язним, якщо асоційований із ним граф - зв'язний.

Компонентою зв'язності графа G називають зв'язний підграф, який не є власним підграфом довільного іншого зв'язного підграфа графа G.

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

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

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

Нехай дано граф G=(V, U). На множині його вершин означимо відношення досяжності d за правилом: дві довільні вершини V_j, V_i графа G перебувають у відношенні досяжності d тоді й тільки тоді, коли вони збігаються або існує маршрут, який їх з'єднує.

Матрицею зв'язності неорієнтованого графа G=(V, U), який має n вершин, називається матриця розмірності nЧn, елементи якої обчислюються за правилом: a_ij=

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

Довільні вершини V_j, V_i орграфа G перебувають у відношенні односторонньої досяжності d₁ тоді й тільки тоді, коли вони збігаються або існує маршрут із вершини V_j у вершину V_i.

Довільні вершини V_j, V_i орграфа G перебувають у відношенні двосторонньої досяжності d₂ тоді й тільки тоді, коли вони збігаються або існує маршрут із вершини V_j у вершину V_i та навпвкт.

Для орграфів вводиться дві матриці зв'язності.

Матрицею сильної зв'язності орієнтованого графа G(V, U), який має n вершин, називається матриця розмірності nЧn, елементи якої обчислюються за правилом:

1, якщо вершина А_j досяжна з А_і і, навпаки;

0 у протилежному випадку

Така матриця не є симетричною.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 Ейлерові цикли у графі

Цикл, який містить усі ребра графа, називається ейлеровим циклом. Зв'язний граф, який має ейлерів цикл, називається ейлеровим графом.

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

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

Достатність. Припустимо, що степені всіх вершин графа G =(V,E ) парні. Візьмемо деяку вершину v₁V і розпочнемо з неї обхід графа, кожен раз обираючи ребро, яке раніше не використовувалось. Оскільки степінь кожної вершини парний і ненульовий, то цей шлях може закінчитися тільки у вершині v₁, утворивши таким чином цикл Z₁. Якщо в результаті описаного процесу використано всі ребра графа G, то шуканий ейлерів цикл побудовано. Якщо ж Z₁ містить не всі ребра графа G, то вилучимо з G всі ребра, які входять у Z₁. Одержимо граф G₁ підграф графа G, всі вершини якого також матимуть парні степені (це випливає з того, що і G, i Z₁ мають вершини тільки парних степенів). Крім того, внаслідок зв'язності графа G Z₁ i G₁ мають принаймні одну спільну вершину v₂. Відтак, починаючи з вершини v₂, побудуємо цикл Z₂ у графі G₁. Позначимо через Z₁ частину циклу Z₁ від v₁ до v₂, а через Z₁ частину циклу Z₁ від v₂ до v₁. Отримаємо новий цикл Z₁, Z₂, Z₁, що веде з v₁ у v₁. Якщо цей цикл ейлерів процес завершився. У противному разі продовжуємо аналогічні побудови ще раз і т.д. Цей процес завершиться побудовою шуканого ейлерового циклу.

Оскільки для графа G з рис.3.11,б умови теореми Ейлера не виконуються, то в задачі про кенігсберзькі мости відповідь негативна.

Теорема 2.2 Для того, щоб скінченний орграф мав ейлеровий цикл необхідно і достатньо, щоб степені входу і виходу кожної вершини були рівні [1, с.154 -- 155].

2.3 Ейлерові ланцюги у графі

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

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

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

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

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

Можливі два випадки:

1) Вершини А та В сполучені ребром.

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

2) Вершини А та В не сполучені ребром.

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

Теорема 2.4. На довільному зв'язному графі з 2k непарними вершинами існує сім'я з k ланцюгів, які в сукупності містять усі ребра графа рівно по одному разу [4, с. 114--115].

2.4 Алгоритм Флері побудови ейлерового циклу

1. Починаємо з довільної вершини u та присвоюємо довільному ребру {u, b} номер 1. Викреслюємо ребро {u, b} й переходимо у вершину v.

2. Нехай v - вершина, у яку ми перейшли на попередньому кроці, k-останній присвоєний номер. Вибираємо довільне ребро, інцидентне вершині v, причому міст вибираємо лише тоді, коли немає інших можливостей. Присвоюємо вибраному ребру номер (k+1) і викреслюємо його.

3. Якщо всі ребра графа викреслено та пронумеровано - ці номери задають послідовність ребер в ейлеревому циклі. В іншому випадку перейти на крок 2 [1, с.160].

Висновки

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

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

Результати наведено дослідження дають підставу зробити такі висновки:

У даній роботі було розглянуто основні означення теорії графів в цілому і означення ейлерових графів як частини великої теорії графів. У першому розділі ввели способи подання графів, розглянули зв'язність графів. Було доведено теорему Ейлера про існування циклічного маршруту у зв'язному графі. У другому розділі обгрунтовано алгоритм Флері побудови ейлерового циклу.

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

Список використаних джерел

1. Андрійчук В.І., Комарницький М.Я., Іщук Ю. Б. Вступ до дискретної математики: Навчальний посібник. Київ: Центр навчальної літератури, 2004. 254 с.

2. Дискретна математика: Підручник / Ю. М. Бардачов, Н. А. Соколова, В. Є. Ходаков; За ред. В. Є. Ходакова. К.: Вища шк., 2007. 383 с.: іл.

3. Нікольський Ю. В., Пасічник В. В., Щербина Ю. М. Дискретна математика. К.: Видавнича група DHV, 2007. 368 с.

4. Швай О. Л. Практикум з дискретної математики. Луцьк: ВНУ, 2011. 236 с.

Додатки

Додаток А

Біографія Ейлера

Ейлер вважається найвидатнішим математиком 18-го століття Ейлер народився 15 квітня 1707 р. в м Базель, в Швейцарії. Незабаром після народження сина, родина переїжджає в містечко Рієн. Батько хлопчика був другом Йоганна Бернуллі -- відомого європейського математика, що зробив великий вплив на Леонарда. У тринадцять років Ейлер-молодший вступає до Базельського університету, і в 1723 р отримує ступінь магістра філософії. У своїй дисертації Ейлер порівнює філософії Ньютона і Декарта. Йоганн Бернуллі, що давав хлопчикові по суботах приватні уроки, швидко розпізнає видатні здібності хлопчика до математики і переконує його залишити ранню теологію і зосередитися на математиці.

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

17 травня 1727 р. Ейлер надходить на службу до медичного відділення Імператорської російської академії наук в Санкт -- Петербурзі, але майже відразу ж переходить на математичний факультет. Однак через заворушення в Росії, 19 червня 1741 р Ейлер переводиться в Берлінську академію. Там учений прослужить близько 25 років, написавши за цей час понад 380 наукових статей. У 1755 р. його обирають іноземним членом Шведської королівської академії наук.

На початку 1760-х рр. Ейлеру надходить пропозиція навчати наукам принцесу Ангальт-Дессау, якій вчений напише більше 200 листів, які увійшли популярний збірник «Листи Ейлера на різні предмети натуральної філософії, адресовані німецькій принцесі». Книга не тільки наочно демонструє здатності вченого міркувати на всілякі теми в області математики і фізики, але також є виразом його особистих і релігійних поглядів. Цікаво те, що ця книга відома краще, ніж всі його математичні праці. Причиною такої популярності цих листів стала дивовижна здатність Ейлера в доступній формі доносити наукові відомості до простого обивателя.

Унікальність цієї праці полягала ще й в тому, що в 1735 р. учений майже повністю осліп на праве око, а в 1766 р. ліве око було вражене катарактою. Але, навіть не дивлячись на це, він продовжує свої роботи і в 1755 р. пише в середньому по одній математичній статті в тиждень.

У 1766 р. Ейлер приймає пропозицію повернутися в Петербурзьку академію, і решту свого життя проведе в Росії. Однак його другий приїзд в цю країну виявляється для нього не таким вдалим: в 1771 р. пожежа знищує його будинок, а, слідом за цим, в 1773 році він втрачає свою дружину Катарину.

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

Особисте життя 7 січня 1734 р. Ейлер одружується на Катаріні Газель. У 1773 р, після 40 років сімейного життя, Катаріна вмирає. Через три роки, Ейлер одружується на її зведеній сестрі, Саломі Абігейл Гзель, з якою і проведе залишок життя. На згадку про його величезний внесок у науку, портрет Ейлера з'явився на швейцарських 10 -- франкових банкнотах шостої серії, а також на ряді російських, швейцарських і німецьких марок.

Додаток Б

Задачі з теорії ейлерових графів

Задача №1

Визначити, які з графів мають ейлеровий цикл. Зобразити його.

Скористаємося теоремою 2.1. 19.

Розглянемо граф G. Вершини V₃ і V₄ мають непарний степінь. Отже граф G не має ейлеревого циклу.

Розглянемо граф H₁. Вершини V₁, V₂, V₄, V₅ мають парний степінь. Отже граф Н₁ має ейлеревого циклу.

Розглянемо граф H₂. Вершини V₂, V₄ мають непарний степінь. Отже граф Н₂ не має ейлеревого циклу.

Розглянемо граф H₃. Вершини V₃, V₅ мають непарний степінь. Отже граф Н₃ не має ейлеревого циклу.

Для зображення ейлеревого циклу скористаємося алгоритмом Флері.

Отримаємо один із можливих ейлеревих циклів: V₁, V₂, V₅, V₄, V₁.

Відповідь: ейлерів цикл має лише граф Н₁.

Задача №2

Довести, що граф, який відповідає ходам коня на шаховій дошці, не є ейлеровим.

Розв'язання

Зобразимо граф, який відповідає шаховій дошці 8Ч8.

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

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