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