64
правки
Изменения
→Транзитивность
|id=theorem1
|statement=
Пусть <tex>T=\langle V, E\rangle</tex> — турнир, <tex>\vert | V \vert | = n</tex>. Тогда следующие утверждения эквивалентны:
#<tex>T</tex> транзитивен;
#<tex>T</tex> не содержит циклов длины <tex>3</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>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>.
