Изменения

Приведем доказательство по индукции по числу вершинв графе. Пусть <tex> n </tex> - количество вершин в графе.

Приведем доказательство по индукции по числу вершинв цикле. Пусть <tex> n </tex> - количество вершин в графе.

В турнире Cильно связанный турнир <tex> T </tex> есть из <tex> n \geq 3 </tex> вершин содержит орцикл длины <tex> 3 </tex>.

Цикл <tex> PS_3: (u \rightarrow v'_1 \rightarrow v'_2 \rightarrow u) </tex> - искомый орцикл длины <tex> 3 </tex>, q.e.d.

Покажем, что если {{Утверждение|statement=Если сильно связанный турнир <tex> T </tex> с из <tex>n\geq 3 </tex> вершинами имеет вершин содержит орцикл <tex> S = v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_k \rightarrow v_1 S_k </tex> длины <tex> k < n </tex>, то он имеет также орцикл содержит и цикл длины <tex>k + 1</tex>. Рассмотрим 2 случая:# Существует такая вершина |proof=Пусть <tex> S_k = (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_k \rightarrow v_1) </tex>.Пусть <tex>v_0 \notin S </tex> такая, что найдутся вершины <tex>\exists u , w \in S</tex> , такие, что ребра :* <tex> (v_0 , u) , \in ET </tex>* <tex> (w , v_0) \in T ET </tex>.# Существует такая вершина <tex> v_0 </tex>. Обозначим за <br> Пусть <tex>v_1</tex> вершину - вершина из <tex>S</tex>, такуютакая, что ребро <tex> e = ( v_1, v_0 ) \in T ET </tex>. Пусть <tex>v_i</tex> – первая вершина при обходе контура <tex>S</tex> из <tex>v_1</tex>, для которой ребро <tex> f = ( v_0, v_i ) \in T ET </tex>. Тогда ребро <tex>g = (v_{i-1}, v_0)</tex> также содержится в <tex>T</tex>. Поэтому <br> Тогда <tex>v_1v_2...S_{k + 1} = (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_{i-1}v_0v_i...v_kv_1\rightarrow v_0 \rightarrow v_i \rightarrow \ldots \rightarrow v_k \rightarrow v_1) </tex> – искомый орцикл длины <tex>k+1</tex>.# Пусть Не существует такой вершины <tex>v_0</tex> нет. Тогда разобьем вершины, не принадлежащие : Пусть::* <tex>U = \{ u \in VT | u \notin S</tex>, на два непересекающихся подмножества <tex>We = (v_i, u) \in ET, \forall i = \overline{1, n} \} </tex> и <tex>Z</tex>, где :* <tex>W</tex> - множество таких вершин <tex>= \{ w \in VT | w</tex> \notin S, что ребро <tex>f = (w, v_i) \in ET, w)</tex> для любого <tex>\forall i= \overline{1, n} \} </tex> содержится в :* <tex>TU \cap W = \emptyset </tex>: Турнир сильно связен, а следовательно::* <tex>ZU \neq \emptyset </tex> – множество таких вершин :* <tex>zW \neq \emptyset </tex>, что ребро :* <tex>\exists g = (zu', v_iw')\in T: </tex> для любого :** <tex>iu' \in U </tex> содержится в :** <tex>Tw' \in W </tex>. Так как : Тогда <tex>TS_{k + 1} = (v_1 \rightarrow u' \rightarrow w' \rightarrow v_3 \rightarrow \ldots \rightarrow v_k \rightarrow v_1</tex> сильно связан, то оба множества – искомый орцикл длины <tex>Wk + 1 </tex> и . Цикл <tex>ZS_{k + 1} </tex> не пусты и найдется ребро - искомый орцикл длины <tex> (w', z') \in T k + 1 </tex> , где <tex>w' \in W , z' \in Z</tex>q. Тогда <tex>v_1 w' z' v_3e.d..v_k v_1</tex> – требуемый орцикл. }}Таким образом , в любом любой сильно связанном турнире связанный турнир <tex>T</tex> с из <tex>n\geq 3 </tex> вершинами будет вершин содержит орцикл длины <tex>n</tex>, то есть гамильтонов цикл, q.e.d.