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