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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Граф додекаэдра с выделенным циклом Гамильтона
Гамильтонов путь (чёрным)

Гамильтонов граф — в теории графов это граф, содержащий гамильтонову цепь или гамильтонов цикл.

Гамильтонов путь (или гамильтонова цепь) — путь (цепь), содержащий каждую вершину графа ровно один раз. Гамильтонов путь, начальная и конечная вершины которого совпадают, называется гамильтоновым циклом. Гамильтонов цикл является простым остовным циклом. Задача определения, содержит ли данный граф гамильтонов цикл, является NP-полной.

Гамильтоновы путь, цикл и граф названы в честь ирландского математика У. Гамильтона, который впервые определил эти классы, исследовав задачу «кругосветного путешествия» по додекаэдру, узловые вершины которого символизировали крупнейшие города Земли, а рёбра — соединяющие их дороги.

Условия существования[править | править исходный текст]

Необходимое условие[править | править исходный текст]

Если неориентированный граф G содержит гамильтонов цикл, тогда в нём не существует ни одной вершины x(i) с локальной степенью p(x(i)) < 2. Доказательство следует из определения.

Условие Дирака (англ.) (1952)[править | править исходный текст]

Пусть p — число вершин в данном графе; если степень каждой вершины не меньше, чем \frac{p}{2}, то граф называется графом Дирака. Граф Дирака — гамильтонов.

Условие Оре (1960)[править | править исходный текст]

Пусть p — количество вершин в данном графе. Если для любой пары несмежных вершин (x, y) выполнено неравенство \deg x + \deg y\geqslant p, то граф называется графом Оре (словами: степени любых двух несмежных вершин не меньше общего числа вершин в графе). Граф Оре — гамильтонов.

Теорема Бонди-Хватала[править | править исходный текст]

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

Граф является гамильтоновым тогда и только тогда, когда его замыкание — гамильтонов граф.


Условие Поша[править | править исходный текст]

Функция Поша f(x) целого неотрицательного аргумента x на графе G = (V, E) задаётся формулой:

f(x) = \left| \left\{ v \in V \mid \deg v \leqslant x \right\} \right| .

Другими словами, функция f(x) в каждом целом неотрицательном x принимает значение, равное количеству вершин графа G = (V, E), степень которых не превосходит x.

Алгоритм поиска[править | править исходный текст]

Эвристические оптимизации[править | править исходный текст]

При прямом переборе возможно значительное увеличение средней асимптотической сложности на случайных графах (если гарантируется наличие гамильтонова пути в графе). Для этого можно на каждом шаге перебора при некоторой построенной части цепи проверять, образуют ли оставшиеся вершины связанный граф (если не образуют, то цепь не может являться началом гамильтоновой цепи); на каждом шаге перебора при выборе следующей вершины пробовать сначала вершины с наименьшей остаточной степенью (количество рёбер, ведущих в ещё не посещённые вершины). Кроме того, можно проверять состояние дерева компонент вершинной двусвязности (то есть частей графа, разделённых мостами) - если это дерево является цепью, то гамильтонов цикл в нём возможен. Иначе (если в дереве есть вершины степенью не меньше, чем 3) построение гамильтонова цикла невозможно.

См. также[править | править исходный текст]

Ссылки[править | править исходный текст]