Изменения

Приведем доказательство по индукции по числу вершинв графе. Пусть <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> ''База индукции:'' </u>

В турнире Cильно связанный турнир <tex> T </tex> есть орцикл из <tex> n \geqslant 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>.

Пусть <tex> u </tex> {{-- -}} произвольная вершина турнира <tex> T , </tex>. Множество вершин <tex> VT - u </tex> распадается на <tex> 2 </tex> непересекающихся множества:* <tex> V_1 = \{ v_1 \in VT | \mid (v_1, u, v_1) \in ET \}</tex>, * <tex> V_2 = \{ v_2 \in VT | \mid (u, v_2, u) \in ET \} </tex>.[[Файл: Redei_kamion_5.png|290px|thumb|center]]

# <tex> V_1 \neq \emptyset </tex>, иначе <tex> v </tex> {{---}} исток турнира# <tex> V_2 \neq \emptyset </tex>, иначе <tex> v </tex> {{---}} сток турнира#<tex> \exists e = (v'_1w_2, v'_2w_1) \in ET : </tex>, иначе нет пути из <tex> V_2 </tex> в <tex> V_1 </tex>:#* <tex> v'_1 w_1 \in V_1 </tex>,#* <tex> v'_2 w_2 \in V_2 </tex>.[[Файл: Redei_kamion_6.png|290px|thumb|center|<font color=#ff2a2a>Красным</font> цветом выделен цикл длины <tex> 3 </tex>]] Цикл <tex> PS_3: (u \rightarrow v'_1 w_2 \rightarrow v'_2 w_1 \rightarrow u) </tex> {{--- }} искомый орцикл цикл длины <tex> 3 </tex>, q.e.d.

Покажем, что если {{Утверждение|statement=Если сильно связанный турнир <tex> T </tex> с из <tex>n\geqslant 3 </tex> вершинами имеет орцикл вершин содержит цикл <tex> S = v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_k \rightarrow v_1 S_k </tex> длины <tex> k, (k < n )</tex>, то он имеет также орцикл содержит и цикл длины <tex>k + 1</tex>. Рассмотрим 2 случая:# Существует такая вершина |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 S_k </tex> такаяи верно, что найдутся вершины <tex>\exists u , w \in SS_k </tex> , такие, что ребра :* <tex> (v_0 , u) \in ET </tex>, * <tex> (w , v_0) \in T ET </tex>. Обозначим за  Рассмотрим два случая:# существует такая вершина <tex>v_1v_0 </tex> вершину из ,# не существует такой вершины <tex>Sv_0 </tex>.Заметим, такуючто при <tex> k = n - 1 </tex> такая вершина необходимо существует, что так как иначе вершина, не входящая в цикл, будет являться либо стоком, либо истоком. <u> Первый случай: </u> Перенумеруем вершины <tex> S_k </tex> так, чтобы ребро <tex> e = ( v_1, v_0 ) \in T ET </tex> для вершины <tex> v_1 \in S_k </tex>. Пусть <tex>v_i</tex> – первая вершина при обходе контура <tex>SS_k </tex> из <tex>v_1</tex>, для которой ребро <tex> f = ( v_0, v_i ) \in T ET </tex>. [[Файл: Redei_kamion_7.png|150px|thumb|center]] Тогда ребро <tex>g = (v_{i-1}, v_0)\in ET </tex> также содержится в .[[Файл: Redei_kamion_8.png|150px|thumb|center|<font color=#ff2a2a>Красным</font> цветом выделен искомый цикл длины <tex>Tk + 1 </tex>. Поэтому ]] Тогда <tex>v_1v_2...S_{k + 1} = (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_{i-1}v_0v_i...v_kv_1\rightarrow v_0 \rightarrow v_i \rightarrow \ldots \rightarrow v_k \rightarrow v_1) </tex> – искомый орцикл цикл длины <tex>k+1</tex>.# <u> Второй случай: </u> Пусть такой вершины :* <tex>v_0V_1 = \{ u \in VT \mid u \notin S_k, e = (u, v_i) \in ET, \forall i = \overline{1, n} \} </tex> нет. Тогда разобьем вершины, не принадлежащие * <tex>SV_2 = \{ u \in VT \mid u \notin S_k, f = (v_i, u) \in ET, \forall i = \overline{1, n} \} </tex>, на два непересекающихся подмножества .Тогда <tex>WV_1 \cap V_2 = \emptyset </tex> и .[[Файл: Redei_kamion_9.png|290px|thumb|center]] Турнир сильно связен, следовательно:* <tex>ZV_1 \neq \emptyset </tex>, где иначе <tex>WT </tex> - множество таких вершин не будет сильно связным, так как тогда нет простых путей с началом в <tex>wV_2 </tex> , что ребро и концом в <tex>(v_i, w)S_k </tex> для любого * <tex>iV_2 \neq \emptyset </tex> содержится в , иначе <tex>T</tex>не будет сильно связным, а так как тогда нет простых путей с началом в <tex>ZS_k </tex> – множество таких вершин и концом в <tex>zV_1 </tex>, что ребро * <tex>\exists g = (zw_2, v_iw_1)\in ET </tex> для любого , иначе <tex>iT </tex> содержится не будет сильно связным, так как тогда нет простых путей с началом в <tex>TV_2 </tex>. Так как и концом в <tex>TV_1 </tex> сильно связан, то оба множества ):** <tex>Ww_1 \in V_1 </tex> и ,** <tex>Zw_2 \in V_2 </tex> не пусты и найдется ребро .[[Файл: Redei_kamion_10.png|290px|thumb|center|<texfont color=#ff2a2a> (w', z') \in T Красным</texfont> , где цветом выделен цикл длины <tex>w' \in W , z' \in Zk + 1 </tex>. ]]Тогда <tex>S_{k + 1} = (v_1 w' z' \rightarrow w_2 \rightarrow w_1 \rightarrow v_3...\rightarrow \ldots \rightarrow v_k \rightarrow v_1) </tex> – требуемый орциклискомый цикл длины <tex> k + 1 </tex>. В любом случае утверждение верно, q.e.d. }}Таким образом в любом , любой сильно связанном турнире связанный турнир <tex>T</tex> с <tex>n\geqslant 3 </tex> вершинами будет орцикл содержит цикл длины <tex>n</tex>, то есть гамильтонов цикл, q.e.d.

{{ЛеммаТеорема

== Литература См. также==* [[Гамильтоновы графы]]* [[Турниры]] == Источники информации ==