Гамильтонов граф
Материал из Википедии — свободной энциклопедии
Гамильтонов граф — в теории графов это граф, содержащий гамильтонову цепь или гамильтонов цикл.
Гамильтонов путь (или гамильтонова цепь) — путь (цепь), содержащий каждую вершину графа ровно один раз. Гамильтонов путь, начальная и конечная вершины которого совпадают, называется гамильтоновым циклом. Гамильтонов цикл является простым остовным циклом (см. Словарь терминов теории графов).
Гамильтоновы путь, цикл и граф названы в честь ирландского математика У. Гамильтона, который впервые определил эти классы, исследовав задачу «кругосветного путешествия» по додекаэдру, узловые вершины которого символизировали крупнейшие города Земли, а рёбра — соединяющие их дороги.
Содержание |
[править] Условия существования
[править] Условие Дирака (англ.) (1952)
Пусть p — число вершин в данном графе; если степень каждой вершины не меньше, чем 
, то граф называется графом Дирака. Граф Дирака — гамильтонов.
[править] Условие Оре (1960)
p — количество вершин в данном графе. Если для любой пары несмежных вершин x,y выполнено неравенство 
, то граф называвается графом Оре (словами: степени любых двух несмежных вершин не меньше общего числа вершин в графе). Граф Оре — гамильтонов.
Доказана теорема Бонди-Хватала (англ.), обобщающая утверждения Дирака и Оре. Вначале определим замыкание графа. Пусть у графа G n вершин. Тогда замыкание cl(G) однозначно строится по G добавлением для всех несмежных вершин u и v, у которых выполняется degree(v) + degree(u) ≥ n нового ребра uv.
|
Граф является гамильтоновым тогда и только тогда, когда его замыкание — гамильтонов граф. |
[править] Условие Поша
Введем следующую функцию f(x) целого неотрицательного аргумента x на графе G = [A,B]:
.
Написанное означает, что функция f(x) в каждом целом неотрицательном x принимает значение, равное количеству вершин графа G = [A,B], степень которых не превосходит x. Такую функцию f(x) называют функцией Поша графа G.
[править] См. также
[править] Ссылки
- Weisstein, Eric W. Hamiltonian Circuit на сайте Wolfram MathWorld.(англ.)
- Теория графов и комбинаторика
- Эйлеровы и Гамильтоновы графы
Методы решения Гамильтоновых графов:
