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

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

з дисципліни

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

за темою

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

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

ЗМІСТ

ВСТУП

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

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. Визначення кінцевих та ізольованих вершин графа