Основи теорії графів. Властивості ойлерових та гамільтонових графів
Курсовой проект - Математика и статистика
Другие курсовые по предмету Математика и статистика
?овних, отриманих з компонент зв язності та , а та число ребер в цих компонентах . Замінемо на повний граф, додавши одну вершину, а замінемо на повний граф, віднявши одну вершину. Тоді загальне число вершин не змінеться, а число ребер збільшиться на додатню величину
Отже, для того, щоб число ребер у графі було максимально можливим (при фіксованих і ), граф повинен складатись з ізольованих вершин і повного графа з вершинами.Звідси й випливає нерівність (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. Граф Кенігзберзьких мостів в ломи головці Ойлера
Ойлер зауважив, що цей граф не являє єдиного циклу; з якої б вершини ми не почали б обхід , ми не можемо обійти весь граф і повернутись назад, не проходячи жодного ребра двічі. Якби такий цикл існував, то з кожної вершини виходило б стільки ребер , скільки в неї входить , інакше кажучи степінь кожної вершини була б парним числом. Таким чином, відповідь на питання Ойлера-негативна.
Виклавши розв язання задачі про кенігзберзькі мости , Ойлер в своїй праці поставив питання : на яких графах можна знайти цикл, який містить всі ребра графа, при чому кожне ребро зустрічається в цик