Турниры
Версия от 05:12, 6 декабря 2011; Antipov Den (обсуждение | вклад)
Турнир — ориентированный граф, между любой парой вершин которого есть ровно одно ориентированное ребро.
Название этого класса графов связано с тем, что их удобно использовать для описания результатов командных соревнований в некоторых видах спорта.
| Определение: |
| Турнир называется гамильтоновым, если он содержит гамильтонов цикл. |
Не все турниры гамильтоновы. Определение не исключает существование вершины с полустепенью исхода или захода равной нулю: в первую нельзя войти, а из второй — выйти. Однако отсутствие таких вершин не означает, что турнир гамильтонов (пример — на рисунке справа).
По теореме Редеи-Камиона турнир является сильно связанным тогда и только тогда, когда он гамильтонов.
