Турниры — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Турнир)
Строка 13: Строка 13:
 
|definition = Турнир называется гамильтоновым, если он содержит гамильтонов цикл.
 
|definition = Турнир называется гамильтоновым, если он содержит гамильтонов цикл.
 
}}
 
}}
 +
 +
По [[Теорема Редеи-Камиона| теореме Редеи-Камиона]] турнир является гамильтоновым тогда и только тогда, когда он сильно связанный.

Версия 01:01, 14 октября 2010

Турнир

Определение:
Турниром называется ориентированный граф, у любой пары вершин которого есть ровно одно ориентированное ребро


Сильный турнир

Определение:
Турнир [math]T[/math] называется сильно связанным, если для любых вершин [math]u,v \in T [/math] существует путь из [math]u[/math] в [math]v[/math].


Гамильтонов турнир

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


По теореме Редеи-Камиона турнир является гамильтоновым тогда и только тогда, когда он сильно связанный.