Xreferat.com » Рефераты по математике » Основи теорії графів. Властивості ойлерових та гамільтонових графів

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

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

з дисципліни

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

за темою

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

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


ЗМІСТ


ВСТУП

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

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.

Граф Основи теорії графів. Властивості ойлерових та гамільтонових графів називається зв язним , якщо будь-які вершини Основи теорії графів. Властивості ойлерових та гамільтонових графів та Основи теорії графів. Властивості ойлерових та гамільтонових графів Основи теорії графів. Властивості ойлерових та гамільтонових графів сполучені ланцюгом з початком в Основи теорії графів. Властивості ойлерових та гамільтонових графів і кінцем в Основи теорії графів. Властивості ойлерових та гамільтонових графів. З симетрії випливає, що в цьому випадку і вершина Основи теорії графів. Властивості ойлерових та гамільтонових
    <div class=

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: