Гамильтоновы графы — различия между версиями
Belan (обсуждение | вклад) |
(→Основные определения) |
||
| Строка 1: | Строка 1: | ||
==Основные определения== | ==Основные определения== | ||
| + | |||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
| − | '''Гамильтоновым | + | '''Гамильтоновым путём''' называют [[Основные определения теории графов|путь]], приходящий в каждую вершину один раз. |
}} | }} | ||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
| − | '''Гамильтоновым | + | '''Гамильтоновым циклом''' называют [[Основные определения теории графов|цикл]], приходящий в каждую вершину графа один раз. |
}} | }} | ||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
| − | '''Гамильтоновым | + | '''Гамильтоновым графом''' называют [[Основные определения теории графов|граф]], содержащий гамильтонов путь. |
}} | }} | ||
| − | |||
[[Файл:Hamiltonian_Dodecahedron_Graph.png|250px|thumb|right|Граф додекаэдра с выделенным циклом Гамильтона]] | [[Файл:Hamiltonian_Dodecahedron_Graph.png|250px|thumb|right|Граф додекаэдра с выделенным циклом Гамильтона]] | ||
Версия 05:55, 19 января 2011
Основные определения
| Определение: |
| Гамильтоновым путём называют путь, приходящий в каждую вершину один раз. |
| Определение: |
| Гамильтоновым циклом называют цикл, приходящий в каждую вершину графа один раз. |
| Определение: |
| Гамильтоновым графом называют граф, содержащий гамильтонов путь. |
Свойства
- Поиск гамильтонова пути в графе - NP-полная задача.
- Число различных гамильтоновых циклов в полном графе:
- Неорентированном: .
- Ориентированном: .
Релевантные теоремы
Примеры
- Любой полный граф.
- Любой турнир.
