272
правки
Изменения
Нет описания правки
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_3.png|200px150px|thumb|right|<tex> S_3 </tex>]]
Пусть <tex> u </tex> - произвольная вершина турнира <tex> T </tex>. Множество вершин <tex> VT - u </tex> распадается на <tex> 2 </tex> непересекающихся множества:
* <tex> V_1 = \{ v_1 \in VT | (v_1, u) \in ET \} </tex>,
<u> Первый случай: </u>
[[Файл:cycle_k+1-1.png|250px150px|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>.
<u> Второй случай: </u>
[[Файл:Cycle_k2cycle_k+1-2.jpgpng|300px150px|thumb|right|<tex> S_{k + 1} во втором случае. </tex>]]
: Пусть:
:* <tex> V_1 = \{ u \in VT | u \notin S, e = (u, v_i) \in ET, \forall i = \overline{1, n} \} </tex>,
