4
правки
Изменения
Нет описания правки
==Гамильтонов графОсновные определения==
{{Определение
|definition =
'''Гамильтоновым графом ''' называют [[Основные определения теории графов|граф]], содержащий гамильтонов путь.
}}
{{Определение
|definition =
'''Гамильтоновым путём ''' называют [[Основные определения теории графов|путь]], приходящий в каждую вершину один раз.
}}
{{Определение
|definition =
'''Гамильтоновым циклом ''' называют гамильтонов путь, являющийся [[Основные определения теории графов|циклом]].
}}
[[Файл:Hamiltonian_Dodecahedron_Graph.png|250px|thumb|right|Граф додекаэдра с выделенным циклом Гамильтона]]
==Свойства==
*Поиск гамильтонова пути в [[Основные определения теории графов|графе]] - [[Понятие NP-трудной и NP-полной задачи|NP-полная задача]].
*Число различных гамильтоновых циклов в полном графе:
**Неорентированном: <math>(n-1)! / 2</math>.
**Ориентированном: <math>(n-1)!</math>.
==Релевантные теоремы==
*[[Теорема_Хватала|Теорема Хватала]]
*[[Теорема_Дирака|Теорема Дирака]]
*[[Теорема_Оре|Теорема Оре]]
*[[Теорема_Редеи-Камиона|Теорема Редеи-Камиона]]
==Примеры==
*Полный граф более чем из двух вершин.
*Любой [[Турниры|турнир]].
