Турниры — различия между версиями
| Строка 18: | Строка 18: | ||
# Турнир гамильтонов тогда и только тогда, когда он сильно связен. | # Турнир гамильтонов тогда и только тогда, когда он сильно связен. | ||
| + | ==См. также== | ||
| + | [[Гамильтоновы графы]] | ||
| + | |||
| + | [[Теорема Редеи-Камиона]] | ||
| + | |||
| + | ==Литература== | ||
| + | * Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — ISBN 5-93972-076-5 | ||
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Обходы графов]] | [[Категория: Обходы графов]] | ||
Версия 22:12, 29 декабря 2011
| Определение: |
| Турнир — ориентированный граф, между любой парой различных вершин которого есть ровно одно ориентированное ребро. |
Название этого класса графов связано с тем, что их удобно использовать для описания результатов командных соревнований в некоторых видах спорта.
Сильно связные турниры
| Определение: |
| Турнир называется сильно связным, если из любой вершины существуют пути до всех других. |
| Определение: |
| Турнир называется гамильтоновым, если он содержит гамильтонов цикл. |
Не все турниры гамильтоновы. Определение не исключает существование вершины с полустепенью исхода или захода равной нулю — в первую нельзя войти, а из второй — выйти. Однако отсутствие таких вершин не означает, что турнир гамильтонов (пример — на рисунке справа).
Теорема Редеи-Камиона устанавливает 2 следующих факта:
- Все турниры полугамильтоновы.
- Турнир гамильтонов тогда и только тогда, когда он сильно связен.
См. также
Литература
- Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы — НИЦ РХД, 2001. — ISBN 5-93972-076-5
