272
правки
Изменения
Нет описания правки
[[Файл:Cycle_k2.jpg|300px|thumb|right|<tex> S_{k + 1} </tex>]]
: Пусть:
:* <tex> U V_1 = \{ u \in VT | u \notin S, e = (u, v_i, u) \in ET, \forall i = \overline{1, n} \} </tex>,:* <tex> W V_2 = \{ w u \in VT | w u \notin S, f = (wv_i, v_iu) \in ET, \forall i = \overline{1, n} \} </tex>,.: Тогда <tex> U V_1 \cap W V_2 = \emptyset </tex>.
: Турнир сильно связен, следовательно:
:* <tex> U V_1 \neq \emptyset </tex>,:* <tex> W V_2 \neq \emptyset </tex>,:* <tex> \exists g = (u'w_2, w'w_1) \in T: </tex>:** <tex> u' w_1 \in U V_1 </tex>,:** <tex> w' w_2 \in W V_2 </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>.
