272
правки
Изменения
Нет описания правки
<tex> T </tex> сильно связен, следовательно:
# <tex> V_1 \neq \emptyset </tex>, (иначе <tex> v </tex> {{---}} исток турнира)# <tex> V_2 \neq \emptyset </tex>, (иначе <tex> v </tex> {{---}} сток турнира)# <tex> \exists e = (w_2, w_1) \in ET </tex>, (иначе нет пути из <tex>V_2</tex> в <tex>V_1</tex>):
#* <tex> w_1 \in V_1 </tex>,
#* <tex> w_2 \in V_2 </tex>.
* <tex> V_2 = \{ u \in VT | u \notin S_k, f = (v_i, u) \in ET, \forall i = \overline{1, n} \} </tex>.
Тогда <tex> V_1 \cap V_2 = \emptyset </tex>.
[[Файл: Redei_kamion_9.png|250px350px|thumb|center]]
Турнир сильно связен, следовательно:
* <tex> V_1 \neq \emptyset </tex>, (иначе <tex> T </tex> не будет сильно связным, так как тогда нет простых путей с началом в <tex> V_2 </tex> и концом в <tex> S_k </tex>)* <tex> V_2 \neq \emptyset </tex>, (иначе <tex> T </tex> не будет сильно связным, так как тогда нет простых путей с началом в <tex> S_k </tex> и концом в <tex> V_1 </tex>)* <tex> \exists g = (w_2, w_1) \in ET </tex>, (иначе <tex>T</tex> не будет сильно связным, так как тогда нет простых путей с началом в <tex>V_2</tex> и концом в <tex>V_1</tex>):
** <tex> w_1 \in V_1 </tex>,
** <tex> w_2 \in V_2 </tex>.
[[Файл: Redei_kamion_10.png|250px350px|thumb|center|<font color=#ED1C24>Красным</font> цветом выделен цикл длины <tex> k + 1 </tex>]]
Тогда <tex> S_{k + 1} = (v_1 \rightarrow w_2 \rightarrow w_1 \rightarrow v_3 \rightarrow \ldots \rightarrow v_k \rightarrow v_1) </tex> – искомый цикл длины <tex> k + 1 </tex>.
