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

Основные определения

Определение:

Гамильтоновым графом называют граф, содержащий гамильтонов путь.

Определение:

Гамильтоновым путём называют путь, приходящий в каждую вершину один раз.

Определение:

Гамильтоновым циклом называют цикл, приходящий в каждую вершину графа один раз.

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

Свойства

• Поиск гамильтонова пути в графе - NP-полная задача.
• Число различных гамильтоновых циклов в полном графе:
  • Неорентированном: [math](n-1)! / 2[/math].
  • Ориентированном: [math](n-1)![/math].

Релевантные теоремы

• Теорема Хватала
• Теорема Дирака
• Теорема Оре
• Теорема Редеи-Камиона

Примеры

• Любой полный граф.
• Любой турнир.