272
правки
Изменения
Нет описания правки
{{Утверждение
|statement=
Cильно связанный турнир <tex> T </tex> из <tex> n \geq 3 </tex> вершин содержит [[Основные_определения_теории_графов#.D0.9E.D1.80.D0.B8.D0.B5.D0.BD.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.BD.D1.8B.D0.B5_.D0.B3.D1.80.D0.B0.D1.84.D1.8B|орциклцикл]] длины <tex> 3 </tex>.
|proof=
[[Файл:Cycle.jpg|300px|thumb|right|<tex> S_3 </tex>]]
#* <tex> v'_1 \in V_1 </tex>,
#* <tex> v'_2 \in V_2 </tex>.
Цикл <tex> S_3: (u \rightarrow v'_2 \rightarrow v'_1 \rightarrow u) </tex> - искомый [[Основные_определения_теории_графов#.D0.9E.D1.80.D0.B8.D0.B5.D0.BD.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.BD.D1.8B.D0.B5_.D0.B3.D1.80.D0.B0.D1.84.D1.8B|орцикл]] цикл длины <tex> 3 </tex>, q.e.d.
}}
{{Утверждение
|statement=
Если сильно связанный турнир <tex> T </tex> из <tex> n \geq 3 </tex> вершин содержит орцикл цикл <tex> S_k </tex> длины <tex> k </tex>, то он содержит и цикл длины <tex> k + 1 </tex>.
|proof=
Пусть <tex> S_k = (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_k \rightarrow v_1) </tex>.
[[Файл:Cycle_k.jpg|300px|thumb|right|<tex> S_{k + 1} </tex>]]
: Пусть <tex> v_1 </tex> - вершина из <tex> S_k </tex> такая, что ребро <tex> e = (v_1, v_0 ) \in ET </tex>. Пусть <tex> v_i </tex> – первая вершина при обходе контура <tex> S_k </tex> из <tex> v_1 </tex>, для которой ребро <tex> f = (v_0, v_i ) \in ET </tex>.
: Тогда ребро <tex> g = (v_{i - 1}, v_0) \in ET </tex>.
: Тогда <tex> S_{k + 1} = (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_{i - 1} \rightarrow v_0 \rightarrow v_i \rightarrow \ldots \rightarrow v_k \rightarrow v_1) </tex> – искомый орцикл цикл длины <tex> k + 1 </tex>.
<u> Второй случай: </u>
:* <tex> U = \{ u \in VT | u \notin S, e = (v_i, u) \in ET, \forall i = \overline{1, n} \} </tex>,
:* <tex> W = \{ w \in VT | w \notin S, f = (w, v_i) \in ET, \forall i = \overline{1, n} \} </tex>,
:* Тогда <tex> U \cap W = \emptyset </tex>.
: Турнир сильно связен, следовательно:
:* <tex> U \neq \emptyset </tex>,
:** <tex> u' \in U </tex>,
:** <tex> w' \in W </tex>.
: Тогда <tex> S_{k + 1} = (v_1 \rightarrow u' \rightarrow w' \rightarrow v_3 \rightarrow \ldots \rightarrow v_k \rightarrow v_1) </tex> – искомый орцикл цикл длины <tex> k + 1 </tex>.
Цикл <tex> S_{k + 1} </tex> - искомый орцикл цикл длины <tex> k + 1 </tex>, q.e.d.
}}
Таким образом, в любой сильно связанный турнир <tex> T </tex> из <tex> n \geq 3 </tex> вершин содержит орцикл цикл длины <tex> n </tex>, то есть гамильтонов цикл, q.e.d.
}}
