Изменения

Приведем доказательство по индукции по числу вершинв графе. Пусть <tex> n </tex> {{- --}} количество вершин в графе.

<u> ''База индукции:'' </u>

Пусть <tex> u </tex> – {{---}} произвольная вершина турнира <tex> T </tex>. Тогда турнир <tex> T - u </tex> имеет <tex> n </tex> вершин, значит, в нем есть гамильтонов путь <tex> P: (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_n ) </tex>. [[Файл: Redei_kamion_1.png|150px|thumb|center]] Одно из ребер рёбер <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_2.png|150px|thumb|center|<font color=# Ребро ff2a2a>Красным</font> цветом выделен искомый путь]] Пусть теперь ребро <tex> (u, v_1) \notin ET </tex>. Пусть <tex> , 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_3.png|180px|thumb|center|<font color=## ff2a2a>Красным</font> цветом выделен искомый путь]] Если такой вершины не существует, то путь <tex> (P \rightarrow u ) </tex> {{-- -}} гамильтонов.[[Файл: Redei_kamion_4.png|150px|thumb|center|<font color=#ff2a2a>Красным</font> цветом выделен искомый путь]] 

Докажем, что в любом сильно связанном турнире есть гамильтонов цикл, Приведем доказательство по индукции по длине циклачислу вершин в цикле. Пусть <tex> n </tex> {{---}} количество вершин в графе.

<u> ''База индукции:'' <br> Покажем, что в любом сильно связанном турнире <tex>T</tex> с <tex>n</tex> вершинами <tex>n \ge 3</tex> есть орцикл длины 3. Выберем произвольную вершину <tex>v_0</tex> и обозначим через <tex>W</tex> множество всех вершин <tex>w</tex>, таких, что ребро <tex>(v_0, w) \in T </tex>, а через <tex>Z</tex> – множество всех вершин <tex>z</tex>, таких, что ребро <tex>(z, v_0) \in T </tex>. Так как <tex>T</tex> сильно связан, то оба множества <tex>W</tex> и <tex>Z</tex> не пусты и найдется ребро <tex>(w', z') \in T </tex> , где <tex>w' \in W, z' \in Z</tex>. Тогда искомым циклом длины 3 будет <tex>v_0</tex>,<tex>w'</tex>,<tex>z'</tex>,<tex>v_0</texu>.

''Индукционный переход:'' <br> Покажем, что если {{Утверждение|statement=Cильно связанный турнир <tex>T</tex> с из <tex>n\geqslant 3 </tex> вершинами имеет орцикл <tex>S = v_1v_2вершин содержит [[Основные_определения_теории_графов#.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.v_kv_1</tex> 8B|цикл]] длины <tex>k < n</tex>, то он имеет также орцикл длины <tex>k + 13 </tex>. Рассмотрим 2 случая:# Существует такая вершина <tex>v_0 \notin S </tex> такая, что найдутся вершины |proof=Пусть <tex>u , w \in S</tex> , такие, что ребра {{---}} произвольная вершина турнира <tex> (v_0 , u) , (w , v_0) \in T </tex>. Обозначим за Множество вершин <tex>v_1VT - u </tex> вершину из распадается на <tex>S2 </tex>, такую, что ребро непересекающихся множества:* <tex> V_1 = \{ v_1 \in VT \mid ( v_1, v_0 u) \in T </tex>. Пусть <tex>v_i</tex> – первая вершина при обходе контура <tex>S</tex> из <tex>v_1ET \} </tex>, для которой ребро * <tex> V_2 = \{ v_2 \in VT \mid ( v_0u, v_i v_2) \in T </tex>. Тогда ребро <tex>(v_{i-1ET \}, v_0)</tex> также содержится в <tex>T</tex>. Поэтому <tex>v_1v_2[[Файл: Redei_kamion_5...v_{i-1}v_0v_i...v_kv_1png|290px|thumb|center]] </tex> – искомый орцикл длины <tex>k+1T </tex>.сильно связен, следовательно:# Пусть такой вершины <tex>v_0V_1 \neq \emptyset </tex> нет. Тогда разобьем вершины, не принадлежащие иначе <tex>Sv </tex>, на два непересекающихся подмножества {{---}} исток турнира# <tex>W</tex> и <tex>ZV_2 \neq \emptyset </tex>, где иначе <tex>Wv </tex> {{--- множество таких вершин <tex>w</tex> , что ребро }} сток турнира# <tex>\exists e = (v_iw_2, ww_1)</tex> для любого <tex>i</tex> содержится в <tex>T\in ET </tex>, а <tex>Z</tex> – множество таких вершин иначе нет пути из <tex>zV_2 </tex>, что ребро <tex>(z, v_i)</tex> для любого <tex>i</tex> содержится в <tex>TV_1 </tex>. Так как <tex>T:#* </tex> сильно связан, то оба множества <tex>W</tex> и <tex>Z</tex> не пусты и найдется ребро <tex> (w', z') w_1 \in T V_1 </tex> , где #* <tex>w' \in W , z' w_2 \in ZV_2 </tex>. Тогда [[Файл: Redei_kamion_6.png|290px|thumb|center|<texfont color=#ff2a2a>v_1 w' z' v_3...v_k v_1Красным</texfont> – требуемый орцикл.Таким образом в любом сильно связанном турнире цветом выделен цикл длины <tex>T3 </tex> с ]] Цикл <tex>nS_3: (u \rightarrow w_2 \rightarrow w_1 \rightarrow u) </tex> вершинами будет орцикл {{---}} искомый цикл длины <tex>n3 </tex>, то есть гамильтонов циклq.e.d.

<u> '''Следствие'Индукционный переход:''<br/u> {{Утверждение|statement=Если сильно связанный турнир <tex> T </tex> из <tex> n \geqslant 3 </tex> вершин содержит цикл <tex> S_k </tex> длины <tex> k, (k < n)</tex>, то он содержит и цикл длины <tex> k + 1 </tex>.|proof=Пусть <tex> S_k = (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_k \rightarrow v_1) </tex>. Пусть <tex> v_0 : v_0 \notin S_k </tex> и верно, что <tex> \exists u, w \in S_k </tex>:* <tex> (v_0, u) \in ET </tex>,* <tex> (w, v_0) \in ET </tex>.

== Литература Источники информации ==