86405 (612740), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Означення 1.9.

Граф є підграфом графа , якщо

.Якщо , то підграф називається остовним підграфом.

Означення 1.10.

Граф є сумою графів

, якщо

ця сума називається прямою, якщо ,

1.3 Оцінки для числа ребер з компонентами зв ‘язності

Означення 1.11.

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

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

Теорема 1.2.

Кожен граф є прямою сумою зв язних графів.

Доведення. На множині вершин граф визначимо відношення

, якщо сполучається з .Відношення є відношенням еквівалентнос-ті. Позначимо через .Тоді і є розбиття на класи еквівалентності. Графи є зв язними графами і

(1.2)

є прямою сумою зв’язних графів.

Ці графи називаються компонентами зв’язності.

Розглянемо оцінки для числа ребер з компонентами зв’язності.

Теорема 1.3.

Нехай граф, який складається з

вершин, ребер і компонент зв язності. Тоді виконуються нерівності

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

вершин, ребер і

компонентами зв’язності. Викреслимо максимальне можливе число ребер так, щоб не змінювалося число компонент зв’язностя. Число ребер в отриманому графі позначемо .

Розглянемо для прикладу граф, зображений на рисунку (1.15)

Рис. 1.15. Приклад 1 графу для оцінки зв’язності

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

Рис. 1.16. Приклад 1 графу для оцінки зв’язності

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

, маємо , звідки .

Для доведення верхньої оцінки в нерівності (1.3) замінимо кожну компо-ненту повним графом. Нехай та два повних, отриманих з компонент зв’ язності та , а та число ребер в цих компонентах . Замінемо на повний граф, додавши одну вершину, а замінемо на повний граф, віднявши одну вершину. Тоді загальне число вершин не змінеться, а число ребер збільшиться на додатню величину

Отже, для того, щоб число ребер у графі було максимально можливим (при фіксованих

і ), граф повинен складатись з

ізольованих вершин і повного графа з вершинами.Звідси й випливає нерівність (1.3). Теорема доведена.

З нерівності (1.3) випливає такий наслідок.

Наслідок. Будь-який граф з і більше ніж ребрами є зв’язним.

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

Найти компоненти сильної зв’язності графу на рис.1.17.

Відповіді

Рис.1.17. 7-ми вершинний граф для обчислення компонентів зв’язності [10]

1.4 Орієнтовані графи, графи з петлями, графи з паралельними дугами

Дамо означення орієнтованих графів, графів з петлями та графів з пара-лельними дугами.

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

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

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

Рис.1.18. Види орієнтованих графів

Означення 1.12.

Нехай множина вершин , - множина впорядкованих пар елементів з ( будемо називати їх дугами).Орієнтованим графом називатимемо пару множин

, де .

Дуга називається дугою з в (див.рис.1.19).

Рис. 1.19. Орієнтований 3-х вершинний граф ( ,

.)

Теорема 1.4. Число усіх орієнтованих графів з вершинами дорівнює .

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

Означення 1.13.

Нехай -множина вершин. Орієнтованим графом з петлями будемо називати пару множин , де (див.рис.1.20).

Рис.1.20. Орієнтований граф з петлями в якому ,

Теорема 1.5. Число орієнтованих графів з петлями , які мають вершин, дорівнює .

Доведення. Справді, число різних множин (підмножин множини ) дорівнює .

Якщо розглядається одночасно декілька типів графів, то графи які описуються означення (1.1), будемо називати простими графами.

Якщо в означенні (1.1) до множини невпорядкованих пар приєднати ще множину всіх пар виду , то відповідний граф називається простим графом з петлями.

З теореми 1.5 випливає довід теореми 1.6 про прості графи.

Теорема 6. Число всіх простих графів з вершинами і петлями дорівнює

Надалі, ми будемо розглядати прості графи.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 Основні поняття та означення ойлерових графів

Означення 2.1

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

Рис.2.3. Структура вершин та ребер в неорієнтованому ойлеровому графі (* - означено точку входу ойлерового ланцюга - циклу)

Означення 2.2

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

Рис.2.4. Структура вершин та ребер в неорієнтованому напівойлеровому графі (* - означено точку початку та кінця ойлерового ланцюгу)

Рис.2.5. Приклад неойлерового графу

Дослідивши структуру неойлерового графу, наведеного на рис.2.5, розг-лянемо необхідні і достатні умови для того, щоб граф був ойлеровим. Доведемо лему, яка далі буде грати істотну роль.

Лема 2.1

Якщо степінь кожної вершини графа не менше двох , то граф містить цикл.

Доведення. Якщо в графі є петлі або кратні дуги, то твердження леми оче-видне. Тому надалі будемо припускати , що є простим графом. Нехай

Характеристики

Список файлов курсовой работы