Турниры — различия между версиями
(→Транзитивность) |
Rgolchin (обсуждение | вклад) (→Транзитивность) |
||
Строка 46: | Строка 46: | ||
'''Переход индукции''' Рассмотрим вершину <tex>s: deg^{-}(s) = 0</tex>. Она будет первой в гамильтоновом пути. Рассмотрим граф <tex>T - s</tex>, в нем существует единственный гамильтонов путь (по предположению), значит и в <tex>T</tex> он будет единственным. | '''Переход индукции''' Рассмотрим вершину <tex>s: deg^{-}(s) = 0</tex>. Она будет первой в гамильтоновом пути. Рассмотрим граф <tex>T - s</tex>, в нем существует единственный гамильтонов путь (по предположению), значит и в <tex>T</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, (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>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, (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>. |
Версия 22:52, 8 января 2017
Определение: |
Турнир (англ. Tournament) — ориентированный граф, между любой парой различных вершин которого есть ровно одно ориентированное ребро. |
Турниром из
вершин можно изобразить исход игры между людьми, где каждый играет с каждым. Тогда ребро будет ориентировано от выигравшего человека к проигравшему.
Содержание
Свойства турниров
Оценка количества турниров в графе
Если в турнире опустить ориентацию ребер, то мы получим полный граф. А так как существует два варианта ориентации каждого ребра, то количество турниров в графе из
вершин равно .Транзитивность
Турнир, в котором
, называется транзитивным. В транзитивном турнире вершины могут быть полностью упорядочены в порядке достижимости.Теорема: |
Пусть — турнир, . Тогда следующие утверждения эквивалентны:
|
Доказательство: |
Пусть существует цикл длины Однако по транзитивности должно существовать ребро , т.е. между есть противоположно направленных ребра, что невозможно по определению турнира. Пусть в графе содержится цикл длины . Это не может быть цикл длины (противоречит определению турнира). Обозначим его вершины в порядке обхода . Заметим, что т.к. нет циклов длины , выполнена транзитивность (в противном случае существовали бы ребра ). Докажем по индукции, что существует ребро База индукции : (по транзитивности).Переход индукции Пусть доказано для всех , что , также известно, что , тогда по транзитивности .Таким образом, в транзитивном турнире содержится цикл длины — противоречие (см. предыдущий пункт).Обозначим множество значений степеней исхода как . Докажем индукцией по . База индукции : верно, т.к. есть одна вершина степениПереход индукции Пусть доказано для . В ациклическом графе существует сток . Рассмотрим граф . . Т.к. из каждой ведет одно ребро в , . Для степеней захода можно доказать аналогично, рассмотрев исток вместо стока.теореме Редеи-Камиона, в любом турнире есть гамильтонов путь, докажем единственность индукцией по . ПоБаза индукции : верно, путь из одной вершины.Переход индукции Рассмотрим вершину . Она будет первой в гамильтоновом пути. Рассмотрим граф , в нем существует единственный гамильтонов путь (по предположению), значит и в он будет единственным.Пусть — единственный гамильтонов путь. Пусть найдется — наименьший индекс такой, что в вершину идет ребро из вершины с большим индексом, а — вершина с наибольшим индексом, из которой ребро ведет в . Возможно несколько случаев:
Замечание Может достигаться равенство Во всех случаях получаем противоречие с единственностью гамильтонова пути, значит не существует такого , в этом случае нужно исключить из пути последовательных вхождения . , т.е . Значит . |
Теория Рамсея
Транзитивные турниры играют существенную роль в теории Рамсея, изучающей условия, при которых в произвольно формируемых математических объектах обязан появиться некоторый порядок. В частности, любой турнир с вершинами содержит транзитивный подтурнир с вершинами. Для его построения выберем любую вершину как часть этого подтурнира и построим подтурнир рекурсивно на множестве либо входящих соседей вершины , либо на множестве исходящих соседей, в зависимости от того, какое множество больше.
Конденсация
Утверждение: |
Конденсация любого турнира является транзитивным турниром. |
Рассмотрим теореме, это означает, что она транзитивна. | компоненты сильной связности , найдутся , либо , значит в конденсации есть либо ребро , либо . Т.к. мы рассмотрели произвольную пару вершин конденсации турнира, она является турниром. Конденсация любого орграфа ациклична, а по доказанной
Таким образом, даже если турнир не является транзитивным, сильно связанные компоненты турнира могут быть вполне упорядочены. В самом деле, по теореме, в турнире существует гамильтонов путь, значит вершины могут быть упорядочены по своим позициям в этом пути.
Сильно связные турниры
Определение: |
Турнир называется сильно связным, если из любой вершины существуют пути до всех других. |
Определение: |
Турнир называется гамильтоновым, если он содержит гамильтонов цикл. |
Не все турниры гамильтоновы. Определение не исключает существование вершины с или равной нулю — в первую нельзя войти, а из второй — выйти. Однако отсутствие таких вершин не означает, что турнир гамильтонов (пример — на рисунке справа).
Теорема Редеи-Камиона устанавливает два следующих факта:
- Все турниры полугамильтоновы.
- Турнир гамильтонов тогда и только тогда, когда он сильно связен.
См. также
Источники информации
- Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы — НИЦ РХД, 2001. — ISBN 5-93972-076-5
- Wikipedia — Турнир
- [1]