РОЗДІЛ ІІІ ГАМІЛЬТОНОВІ ГРАФИ
3.1 Сутність гамільтонових графів
Ейлерові цикли характеризуються властивістю проходити по одному разу через кожне ребро графа, а гамільтонові цикли -- через кожну вершину.
Назва гамільтонів граф виникла у зв язку з тим , що в 1859 році відомий ірландський математик сер Вільям Гамільтон випустив до продажу своєрідну іграшкову головоломку . ЇЇ основою частиною був правильний додекаедр, зроблений з дерева (рис.3.1). Це один з так званих правильних багатогранників: його граням є 12 правильних пятикутників, в кожній з його вершин сходиться три ребра. Кожна з вершин гамільтонового додекаедра була позначена назвою одного з крупних міст Земної кулі -Брюсель, Кантон, Делі, Лондон і так далі. Задача полягає в знаходженні шляху вздовж ребер додекаедра, який проходить через кожне місто в точності один раз. Гамільтонів цикл на додекаедрі не пок-риває, звичайно, всіх ребер додекаедра, бо в кожній вершині він проходить в точності по двох ребрах.
Рис.3.1. Гамільтонів цикл у додекаедрі [4]
- ВСТУП
- РОЗДІЛ І ВВЕДЕННЯ В ТЕОРІЮ ГРАФІВ
- 1.1 Основні поняття та означення
- 1.2 Лема про рукостискання
- 1.3 Оцінки для числа ребер з компонентами зв `язності
- 1.4 Орієнтовані графи, графи з петлями, графи з паралельними дугами
- РОЗДІЛ ІІ ОЙЛЕРОВІ ГРАФИ
- 2.1 Ойлерова ломиголовка «Кенігзберзьких мостів»
- 2.2 Основні поняття та означення ойлерових графів
- 2.3 Приклади ойлерових графів
- РОЗДІЛ ІІІ ГАМІЛЬТОНОВІ ГРАФИ
- 3.2 Основні поняття та означення
- 3.3 Приклади гамільтонових графів
- ВИСНОВКИ