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