Изменения

Следующие утверждения для <tex>2 \Rightarrow 3:</tex> Пусть в графе содержится цикл длины <tex>k \neq 3</tex>. Это не может быть цикл длины <tex>2</tex> (противоречит определению турнира ). Обозначим его вершины в порядке обхода <tex>Tv_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>nk = 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>T(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> ацикличен. Докажем индукцией по n. '''База индукции''' <tex>n = 1</tex>: верно,т.к. есть одна вершина степени <tex>0</tex>  *'''Переход индукции''' Пусть доказано для <tex>Tn - 1</tex>. В ациклическом графе существует сток <tex>t, deg^{+}(t) = 0</tex> не содержит циклов длины . Рассмотрим граф <tex>3T-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>T</tex> он будет единственным. <tex>5 \Rightarrow 1: </tex> Пусть <tex>P=\{ 0v_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, 2k \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>Tm = 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, (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> содержит ровно один гамильтонов путь.}}