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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 13: Строка 13:
  
 
[[Файл: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</tex> обозначает ориентированное ребро из <tex>a</tex> в <tex>b</tex>, называется транзитивным. В транзитивном турнире вершины могут быть полностью упорядочены в порядке достижимости.
+
Турнир, в котором <tex>(a, b)\land(b, c) \Rightarrow (a, c)</tex>, называется транзитивным. В транзитивном турнире вершины могут быть полностью упорядочены в порядке достижимости.
  
 
Следующие утверждения для турнира <tex>T</tex> с <tex>n</tex> вершинами эквивалентны:
 
Следующие утверждения для турнира <tex>T</tex> с <tex>n</tex> вершинами эквивалентны:
Строка 22: Строка 22:
 
*<tex>T</tex> содержит ровно один гамильтонов путь.
 
*<tex>T</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>, либо на множестве исходящих соседей, в зависимости от того, какое множество больше.  
+
===Теория Рамсея===
 +
Транзитивные турниры играют существенную роль в [[Теория_Рамсея | теории Рамсея]], изучающей условия, при которых в произвольно формируемых математических объектах обязан появиться некоторый порядок. В частности, любой турнир с <tex>n</tex> вершинами содержит транзитивный подтурнир с <tex>1+\lfloor\log_2 n\rfloor</tex> вершинами. Для его построения выберем любую вершину <tex>v</tex> как часть этого подтурнира и построим подтурнир рекурсивно на множестве либо входящих соседей вершины <tex>v</tex>, либо на множестве исходящих соседей, в зависимости от того, какое множество больше.  
 
<br clear="all">
 
<br clear="all">
  
Строка 39: Строка 40:
 
Не все турниры гамильтоновы. Определение не исключает существование вершины с <tex>\deg^{-}</tex> или <tex>\deg^{+}</tex> равной нулю — в первую нельзя войти, а из второй — выйти. Однако отсутствие таких вершин не означает, что турнир гамильтонов (пример — на рисунке справа).
 
Не все турниры гамильтоновы. Определение не исключает существование вершины с <tex>\deg^{-}</tex> или <tex>\deg^{+}</tex> равной нулю — в первую нельзя войти, а из второй — выйти. Однако отсутствие таких вершин не означает, что турнир гамильтонов (пример — на рисунке справа).
  
[[Теорема Редеи-Камиона]] устанавливает 2 следующих факта:
+
[[Теорема Редеи-Камиона]] устанавливает два следующих факта:
 
# Все турниры полугамильтоновы.
 
# Все турниры полугамильтоновы.
 
# Турнир гамильтонов тогда и только тогда, когда он сильно связен.
 
# Турнир гамильтонов тогда и только тогда, когда он сильно связен.
Строка 47: Строка 48:
 
* [[Гамильтоновы графы]]
 
* [[Гамильтоновы графы]]
 
* [[Теорема Редеи-Камиона]]
 
* [[Теорема Редеи-Камиона]]
 +
* [http://epubs.siam.org/doi/abs/10.1137/0403002 Поиск гамильтонова цикла за <tex>O(n\cdot log(n))</tex>]
  
 
==Источники информации==
 
==Источники информации==

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

Определение:
Турнир (англ. 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[/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] равной нулю — в первую нельзя войти, а из второй — выйти. Однако отсутствие таких вершин не означает, что турнир гамильтонов (пример — на рисунке справа).

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

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


См. также

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

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