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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 3: Строка 3:
 
}}  
 
}}  
  
Название этого класса графов связано с тем, что их удобно использовать для описания результатов командных соревнований в некоторых видах спорта.
+
Имя турнир исходит из графической интерпретации исходов кругового турнира, в котором каждый игрок встречается в схватке с каждым другим игроком ровно раз, и в котором не может быть ничьих. В орграфе турнира вершины соответствуют игрокам. Дуга между каждой парой игроков ориентирована от выигравшего к проигравшему. Если игрок <tex>a</tex> побеждает игрока <tex>b</tex>, то говорят, что <tex>a</tex> доминирует над <tex>b</tex>.
  
 
[[Файл:Tournament_1_3.png|415px|thumb|left|Турниры из трех вершин]]
 
[[Файл:Tournament_1_3.png|415px|thumb|left|Турниры из трех вершин]]
Строка 11: Строка 11:
 
==Оценка количества турниров в графе==
 
==Оценка количества турниров в графе==
 
Если в турнире опустить ориентацию ребер, то мы получим полный граф. А так как существует два варианта ориентации каждого ребра, то количество турниров в графе из <tex>n</tex> вершин равно <tex dpi=150>2^{\frac{n\cdot(n-1)}{2}}</tex>.
 
Если в турнире опустить ориентацию ребер, то мы получим полный граф. А так как существует два варианта ориентации каждого ребра, то количество турниров в графе из <tex>n</tex> вершин равно <tex dpi=150>2^{\frac{n\cdot(n-1)}{2}}</tex>.
 +
==Транзитивность==
 +
 +
[[Файл:Tournament_transitive.png|300px|thumb|right|Транзитивный турнир с 8 вершинами]]
 +
Турнир, в котором <tex>((a \rightarrow b)\&(b \rightarrow c)) \Rightarrow (a \rightarrow c)</tex>, называется транзитивным. В транзитивном турнире вершины могут быть полностью упорядочены в порядке достижимости.
 +
 +
Следующие утверждения для турнира с n вершинами эквивалентны:
 +
*<tex>T</tex> транзитивен.
 +
*<tex>T</tex> ацикличен.
 +
*<tex>T</tex> не содержит циклов длины 3.
 +
*Последовательность числа выигрышей (множество полуисходов) <tex>T</tex> есть <tex> 0, 1, 2,..., n - 1 </tex>.
 +
*<tex>T</tex> содержит ровно один гамильтонов путь.
 +
<br clear="all">
 +
 +
==Парадоксальные турниры==
 +
Игрок, выигравший все игры, естественно, будет победителем турнира. Однако, как показывает существование нетранзитивных турниров, такого игрока может не оказаться. Турнир, в котором каждый игрок проигрывает хотя бы одну игру называется 1-парадоксальным турниром. Обобщая, Турнир <tex>T=(V,E)</tex> называется <tex>k</tex>-парадоксальным, если для любого <tex>k</tex>-элементного подмножества <tex>S</tex> множества <tex>V</tex> существует вершина <tex>v_0</tex> в <tex>V\setminus S</tex>, такая что <tex>v_0 \rightarrow v</tex> для всех <tex>v \in S</tex>.
 +
 +
==Конденсация==
 +
Конденсация любого турнира является транзитивным турниром. Таким образом, даже если турнир не является транзитивным, сильно связанные компоненты турнира могут быть полностью упорядочены.
 
==Сильно связные турниры==
 
==Сильно связные турниры==
 
{{Определение|definition = Турнир называется [[Отношение связности, компоненты связности#sc_def |сильно связным]], если из любой вершины существуют пути до всех других.}}
 
{{Определение|definition = Турнир называется [[Отношение связности, компоненты связности#sc_def |сильно связным]], если из любой вершины существуют пути до всех других.}}
Строка 21: Строка 39:
  
  
Не все турниры гамильтоновы. Определение не исключает существование вершины с полустепенью исхода или захода равной нулю — в первую нельзя войти, а из второй — выйти. Однако отсутствие таких вершин не означает, что турнир гамильтонов (пример — на рисунке справа).
+
Не все турниры гамильтоновы. Определение не исключает существование вершины с <tex>deg^{-}</tex> или <tex>deg^{+}</tex> равной нулю — в первую нельзя войти, а из второй — выйти. Однако отсутствие таких вершин не означает, что турнир гамильтонов (пример — на рисунке справа).
  
 
[[Теорема Редеи-Камиона]] устанавливает 2 следующих факта:
 
[[Теорема Редеи-Камиона]] устанавливает 2 следующих факта:

Версия 21:17, 7 ноября 2015

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


Имя турнир исходит из графической интерпретации исходов кругового турнира, в котором каждый игрок встречается в схватке с каждым другим игроком ровно раз, и в котором не может быть ничьих. В орграфе турнира вершины соответствуют игрокам. Дуга между каждой парой игроков ориентирована от выигравшего к проигравшему. Если игрок [math]a[/math] побеждает игрока [math]b[/math], то говорят, что [math]a[/math] доминирует над [math]b[/math].

Турниры из трех вершин


Оценка количества турниров в графе

Если в турнире опустить ориентацию ребер, то мы получим полный граф. А так как существует два варианта ориентации каждого ребра, то количество турниров в графе из [math]n[/math] вершин равно [math]2^{\frac{n\cdot(n-1)}{2}}[/math].

Транзитивность

Транзитивный турнир с 8 вершинами

Турнир, в котором [math]((a \rightarrow b)\&(b \rightarrow c)) \Rightarrow (a \rightarrow c)[/math], называется транзитивным. В транзитивном турнире вершины могут быть полностью упорядочены в порядке достижимости.

Следующие утверждения для турнира с n вершинами эквивалентны:

  • [math]T[/math] транзитивен.
  • [math]T[/math] ацикличен.
  • [math]T[/math] не содержит циклов длины 3.
  • Последовательность числа выигрышей (множество полуисходов) [math]T[/math] есть [math] 0, 1, 2,..., n - 1 [/math].
  • [math]T[/math] содержит ровно один гамильтонов путь.


Парадоксальные турниры

Игрок, выигравший все игры, естественно, будет победителем турнира. Однако, как показывает существование нетранзитивных турниров, такого игрока может не оказаться. Турнир, в котором каждый игрок проигрывает хотя бы одну игру называется 1-парадоксальным турниром. Обобщая, Турнир [math]T=(V,E)[/math] называется [math]k[/math]-парадоксальным, если для любого [math]k[/math]-элементного подмножества [math]S[/math] множества [math]V[/math] существует вершина [math]v_0[/math] в [math]V\setminus S[/math], такая что [math]v_0 \rightarrow v[/math] для всех [math]v \in S[/math].

Конденсация

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

Сильно связные турниры

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


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


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


Не все турниры гамильтоновы. Определение не исключает существование вершины с [math]deg^{-}[/math] или [math]deg^{+}[/math] равной нулю — в первую нельзя войти, а из второй — выйти. Однако отсутствие таких вершин не означает, что турнир гамильтонов (пример — на рисунке справа).

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

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


См. также

Источники информации

  • Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы — НИЦ РХД, 2001. — ISBN 5-93972-076-5