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

Материал из Викиконспекты
Перейти к: навигация, поиск

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

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


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


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


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

Свойства

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

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

Примеры