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

В ньому

.Викресливши два ребра, отримаємо граф . Викреслити далі яке-небудь ребро, не порушуючи зв язності, вже не можна (див.рис.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..