272
правки
Изменения
Нет описания правки
Cильно связанный турнир <tex> T </tex> из <tex> n \geq 3 </tex> вершин содержит орцикл длины <tex> 3 </tex>.
|proof=
[[Файл:Cycle.jpg|200px|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, v_1) \in ET \}</tex>, * <tex> V_2 = \{ v_2 \in VT | (u, v_2, u) \in ET \} </tex>.
<tex> T </tex> сильно связен, следовательно:
# <tex> V_1 \neq \emptyset </tex>, иначе у турнира существует исток.# <tex> V_2 \neq \emptyset </tex>, иначе у турнира существует сток.#<tex> \exists e = (v'_1_2, v'_2_1) \in ET : </tex>:#* <tex> v'_1 \in V_1 </tex>,#* <tex> v'_2 \in V_2 </tex>.Цикл <tex> S_3: (u \rightarrow v'_1 _2 \rightarrow v'_2 _1 \rightarrow u) </tex> - искомый орцикл длины <tex> 3 </tex>, q.e.d.
}}
