12-10-2023
Гамильтонов граф — в теории графов это граф, содержащий гамильтонову цепь или гамильтонов цикл.
Гамильтонов путь (или гамильтонова цепь) — путь (цепь), содержащий каждую вершину графа ровно один раз. Гамильтонов путь, начальная и конечная вершины которого совпадают, называется гамильтоновым циклом. Гамильтонов цикл является простым остовным циклом (см. Словарь терминов теории графов).
Гамильтоновы путь, цикл и граф названы в честь ирландского математика У. Гамильтона, который впервые определил эти классы, исследовав задачу «кругосветного путешествия» по додекаэдру, узловые вершины которого символизировали крупнейшие города Земли, а рёбра — соединяющие их дороги.
Содержание |
Пусть — число вершин в данном графе; если степень каждой вершины не меньше, чем , то граф называется графом Дирака. Граф Дирака — гамильтонов.
— количество вершин в данном графе. Если для любой пары несмежных вершин выполнено неравенство , то граф называется графом Оре (словами: степени любых двух несмежных вершин не меньше общего числа вершин в графе). Граф Оре — гамильтонов.
Теорема Бонди-Хватала (англ.) обобщает утверждения Дирака и Оре. Для графа G с n вершинами замыкание определяется добавлением в G ребра (u,v) для каждой пары несмежных вершин u и v, сумма степеней которых не меньше n.
|
Граф является гамильтоновым тогда и только тогда, когда его замыкание — гамильтонов граф. |
Введем следующую функцию целого неотрицательного аргумента на графе :
Написанное означает, что функция в каждом целом неотрицательном принимает значение, равное количеству вершин графа , степень которых не превосходит . Такую функцию называют функцией Поша графа .
Гамильтонов цикл.
