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

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

графів" width="19" height="26" align="BOTTOM" border="0" /> сполучена з вершиною Основи теорії графів. Властивості ойлерових та гамільтонових графів.

Теорема 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

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

Доведення. Якщо в графі є петлі або кратні дуги, то твердження леми оче-видне. Тому надалі будемо припускати , що Основи теорії графів.
    <div class=

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

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

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

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