Турниры — различия между версиями
| Строка 4: | Строка 4: | ||
Название этого класса графов связано с тем, что их удобно использовать для описания результатов командных соревнований в некоторых видах спорта. | Название этого класса графов связано с тем, что их удобно использовать для описания результатов командных соревнований в некоторых видах спорта. | ||
| + | ==Гамильтоновы турниры== | ||
{{Определение | {{Определение | ||
|definition = Турнир называется гамильтоновым, если он содержит гамильтонов цикл. | |definition = Турнир называется гамильтоновым, если он содержит гамильтонов цикл. | ||
| Строка 11: | Строка 12: | ||
Не все турниры гамильтоновы. Определение не исключает существование вершины с полустепенью исхода или захода равной нулю: в первую нельзя войти, а из второй — выйти. Однако отсутствие таких вершин не означает, что турнир гамильтонов (пример — на рисунке справа). | Не все турниры гамильтоновы. Определение не исключает существование вершины с полустепенью исхода или захода равной нулю: в первую нельзя войти, а из второй — выйти. Однако отсутствие таких вершин не означает, что турнир гамильтонов (пример — на рисунке справа). | ||
| − | + | [[Теорема Редеи-Камиона]] устанавливает 2 следующих факта: | |
| + | # Все турниры полугамильтоновы (содержат остовную цепочку). | ||
| + | # Турнир гамильтонов тогда и только тогда, когда он сильно связен. | ||
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Обходы графов]] | [[Категория: Обходы графов]] | ||
Версия 05:21, 6 декабря 2011
Турнир — ориентированный граф, между любой парой вершин которого есть ровно одно ориентированное ребро.
Название этого класса графов связано с тем, что их удобно использовать для описания результатов командных соревнований в некоторых видах спорта.
Гамильтоновы турниры
| Определение: |
| Турнир называется гамильтоновым, если он содержит гамильтонов цикл. |
Не все турниры гамильтоновы. Определение не исключает существование вершины с полустепенью исхода или захода равной нулю: в первую нельзя войти, а из второй — выйти. Однако отсутствие таких вершин не означает, что турнир гамильтонов (пример — на рисунке справа).
Теорема Редеи-Камиона устанавливает 2 следующих факта:
- Все турниры полугамильтоновы (содержат остовную цепочку).
- Турнир гамильтонов тогда и только тогда, когда он сильно связен.
