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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
[[Файл:тур.png|thumb|right|турниры из 2, 3 и 4 вершин]]
 
[[Файл:тур.png|thumb|right|турниры из 2, 3 и 4 вершин]]
{{Определение
+
'''Турнир''' — [[ориентированный граф]], между любой парой вершин которого есть ровно одно ориентированное ребро.
|definition = Турниром называется [[ориентированный граф]], между любой парой вершин которого есть ровно одно ориентированное ребро
+
 
}}
 
 
Название этого класса графов связано с тем, что их удобно использовать для описания результатов командных соревнований в некоторых видах спорта.
 
Название этого класса графов связано с тем, что их удобно использовать для описания результатов командных соревнований в некоторых видах спорта.
  
Строка 9: Строка 8:
 
}}
 
}}
  
[[Файл:тур.png|thumb|right|Негамильтонов турнир]]
+
[[Файл:негам.png|thumb|right|Негамильтонов турнир]]
Не все турниры гамильтоновы: определение не исключает существование вершины с полустепенью исхода или захода равной нулю: в первую нельзя войти, а из второй — выйти. Однако отсутствие таких вершин не означает, что турнир гамильтонов (пример — на рисунке справа).
+
Не все турниры гамильтоновы. Определение не исключает существование вершины с полустепенью исхода или захода равной нулю: в первую нельзя войти, а из второй — выйти. Однако отсутствие таких вершин не означает, что турнир гамильтонов (пример — на рисунке справа).
  
 
По [[Теорема Редеи-Камиона| теореме Редеи-Камиона]] турнир является сильно связанным тогда и только тогда, когда он гамильтонов.
 
По [[Теорема Редеи-Камиона| теореме Редеи-Камиона]] турнир является сильно связанным тогда и только тогда, когда он гамильтонов.

Версия 05:12, 6 декабря 2011

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

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

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


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


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

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

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