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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 26 промежуточных версий 6 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
|definition = '''Турнир''' — [[ориентированный граф]], между любой парой различных вершин которого есть ровно одно ориентированное ребро.
+
|definition = '''Турнир''' (англ. ''Tournament'') — [[ориентированный граф]], между любой парой различных вершин которого есть ровно одно ориентированное ребро.
 
}}  
 
}}  
Название этого класса графов связано с тем, что их удобно использовать для описания результатов командных соревнований в некоторых видах спорта.
+
Турниром из <tex>n</tex> вершин можно изобразить исход игры между <tex>n</tex> людьми, где каждый играет с каждым. Тогда ребро будет ориентировано от выигравшего человека к проигравшему.
[[Файл:тур.png|thumb|right|турниры из 2, 3 и 4 вершин]]
 
  
==Сильно связные турниры==
+
[[Файл:Tournament_1_3.png|415px|thumb|left|Турниры из трех вершин]]
 +
 
 +
<br clear="all">
 +
==Свойства турниров==
 +
===Оценка количества турниров в графе===
 +
Если в турнире опустить ориентацию ребер, то мы получим полный граф. А так как существует два варианта ориентации каждого ребра, то количество турниров в графе из <tex>n</tex> вершин равно <tex dpi=150>2^{\frac{n\cdot(n-1)}{2}}</tex>.
 +
===Транзитивность===
 +
 
 +
[[Файл:Tournament_transitive.png|300px|thumb|right|Транзитивный турнир с 8 вершинами]]
 +
Турнир, в котором <tex>(a, b)\land(b, c) \Rightarrow (a, c)</tex>, называется транзитивным. В транзитивном турнире вершины могут быть полностью упорядочены в порядке достижимости.
 +
{{Теорема
 +
|id=theorem1
 +
|statement=
 +
Пусть <tex>T=\langle V, E\rangle</tex> — турнир, <tex>| V| = n</tex>. Тогда следующие утверждения эквивалентны:
 +
#<tex>T</tex> транзитивен;
 +
#<tex>T</tex> не содержит циклов длины <tex>3</tex>;
 +
#<tex>T</tex> ациклический;
 +
# множества, составленные из <tex>\deg^{-}</tex> или <tex>\deg^{+}</tex> для каждой вершины <tex>T</tex>, есть <tex>\{ 0, 1, 2,..., n - 1\} </tex>;
 +
#<tex>T</tex> содержит ровно один гамильтонов путь.
 +
|proof=
 +
<tex>1 \Rightarrow 2:</tex> Пусть существует цикл длины <tex>3: (u, v), (v, w), (w, u). </tex> Однако по транзитивности должно существовать ребро <tex>(u, w)</tex>, т.е. между <tex>u, w</tex> есть <tex>2</tex> противоположно направленных ребра, что невозможно по определению турнира.
 +
 
 +
<tex>2 \Rightarrow 3:</tex> Пусть в графе содержится цикл длины <tex>k \neq 3</tex>. Это не может быть цикл длины <tex>2</tex> (противоречит определению турнира). Обозначим его вершины в порядке обхода <tex>v_1, v_2, \ldots, v_k, k \geqslant 4</tex>. Заметим, что т.к. нет циклов длины <tex>3</tex>, выполнена транзитивность (в противном случае существовали бы ребра <tex>(u, v), (v, w), (w, u)</tex>). Докажем по индукции, что существует ребро <tex>(v_1, v_{k - 1}).</tex>
 +
 
 +
'''База индукции''' <tex>k = 3</tex>: <tex>(v_1, v_2) , (v_2, v_3) \in E \Rightarrow (v_1, v_3) \in E </tex> (по транзитивности). 
 +
 
 +
'''Переход индукции''' Пусть доказано для всех <tex>i < k - 1</tex>, что <tex>(v_1, v_i) \in E</tex>, также известно, что <tex>(v_i, v_{i+1}) \in E</tex>, тогда по транзитивности <tex>(v_1, v_{i+1}) \in E</tex>.
 +
 
 +
Таким образом, в транзитивном турнире содержится цикл длины <tex>3</tex> — противоречие (см. предыдущий пункт).
 +
 
 +
<tex>3 \Rightarrow 4: </tex> Обозначим множество значений степеней исхода как <tex>Deg^{+}(T)</tex>. Докажем индукцией по <tex>n</tex>.
 +
 
 +
'''База индукции''' <tex>n = 1</tex>: верно, т.к. есть одна вершина степени <tex>0</tex>
 +
 
 +
'''Переход индукции''' Пусть доказано для <tex>n - 1</tex>. В ациклическом графе существует сток <tex>t, deg^{+}t = 0</tex>. Рассмотрим граф <tex>T-t</tex>. <tex>Deg^{+}(T - t) = \{0, 1, \ldots, n - 2\}</tex> . Т.к. из каждой <tex>v \in V \setminus \{t\}</tex> ведет одно ребро в <tex>t</tex>, <tex> Deg^{+}(T)=\{deg^{+}t\} \cup \{x + 1 \mid x \in Deg^{+}(T -t)\} = \{0, 1, \ldots, n - 1\}</tex>. Для степеней захода можно доказать аналогично, рассмотрев исток вместо стока.
 +
 
 +
<tex>4 \Rightarrow 5: </tex> По [[Теорема Редеи-Камиона|теореме Редеи-Камиона]], в любом турнире есть гамильтонов путь, докажем индукцией по <tex>n</tex>, что этот путь единственный.
 +
 
 +
'''База индукции''' <tex>n  = 1</tex>: верно, путь из одной вершины.
 +
 
 +
'''Переход индукции''' Рассмотрим вершину <tex>s: deg^{-}(s) = 0</tex>. Она будет первой в гамильтоновом пути (иначе мы в нее не зайдем). Рассмотрим граф <tex>T - s</tex>. Т.к. <tex>s</tex> была соединена со всеми его вершинами, их степени меньше на <tex>1</tex> соответствующих степеней в исходном турнире, значит <tex>Deg^{-}(T-s)=\{0,1, \ldots, n - 2\}</tex>, следовательно в <tex>T-s</tex> существует единственный гамильтонов путь <tex>v_1, v_2, \ldots v_{n -1}</tex> (по предположению). Пусть существуют <tex>2</tex> гамильтонова пути, начинающиеся на <tex>s</tex>, но тогда существуют 2 пути в <tex>T-s</tex> {{---}} противоречие.
 +
 
 +
<tex>5 \Rightarrow 1: </tex> Пусть <tex>P=v_1, v_2, \ldots, v_n</tex> — единственный гамильтонов путь. Пусть найдется <tex>m</tex> — наименьший индекс такой, что в вершину <tex>v_m</tex> идет ребро из вершины с большим индексом, а <tex>v_k</tex> — вершина с наибольшим индексом, из которой ребро ведет в <tex>v_m</tex>. Возможно несколько случаев:
 +
# <tex> m \neq 1, k \neq n: </tex> Из <tex>v_{m -1}</tex> ведет ребро в <tex>v_{m+1}</tex> (по минимальности <tex>m</tex>), а из <tex>v_m</tex> ведет ребро в <tex>v_{k +1}</tex> (по максимальности <tex>k</tex>). Тогда будет существовать еще один гамильтонов путь <tex>P_1 = v_1, \ldots, v_{m-1}, v_{m+1}, \ldots, v_{k}, v_m, v_{k+1}, \ldots, v_n</tex>.
 +
# <tex> m \neq 1, k = n: </tex> <tex>P_1 = v_1, \ldots, v_{m-1}, v_{m+1}, \ldots, v_{n}, v_m</tex>.
 +
# <tex> m = 1, k \neq n:</tex> <tex>P_1 = v_2, \ldots, v_{k}, v_1, v_{k+1}</tex>
 +
#<tex> m = 1, k = n:</tex> <tex>P_1 = v_2, \ldots, v_n, v_1</tex>
 +
'''Замечание''' Может достигаться равенство <tex>m + 1 = n</tex>, в этом случае нужно исключить из пути <tex>2</tex> последовательных вхождения <tex>v_n</tex>.
 +
Во всех случаях получаем противоречие с единственностью гамильтонова пути, значит не существует такого <tex>m</tex>, т.е <tex>(v_i, v_j) \in E \Leftrightarrow i < j</tex>. Значит <tex>\forall i, j, k: 1 \leqslant i, j, k \leqslant n</tex> <tex> (v_i, v_j) \in E \land (v_j, v_k) \in E \Rightarrow i < j \land j < k \Rightarrow (v_i, v_k) \in E </tex>.
 +
}}
 +
 
 +
===Теория Рамсея===
 +
Транзитивные турниры играют существенную роль в [[Теория_Рамсея | теории Рамсея]], изучающей условия, при которых в произвольно формируемых математических объектах обязан появиться некоторый порядок. В частности, любой турнир с <tex>n</tex> вершинами содержит транзитивный подтурнир с <tex>1+\lfloor\log_2 n\rfloor</tex> вершинами. Для его построения выберем любую вершину <tex>v</tex> как часть этого подтурнира и построим подтурнир рекурсивно на множестве либо входящих соседей вершины <tex>v</tex>, либо на множестве исходящих соседей, в зависимости от того, какое множество больше.
 +
<br clear="all">
 +
 
 +
===Конденсация===
 +
{{Утверждение
 +
|statement = Конденсация любого турнира является транзитивным турниром.
 +
|proof = Рассмотрим <tex>2</tex> компоненты сильной связности <tex>U, V</tex>, найдутся <tex>u \in U, v \in V: (u, v) \in E</tex>, либо <tex>(v, u) \in E </tex>, значит в конденсации есть либо ребро <tex>(U,V)</tex>, либо <tex>(V,U)</tex>. Т.к. мы рассмотрели произвольную пару вершин конденсации турнира, она является турниром. Конденсация любого орграфа ациклична, а по доказанной [[#theorem1|теореме]], это означает, что она транзитивна.
 +
}}
 +
Таким образом, даже если турнир не является транзитивным, сильно связанные компоненты турнира могут быть [[Отношение порядка|вполне упорядочены]]. В самом деле, по [[#theorem1|теореме]], в турнире существует гамильтонов путь, значит вершины могут быть упорядочены по своим позициям в этом пути.
 +
 
 +
===Сильно связные турниры===
 
{{Определение|definition = Турнир называется [[Отношение связности, компоненты связности#sc_def |сильно связным]], если из любой вершины существуют пути до всех других.}}
 
{{Определение|definition = Турнир называется [[Отношение связности, компоненты связности#sc_def |сильно связным]], если из любой вершины существуют пути до всех других.}}
 
{{Определение
 
{{Определение
Строка 11: Строка 72:
 
}}
 
}}
  
[[Файл:негам.png|thumb|right|Негамильтонов турнир]]
 
Не все турниры гамильтоновы. Определение не исключает существование вершины с полустепенью исхода или захода равной нулю — в первую нельзя войти, а из второй — выйти. Однако отсутствие таких вершин не означает, что турнир гамильтонов (пример — на рисунке справа).
 
  
[[Теорема Редеи-Камиона]] устанавливает 2 следующих факта:
+
[[Файл:Tournament_2.png|380px|thumb|right|Негамильтонов турнир]]
 +
 
 +
 
 +
Не все турниры гамильтоновы. Определение не исключает существование вершины с <tex>\deg^{-}</tex> или <tex>\deg^{+}</tex> равной нулю — в первую нельзя войти, а из второй — выйти. Однако отсутствие таких вершин не означает, что турнир гамильтонов (пример — на рисунке справа).
 +
 
 +
[[Теорема Редеи-Камиона]] устанавливает два следующих факта:
 
# Все турниры полугамильтоновы.
 
# Все турниры полугамильтоновы.
 
# Турнир гамильтонов тогда и только тогда, когда он сильно связен.
 
# Турнир гамильтонов тогда и только тогда, когда он сильно связен.
 +
<br clear="all">
  
 
==См. также==
 
==См. также==
[[Гамильтоновы графы]]
+
* [[Гамильтоновы графы]]
 
+
* [[Теорема Редеи-Камиона]]
[[Теорема Редеи-Камиона]]
+
* [http://epubs.siam.org/doi/abs/10.1137/0403002 Поиск гамильтонова цикла за <tex>O(n\cdot log(n))</tex>]
  
==Литература==
+
==Источники информации==
 
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — ISBN 5-93972-076-5
 
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — ISBN 5-93972-076-5
 +
* [[wikipedia:Tournament_(graph_theory) | Wikipedia {{---}} Турнир]]
 +
* [http://www-math.ucdenver.edu/~wcherowi/courses/m4408/gtln12.html]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Обходы графов]]
 
[[Категория: Обходы графов]]
 +
[[Категория: Гамильтоновы графы]]

Текущая версия на 19:28, 4 сентября 2022

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

Турниром из [math]n[/math] вершин можно изобразить исход игры между [math]n[/math] людьми, где каждый играет с каждым. Тогда ребро будет ориентировано от выигравшего человека к проигравшему.

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


Свойства турниров

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

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

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

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

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

Теорема:
Пусть [math]T=\langle V, E\rangle[/math] — турнир, [math]| V| = n[/math]. Тогда следующие утверждения эквивалентны:
  1. [math]T[/math] транзитивен;
  2. [math]T[/math] не содержит циклов длины [math]3[/math];
  3. [math]T[/math] ациклический;
  4. множества, составленные из [math]\deg^{-}[/math] или [math]\deg^{+}[/math] для каждой вершины [math]T[/math], есть [math]\{ 0, 1, 2,..., n - 1\} [/math];
  5. [math]T[/math] содержит ровно один гамильтонов путь.
Доказательство:
[math]\triangleright[/math]

[math]1 \Rightarrow 2:[/math] Пусть существует цикл длины [math]3: (u, v), (v, w), (w, u). [/math] Однако по транзитивности должно существовать ребро [math](u, w)[/math], т.е. между [math]u, w[/math] есть [math]2[/math] противоположно направленных ребра, что невозможно по определению турнира.

[math]2 \Rightarrow 3:[/math] Пусть в графе содержится цикл длины [math]k \neq 3[/math]. Это не может быть цикл длины [math]2[/math] (противоречит определению турнира). Обозначим его вершины в порядке обхода [math]v_1, v_2, \ldots, v_k, k \geqslant 4[/math]. Заметим, что т.к. нет циклов длины [math]3[/math], выполнена транзитивность (в противном случае существовали бы ребра [math](u, v), (v, w), (w, u)[/math]). Докажем по индукции, что существует ребро [math](v_1, v_{k - 1}).[/math]

База индукции [math]k = 3[/math]: [math](v_1, v_2) , (v_2, v_3) \in E \Rightarrow (v_1, v_3) \in E [/math] (по транзитивности).

Переход индукции Пусть доказано для всех [math]i \lt k - 1[/math], что [math](v_1, v_i) \in E[/math], также известно, что [math](v_i, v_{i+1}) \in E[/math], тогда по транзитивности [math](v_1, v_{i+1}) \in E[/math].

Таким образом, в транзитивном турнире содержится цикл длины [math]3[/math] — противоречие (см. предыдущий пункт).

[math]3 \Rightarrow 4: [/math] Обозначим множество значений степеней исхода как [math]Deg^{+}(T)[/math]. Докажем индукцией по [math]n[/math].

База индукции [math]n = 1[/math]: верно, т.к. есть одна вершина степени [math]0[/math]

Переход индукции Пусть доказано для [math]n - 1[/math]. В ациклическом графе существует сток [math]t, deg^{+}t = 0[/math]. Рассмотрим граф [math]T-t[/math]. [math]Deg^{+}(T - t) = \{0, 1, \ldots, n - 2\}[/math] . Т.к. из каждой [math]v \in V \setminus \{t\}[/math] ведет одно ребро в [math]t[/math], [math] Deg^{+}(T)=\{deg^{+}t\} \cup \{x + 1 \mid x \in Deg^{+}(T -t)\} = \{0, 1, \ldots, n - 1\}[/math]. Для степеней захода можно доказать аналогично, рассмотрев исток вместо стока.

[math]4 \Rightarrow 5: [/math] По теореме Редеи-Камиона, в любом турнире есть гамильтонов путь, докажем индукцией по [math]n[/math], что этот путь единственный.

База индукции [math]n = 1[/math]: верно, путь из одной вершины.

Переход индукции Рассмотрим вершину [math]s: deg^{-}(s) = 0[/math]. Она будет первой в гамильтоновом пути (иначе мы в нее не зайдем). Рассмотрим граф [math]T - s[/math]. Т.к. [math]s[/math] была соединена со всеми его вершинами, их степени меньше на [math]1[/math] соответствующих степеней в исходном турнире, значит [math]Deg^{-}(T-s)=\{0,1, \ldots, n - 2\}[/math], следовательно в [math]T-s[/math] существует единственный гамильтонов путь [math]v_1, v_2, \ldots v_{n -1}[/math] (по предположению). Пусть существуют [math]2[/math] гамильтонова пути, начинающиеся на [math]s[/math], но тогда существуют 2 пути в [math]T-s[/math] — противоречие.

[math]5 \Rightarrow 1: [/math] Пусть [math]P=v_1, v_2, \ldots, v_n[/math] — единственный гамильтонов путь. Пусть найдется [math]m[/math] — наименьший индекс такой, что в вершину [math]v_m[/math] идет ребро из вершины с большим индексом, а [math]v_k[/math] — вершина с наибольшим индексом, из которой ребро ведет в [math]v_m[/math]. Возможно несколько случаев:

  1. [math] m \neq 1, k \neq n: [/math] Из [math]v_{m -1}[/math] ведет ребро в [math]v_{m+1}[/math] (по минимальности [math]m[/math]), а из [math]v_m[/math] ведет ребро в [math]v_{k +1}[/math] (по максимальности [math]k[/math]). Тогда будет существовать еще один гамильтонов путь [math]P_1 = v_1, \ldots, v_{m-1}, v_{m+1}, \ldots, v_{k}, v_m, v_{k+1}, \ldots, v_n[/math].
  2. [math] m \neq 1, k = n: [/math] [math]P_1 = v_1, \ldots, v_{m-1}, v_{m+1}, \ldots, v_{n}, v_m[/math].
  3. [math] m = 1, k \neq n:[/math] [math]P_1 = v_2, \ldots, v_{k}, v_1, v_{k+1}[/math]
  4. [math] m = 1, k = n:[/math] [math]P_1 = v_2, \ldots, v_n, v_1[/math]

Замечание Может достигаться равенство [math]m + 1 = n[/math], в этом случае нужно исключить из пути [math]2[/math] последовательных вхождения [math]v_n[/math].

Во всех случаях получаем противоречие с единственностью гамильтонова пути, значит не существует такого [math]m[/math], т.е [math](v_i, v_j) \in E \Leftrightarrow i \lt j[/math]. Значит [math]\forall i, j, k: 1 \leqslant i, j, k \leqslant n[/math] [math] (v_i, v_j) \in E \land (v_j, v_k) \in E \Rightarrow i \lt j \land j \lt k \Rightarrow (v_i, v_k) \in E [/math].
[math]\triangleleft[/math]

Теория Рамсея

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

Конденсация

Утверждение:
Конденсация любого турнира является транзитивным турниром.
[math]\triangleright[/math]
Рассмотрим [math]2[/math] компоненты сильной связности [math]U, V[/math], найдутся [math]u \in U, v \in V: (u, v) \in E[/math], либо [math](v, u) \in E [/math], значит в конденсации есть либо ребро [math](U,V)[/math], либо [math](V,U)[/math]. Т.к. мы рассмотрели произвольную пару вершин конденсации турнира, она является турниром. Конденсация любого орграфа ациклична, а по доказанной теореме, это означает, что она транзитивна.
[math]\triangleleft[/math]

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

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

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


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


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


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

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

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


См. также

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

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