Гамильтонов граф | это... Что такое Гамильтонов граф? (original) (raw)

Граф додекаэдра с выделенным циклом Гамильтона

Гамильтонов путь (чёрным)

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

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

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

Содержание

Условия существования

Необходимое условие

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

Условие Дирака (англ.) (1952)

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

Условие Оре (1960)

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

Теорема Бонди-Хватала

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

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

Условие Поша

Введем следующую функцию 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.

См. также

Ссылки