рафі G з явився гамільтонів цикл. Покажемо, что припущені k? 1 виробляти до суперечності.
Нехай v, p, w, ..., v - гамільтонів цикл у G ', де v та w < b align = "justify"> - вершини з G, p - одна з новіх вершин. Тоді w несуміжна з v, інакше могли б НЕ використовуват вершину p, что суперечіть мінімальності k. Більше того, вершина w ', суміжна з вершиною w, що не может в гамільтоновому ціклі безпосередно йти за вершиною v', суміжною з v. Дійсно, ЯКЩО є гамільтонів цикл v, p, w, ..., v ', w', ..., v, то Ми можемо замініті его на v, v ', ..., w, w', ..., v, повертаючі Частину циклу, что містіться между w та v ' - це вновь суперечіть мінімальності k.
Отже, кількість вершин графа G ', Які НЕ суміжні з w, не менше від кількості вершин, суміжніх з v (тоб дорівнює прінаймні n 2 + k). Натомість очевидно, что кількість вершин графа G ', суміжніх з w, такоже дорівнює прінаймні n 2 + k. Альо Жодна з вершин графа G "не может одночасно буті суміжною и несуміжною З вершин w, так что загальна кількість вершин графа G 'дорівнює щонайменш n 2 + k. Альо це суперечіть того, что кількість вершин графа G 'дорівнює n + k. p align="justify"> Одержана суперечність доводити теорему.
Теорема 2.2.3 (Оре, 1960 р.). Если у графі G з n вершинами (n? 3) сума степенів будь-яких двох вершин є не менше, чем n, то граф G є гамільтоновім.
Теорема 2.2.4 (В.А. Перепелиця). Майже УСІ повні графи - гамільтонові.
теореми Оре и Дірака є наслідкамі до теореми Пошали.
Ці умови НЕ є необхіднімі.
Як знайти гамільтонів цикл або переконатісь, что его немає? Очевидність алгоритм, Який Можемо застосуваті - це В«повний перебір усіх можливостейВ», тоб n!. Перестановок всех вершин графа и перевірок. Зрозуміло, что такий способ практичного! Застосування НЕ знаходится.
Для таких завдань Невідомий (і є вагомі Підстави вважаті, что его НЕ існує) Ефективний алгоритм їхнього розв язання.
Зв язок между ейлеровімі и гамільтоновімі циклами заданого графа G и відповіднімі циклами так званого реберного графа L (G) встановлюється за помощью ніжченаведеніх тверджень.
множи...
