Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Гамильтонов граф



План:


Введення

Граф Додекаедр з виділеним циклом Гамільтона
Гамильтонов шлях (чорним)

Гамильтонов граф - в теорії графів це граф, що містить гамильтонова ланцюг або гамільтонів цикл.

Гамильтонов шлях (або гамильтонова ланцюг) - шлях ( ланцюг), що містить кожну вершину графа рівно один раз. Гамильтонов шлях, початкова та кінцева вершини якого збігаються, називається Гамільтона циклом. Гамильтонов цикл є простим Остовним циклом (див. Словник термінів теорії графів).

Гамильтонова шлях, цикл і граф названі на честь ірландського математика У. Гамільтона, який вперше визначив ці класи, дослідивши завдання "кругосвітньої подорожі" по додекаедр, вузлові вершини якого символізували найбільші міста Землі, а ребра - з'єднують їх дороги.


1. Умови існування

1.1. Необхідна умова

Якщо неорієнтований граф G містить гамільтонів цикл, тоді в ньому не існує ні однієї вершини x (i) з локальної ступенем p (x (i)) <2. Доказ випливає з визначення.

1.2. Умова Дірака (англ.) (1952)

Нехай p - Число вершин у даному графі; якщо ступінь кожної вершини не менше, ніж \ Frac {p} {2} , То граф називається графом Дірака. Граф Дірака - гамільтонів.

1.3. Умова Оре (1960)

Нехай p - Кількість вершин в даному графі. Якщо для будь-якої пари несуміжних вершин x, y виконано нерівність d (x) + d (y) \ geqslant p , То граф називається графом Оре (словами: ступеня будь-яких двох несуміжних вершин не менше загального числа вершин у графі). Граф Оре - гамільтонів.

1.4. Теорема Бонді-хапала

Теорема Бонді-вистачає (англ.) узагальнює затвердження Дірака і Оре. Для графа G з n вершинами замикання визначається додаванням в G ребра (u, v) для кожної пари несуміжних вершин u і v, сума ступенів яких не менше n.

Граф є Гамільтона тоді і тільки тоді, коли його замикання - гамільтонів граф.



1.5. Умова Пошана

Введемо наступну функцію f (x) цілого невід'ємне аргументу x на графі G = [A, B] :

f (x) = \ left | \ left \ {a \ in A | d (a) \ le x \ right \} \ right | .

Написане означає, що функція f (x) в кожному цілому невід'ємне x приймає значення, яке дорівнює кількості вершин графа G = [A, B] , Ступінь яких не перевершує x . Таку функцію f (x) називають функцією Пошана графа G .


Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Граф
Граф Нулін
Граф Петерсена
Граф, Девід
Граф, Штеффі
Граф Монтенегро
Граф алгоритму
Граф Ессекс
Граф Лестер
© Усі права захищені
написати до нас
Рейтинг@Mail.ru