272
правки
Изменения
Нет описания правки
Одно из ребер <tex> (u, v_1) </tex> или <tex> (v_1, u) </tex> обязательно содержится в <tex> T </tex>.
Если ребро <tex> (u, v_1) \in ET </tex>, то путь <tex> (u \rightarrow P) </tex> {{- --}} гамильтонов.
[[Файл: Redei_kamion_4.png|250px|thumb|center|<font color=#ED1C24>Красным</font> цветом выделен искомый путь]]
Пусть теперь ребро <tex> (u, v_1) \notin ET, v_i </tex> {{- --}} первая вершина пути <tex> P </tex>, для которой ребро <tex> (u, v_i) \in T </tex>.
Если такая вершина существует, то в <tex> T </tex> существует ребро <tex> (v_{i - 1}, u) </tex> и путь <tex> (v_1 \rightarrow \ldots \rightarrow v_{i - 1} \rightarrow u \rightarrow v_i \rightarrow \ldots v_n) </tex> – гамильтонов.
[[Файл: Redei_kamion_5.png|250px|thumb|center|<font color=#ED1C24>Красным</font> цветом выделен искомый путь]]
Если такой вершины не существует, то путь <tex> (P \rightarrow u) </tex> {{- --}} гамильтонов.
[[Файл: Redei_kamion_6.png|250px|thumb|center|<font color=#ED1C24>Красным</font> цветом выделен искомый путь]]
В любом [[Отношение_связности,_компоненты_связности#.D0.A1.D0.B8.D0.BB.D1.8C.D0.BD.D0.B0.D1.8F_.D1.81.D0.B2.D1.8F.D0.B7.D0.BD.D0.BE.D1.81.D1.82.D1.8C|сильно связанном]] турнире есть [[Гамильтоновы_графы#.D0.9E.D1.81.D0.BD.D0.BE.D0.B2.D0.BD.D1.8B.D0.B5_.D0.BE.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|гамильтонов цикл]].
|proof=
Приведем доказательство по индукции по числу вершин в цикле. Пусть <tex> n </tex> {{- --}} количество вершин в графе.
<u> ''База индукции:'' </u>
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=
Пусть <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>,
* <tex> V_2 = \{ v_2 \in VT | (u, v_2) \in ET \} </tex>.
<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>,
[[Файл: Redei_kamion_2.png|250px|thumb|center|<font color=#ED1C24>Красным</font> цветом выделен цикл длины <tex> 3 </tex>]]
Цикл <tex> S_3: (u \rightarrow w_2 \rightarrow w_1 \rightarrow u) </tex> {{- --}} искомый цикл длины <tex> 3 </tex>, q.e.d.
}}
<u> Первый случай: </u>
Пусть <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>.
[[Файл: Redei_kamion_7.png|250px|thumb|center]]
