Турниры — различия между версиями
(→Турнир) |
Kirillova (обсуждение | вклад) |
||
| Строка 13: | Строка 13: | ||
|definition = Турнир называется гамильтоновым, если он содержит гамильтонов цикл. | |definition = Турнир называется гамильтоновым, если он содержит гамильтонов цикл. | ||
}} | }} | ||
| + | |||
| + | По [[Теорема Редеи-Камиона| теореме Редеи-Камиона]] турнир является гамильтоновым тогда и только тогда, когда он сильно связанный. | ||
Версия 01:01, 14 октября 2010
Турнир
| Определение: |
| Турниром называется ориентированный граф, у любой пары вершин которого есть ровно одно ориентированное ребро |
Сильный турнир
| Определение: |
| Турнир называется сильно связанным, если для любых вершин существует путь из в . |
Гамильтонов турнир
| Определение: |
| Турнир называется гамильтоновым, если он содержит гамильтонов цикл. |
По теореме Редеи-Камиона турнир является гамильтоновым тогда и только тогда, когда он сильно связанный.
