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

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

Версия 01:40, 8 декабря 2011

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

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

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

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

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


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

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

Теорема Редеи-Камиона устанавливает 2 следующих факта:

  1. Все турниры полугамильтоновы (содержат остовную цепочку).
  2. Турнир гамильтонов тогда и только тогда, когда он сильно связен.