64
правки
Изменения
→Транзитивность
'''Переход индукции''' Пусть доказано для <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>, что этот путь единственный.
'''База индукции''' <tex>n = 1</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=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 = 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, </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>.
}}
