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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 2: Строка 2:
 
|definition = '''Турнир''' (англ. ''Tournament'') — [[ориентированный граф]], между любой парой различных вершин которого есть ровно одно ориентированное ребро.
 
|definition = '''Турнир''' (англ. ''Tournament'') — [[ориентированный граф]], между любой парой различных вершин которого есть ровно одно ориентированное ребро.
 
}}  
 
}}  
−
 
+
Турниром из <tex>n</tex> вершин можно изобразить исход игры между <tex>n</tex> людьми, где каждый играет с каждым. Тогда ребро будет ориентировано от выигравшего человека к проигравшему.
−
Имя турнир исходит из графической интерпретации исходов кругового турнира, в котором каждый игрок встречается в схватке с каждым другим игроком ровно раз, и в котором не может быть ничьих. В орграфе турнира вершины соответствуют игрокам. Дуга между каждой парой игроков ориентирована от выигравшего к проигравшему. Если игрок <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|Турниры из трех вершин]]
  
 
<br clear="all">
 
<br clear="all">
−
 
+
==Свойства турниров==
−
==Оценка количества турниров в графе==
+
===Оценка количества турниров в графе===
 
Если в турнире опустить ориентацию ребер, то мы получим полный граф. А так как существует два варианта ориентации каждого ребра, то количество турниров в графе из <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 вершинами]]
 
[[Файл:Tournament_transitive.png|300px|thumb|right|Транзитивный турнир с 8 вершинами]]
−
Турнир, в котором <tex>((a \rightarrow b)\&(b \rightarrow c)) \Rightarrow (a \rightarrow c)</tex>, называется транзитивным. В транзитивном турнире вершины могут быть полностью упорядочены в порядке достижимости.
+
Турнир, в котором <tex>((a \rightarrow b)\&(b \rightarrow c)) \Rightarrow (a \rightarrow c)</tex>, где <tex>a \rightarrow b</tex> обозначает ориентированное ребро из <tex>a</tex> в <tex>b</tex>, называется транзитивным. В транзитивном турнире вершины могут быть полностью упорядочены в порядке достижимости.
  
−
Следующие утверждения для турнира с n вершинами эквивалентны:
+
Следующие утверждения для турнира <tex>T</tex> с <tex>n</tex> вершинами эквивалентны:
−
*<tex>T</tex> транзитивен.
+
*<tex>T</tex> транзитивен,
−
*<tex>T</tex> ацикличен.
+
*<tex>T</tex> ацикличен,
−
*<tex>T</tex> не содержит циклов длины 3.
+
*<tex>T</tex> не содержит циклов длины <tex>3</tex>,
−
*Последовательность числа выигрышей (множество полуисходов) <tex>T</tex> есть <tex> 0, 1, 2,..., n - 1 </tex>.
+
* множества, составленные из <tex>\deg^{-}</tex> или <tex>\deg^{+}</tex> для каждой вершины <tex>T</tex>, есть <tex>\{ 0, 1, 2,..., n - 1\} </tex>,
 
*<tex>T</tex> содержит ровно один гамильтонов путь.
 
*<tex>T</tex> содержит ровно один гамильтонов путь.
  
−
Транзитивные турниры играют существенную роль в теории Рамсея, изучающей условия, при которых в произвольно формируемых математических объектах обязан появиться некоторый порядок. В частности, любой турнир с <tex>n</tex> вершинами содержит транзитивный подтурнир с <tex>1+\lfloor\log_2 n\rfloor</tex> вершинами. Для его построения выберем любую вершину <tex>v</tex> как часть этого подтурнира и построим подтурнир рекурсивно на множестве либо входящих соседей вершины <tex>v</tex>, либо на множестве исходящих соседей, в зависимости от того, какое множество больше.  
+
Транзитивные турниры играют существенную роль в [https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%A0%D0%B0%D0%BC%D1%81%D0%B5%D1%8F теории Рамсея], изучающей условия, при которых в произвольно формируемых математических объектах обязан появиться некоторый порядок. В частности, любой турнир с <tex>n</tex> вершинами содержит транзитивный подтурнир с <tex>1+\lfloor\log_2 n\rfloor</tex> вершинами. Для его построения выберем любую вершину <tex>v</tex> как часть этого подтурнира и построим подтурнир рекурсивно на множестве либо входящих соседей вершины <tex>v</tex>, либо на множестве исходящих соседей, в зависимости от того, какое множество больше.  
 
<br clear="all">
 
<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 |сильно связным]], если из любой вершины существуют пути до всех других.}}
 
{{Определение
 
{{Определение
Строка 41: Строка 37:
  
  
−
Не все турниры гамильтоновы. Определение не исключает существование вершины с <tex>deg^{-}</tex> или <tex>deg^{+}</tex> равной нулю — в первую нельзя войти, а из второй — выйти. Однако отсутствие таких вершин не означает, что турнир гамильтонов (пример — на рисунке справа).
+
Не все турниры гамильтоновы. Определение не исключает существование вершины с <tex>\deg^{-}</tex> или <tex>\deg^{+}</tex> равной нулю — в первую нельзя войти, а из второй — выйти. Однако отсутствие таких вершин не означает, что турнир гамильтонов (пример — на рисунке справа).
  
 
[[Теорема Редеи-Камиона]] устанавливает 2 следующих факта:
 
[[Теорема Редеи-Камиона]] устанавливает 2 следующих факта:
Строка 54: Строка 50:
 
==Источники информации==
 
==Источники информации==
 
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — ISBN 5-93972-076-5
 
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — ISBN 5-93972-076-5
 +
* [[wikipedia:Tournament_(graph_theory) | Wikipedia {{---}} Турнир]]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Обходы графов]]
 
[[Категория: Обходы графов]]
 
[[Категория: Гамильтоновы графы]]
 
[[Категория: Гамильтоновы графы]]

Версия 22:47, 7 ноября 2015

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

Турниром из [math]n[/math] вершин можно изобразить исход игры между [math]n[/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], где [math]a \rightarrow b[/math] обозначает ориентированное ребро из [math]a[/math] в [math]b[/math], называется транзитивным. В транзитивном турнире вершины могут быть полностью упорядочены в порядке достижимости.

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

  • [math]T[/math] транзитивен,
  • [math]T[/math] ацикличен,
  • [math]T[/math] не содержит циклов длины [math]3[/math],
  • множества, составленные из [math]\deg^{-}[/math] или [math]\deg^{+}[/math] для каждой вершины [math]T[/math], есть [math]\{ 0, 1, 2,..., n - 1\} [/math],
  • [math]T[/math] содержит ровно один гамильтонов путь.

Транзитивные турниры играют существенную роль в теории Рамсея, изучающей условия, при которых в произвольно формируемых математических объектах обязан появиться некоторый порядок. В частности, любой турнир с [math]n[/math] вершинами содержит транзитивный подтурнир с [math]1+\lfloor\log_2 n\rfloor[/math] вершинами. Для его построения выберем любую вершину [math]v[/math] как часть этого подтурнира и построим подтурнир рекурсивно на множестве либо входящих соседей вершины [math]v[/math], либо на множестве исходящих соседей, в зависимости от того, какое множество больше.

Конденсация

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

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

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


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


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


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

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

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


См. также

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

  • Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы — НИЦ РХД, 2001. — ISBN 5-93972-076-5
  • Wikipedia — Турнир
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Турниры&oldid=49784»