Турниры — различия между версиями
(→Транзитивность) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 3 промежуточные версии 2 участников) | |||
Строка 40: | Строка 40: | ||
'''Переход индукции''' Пусть доказано для <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>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>4 \Rightarrow 5: </tex> По [[Теорема Редеи-Камиона|теореме Редеи-Камиона]], в любом турнире есть гамильтонов путь, докажем индукцией по <tex>n</tex>, что этот путь единственный. |
'''База индукции''' <tex>n = 1</tex>: верно, путь из одной вершины. | '''База индукции''' <tex>n = 1</tex>: верно, путь из одной вершины. | ||
− | '''Переход индукции''' Рассмотрим вершину <tex>s: deg^{-}(s) = 0</tex>. Она будет первой в гамильтоновом пути. Рассмотрим граф <tex>T - s</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= | + | <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 = | + | # <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 = | + | # <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 = | + | # <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 = | + | #<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 + 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>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>. |
}} | }} | ||
Текущая версия на 19:28, 4 сентября 2022
Определение: |
Турнир (англ. Tournament) — ориентированный граф, между любой парой различных вершин которого есть ровно одно ориентированное ребро. |
Турниром из
вершин можно изобразить исход игры между людьми, где каждый играет с каждым. Тогда ребро будет ориентировано от выигравшего человека к проигравшему.
Содержание
Свойства турниров
Оценка количества турниров в графе
Если в турнире опустить ориентацию ребер, то мы получим полный граф. А так как существует два варианта ориентации каждого ребра, то количество турниров в графе из
вершин равно .Транзитивность
Турнир, в котором
, называется транзитивным. В транзитивном турнире вершины могут быть полностью упорядочены в порядке достижимости.Теорема: |
Пусть — турнир, . Тогда следующие утверждения эквивалентны:
|
Доказательство: |
Пусть существует цикл длины Однако по транзитивности должно существовать ребро , т.е. между есть противоположно направленных ребра, что невозможно по определению турнира. Пусть в графе содержится цикл длины . Это не может быть цикл длины (противоречит определению турнира). Обозначим его вершины в порядке обхода . Заметим, что т.к. нет циклов длины , выполнена транзитивность (в противном случае существовали бы ребра ). Докажем по индукции, что существует ребро База индукции : (по транзитивности).Переход индукции Пусть доказано для всех , что , также известно, что , тогда по транзитивности .Таким образом, в транзитивном турнире содержится цикл длины — противоречие (см. предыдущий пункт).Обозначим множество значений степеней исхода как . Докажем индукцией по . База индукции : верно, т.к. есть одна вершина степениПереход индукции Пусть доказано для . В ациклическом графе существует сток . Рассмотрим граф . . Т.к. из каждой ведет одно ребро в , . Для степеней захода можно доказать аналогично, рассмотрев исток вместо стока.теореме Редеи-Камиона, в любом турнире есть гамильтонов путь, докажем индукцией по , что этот путь единственный. ПоБаза индукции : верно, путь из одной вершины.Переход индукции Рассмотрим вершину . Она будет первой в гамильтоновом пути (иначе мы в нее не зайдем). Рассмотрим граф . Т.к. была соединена со всеми его вершинами, их степени меньше на соответствующих степеней в исходном турнире, значит , следовательно в существует единственный гамильтонов путь (по предположению). Пусть существуют гамильтонова пути, начинающиеся на , но тогда существуют 2 пути в — противоречие.Пусть — единственный гамильтонов путь. Пусть найдется — наименьший индекс такой, что в вершину идет ребро из вершины с большим индексом, а — вершина с наибольшим индексом, из которой ребро ведет в . Возможно несколько случаев:
Замечание Может достигаться равенство Во всех случаях получаем противоречие с единственностью гамильтонова пути, значит не существует такого , в этом случае нужно исключить из пути последовательных вхождения . , т.е . Значит . |
Теория Рамсея
Транзитивные турниры играют существенную роль в теории Рамсея, изучающей условия, при которых в произвольно формируемых математических объектах обязан появиться некоторый порядок. В частности, любой турнир с вершинами содержит транзитивный подтурнир с вершинами. Для его построения выберем любую вершину как часть этого подтурнира и построим подтурнир рекурсивно на множестве либо входящих соседей вершины , либо на множестве исходящих соседей, в зависимости от того, какое множество больше.
Конденсация
Утверждение: |
Конденсация любого турнира является транзитивным турниром. |
Рассмотрим теореме, это означает, что она транзитивна. | компоненты сильной связности , найдутся , либо , значит в конденсации есть либо ребро , либо . Т.к. мы рассмотрели произвольную пару вершин конденсации турнира, она является турниром. Конденсация любого орграфа ациклична, а по доказанной
Таким образом, даже если турнир не является транзитивным, сильно связанные компоненты турнира могут быть вполне упорядочены. В самом деле, по теореме, в турнире существует гамильтонов путь, значит вершины могут быть упорядочены по своим позициям в этом пути.
Сильно связные турниры
Определение: |
Турнир называется сильно связным, если из любой вершины существуют пути до всех других. |
Определение: |
Турнир называется гамильтоновым, если он содержит гамильтонов цикл. |
Не все турниры гамильтоновы. Определение не исключает существование вершины с или равной нулю — в первую нельзя войти, а из второй — выйти. Однако отсутствие таких вершин не означает, что турнир гамильтонов (пример — на рисунке справа).
Теорема Редеи-Камиона устанавливает два следующих факта:
- Все турниры полугамильтоновы.
- Турнир гамильтонов тогда и только тогда, когда он сильно связен.
См. также
Источники информации
- Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы — НИЦ РХД, 2001. — ISBN 5-93972-076-5
- Wikipedia — Турнир
- [1]