Турниры

Определение:

Турнир — ориентированный граф, между любой парой различных вершин которого есть ровно одно ориентированное ребро.

Название этого класса графов связано с тем, что их удобно использовать для описания результатов командных соревнований в некоторых видах спорта.

Турниры из 2, 3 и 4 вершин

Сильно связные турниры

Определение:

Турнир называется сильно связным, если из любой вершины существуют пути до всех других.

Определение:

Турнир называется гамильтоновым, если он содержит гамильтонов цикл.

Негамильтонов турнир

Не все турниры гамильтоновы. Определение не исключает существование вершины с полустепенью исхода или захода равной нулю — в первую нельзя войти, а из второй — выйти. Однако отсутствие таких вершин не означает, что турнир гамильтонов (пример — на рисунке справа).

Теорема Редеи-Камиона устанавливает 2 следующих факта:

1. Все турниры полугамильтоновы.
2. Турнир гамильтонов тогда и только тогда, когда он сильно связен.

См. также

• Гамильтоновы графы
• Теорема Редеи-Камиона

Литература

• Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы — НИЦ РХД, 2001. — ISBN 5-93972-076-5