Рис. 1.19. Орієнтований 3-х вершинний граф
Теорема 1.4. Число всіх орієнтованих графів з вершинами дорівнює.
Доказ. Дійсно, число впорядкованих пар елементів з дорівнює, тому число всіх можливих множин дуг дорівнює. Теорема доведена.
Визначення 1.13.
Нехай -безліч вершин. Орієнтованим графом з петлями будемо називати пару множин, де (див. Ріс.1.20).
Ріс.1.20. Орієнтований граф з петлями
Теорема 1.5. Число орієнтованих графів з петлями, які мають вершин, дорівнює.
Доказ. Дійсно, число різних множин (підмножин множини) одно. Теорема доведена.
Якщо розглядається одночасно кілька типів графів, то графи описуваних визначення (1.1), будемо називати простими графами.
Якщо у визначенні (1.1) до безлічі невпорядкованих пар приєднати ще безліч всіх пар виду, то відповідний граф називається простим графом з петлями.
З теореми 1.5 випливає висновок для теореми 1.6 про прості графах.
Теорема 1.6. Число всіх простих графів з вершинами і петлями дорівнює
Надалі, ми будемо розглядати прості графи.
РОЗДІЛ ІІ ейлеровимі ГРАФИ
2.1 Ейлерова Головоломка «Кенігзберзькіх мостів»
Для вирішення серйозних математичних задач математик Ейлер (Euler) використовував наочні головоломки. Одна з них поклала початок абсолютно новій галузі досліджень, виросла згодом у самостійний розділ математики - теорію графів і топології. Особливість цієї теорії - в геометричному підході до вивчення об'єктів.
Теорія графів - одна з небагатьох математичних дисциплін, дата народження якої може бути встановлена ??абсолютно точно.
Перша робота з теорії графів належить Леонарда Ейлера. Вона з'явилася в публікаціях Санкт-Петербургзськоі Академії наук в 1736 році.
Праця Ейлера починалася з розгляду однієї головоломки так званої задачі про кенігзберзькіх мостах .
Місто Кенігзберг (нині Калінінград) розташований на берегах річки Прегель і двох островах. Різні частини міста з'єднані сім'ю мостами. Щотижня жителі міста любили здійснювати прогулянки по місту. Ейлер поставив питання: можна зробити прогулянку, вийшовши з дому і повернувшись до нього, таку, щоб по кожному мосту пройти рівно один раз.
Сформулюємо задачу, як задачу теорії графів. Схематична карта міста зображена на малюнку 2.1.
Чотири частини міста зображені літерами Оскільки нас інтересують лише переходи через мости, ми можемо вважати вершинами графа, ребра якого відповідають мостам. Цей граф зображено на малюнку 2.2.
Рис. 2.1. Схема мостів у Кенігзберзі
Рис. 2.2 Граф «Кенігзберзькіх мостів»
Ейлер зазначив, що цей граф не має єдиного циклу, з якою б вершини ми не стали б обхід, ми не можемо обійти весь граф і повернутися назад, не проходячи кожне ребро двічі. Якби такий цикл існував, то з кожної вершини виходило б стільки ребер, скільки в неї входить, інакше кажучи ступінь кожної вершини була б парним числом. Таким чином, відповідь на питання Ейлера негативний.
Виклавши рішення задачі про кенігзберзькіх мостах, Ейлер у своїй роботі поставив питання: на яких графах можна знайти цикл, що містить всі ребра графа, причому кожне ребро зустрічається в циклі рівно один раз?
Це дало початок системному математичному підходу до побудови та вивчення властивості графів.
2.2 Основні поняття та визначення ейлеровимі графів
Визначення 2.1.
Зв'язаний граф називається ейлеровимі графом, якщо існує замкнута ланцюг, який проходить через кожне ребро.
Таку ланцюг будемо називати ейлеровимі ланцюгом, або ейлеровскім циклом (див. рис.2.3)
Рис.2.3 Структура вершин і ребер в неорієнтованому ейлеровом графі
Визначення 2.2
Граф називається полуейлеровім, якщо існує ланцюг, яка проходить через кожне його ребро рівно один раз (див. рис.2.4).
Рис.2.4 Структура вершин і ребер в неорієнтованому полуейлерованном графі
Рис.2.5 Приклад неейлерового графа
Дослідивши структуру неейлерового графа, наведеному на рис.2.5, розглянемо необхідні і достатні умови для того, щоб граф був ейлеровимі. Доведемо лему, яка далі буде відігравати суттєву роль.
Лемма 2.1
Якщо ступінь кожної вершини графа не менше двох, то граф містить цикл.
Доказ. Якщо в графі є петлі або кратні дуги, то...
