Изменения

|about = Теорема Редеи-Камиона (для пути )|statement= В любом [[Турниры|турнире ]] есть [[Гамильтоновы_графы#.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|гамильтонов путь]].

Докажем,что в любом турнире есть гамильтонов путь по индукции по числу вершин n.# <u> ''База индукции: n = 3 '' <br/u>  Очевидно, для <tex> n = 3 </tex> утверждение верно.# <u> ''Индукционный переход :'' <br/u> Предположим, что теорема верна  Пусть предположение верно для всех турниров с количеством вершин не более <tex> n вершинами</tex>. Рассмотрим турнир <tex> T </tex> с <tex> n + 1 </tex> вершинами.  Пусть <tex>v_0u </tex> – {{---}} произвольная вершина турнира <tex> T</tex>. Тогда турнир T – <tex>v_0T - u </tex> имеет <tex> n </tex> вершин, значит, в нем есть гамильтонов путь P: <tex>v_1v_2...P: (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_n) </tex> . [[Файл: Redei_kamion_1.png|150px|thumb|center]] Одно из ребер ( рёбер <tex>v_0</tex>(u, <tex>v_1) </tex> ) или ( <tex>(v_1, u) </tex>, обязательно содержится в <tex>v_0T </tex> ) обязательно содержится в T. Рассмотрим 3 случая: ## Ребро Если ребро <tex> ( v_0u, v_1 ) \in T ET </tex>. Тогда , то путь <tex>v_0v_1v_2...v_n(u \rightarrow P) </tex> является гамильтоновым{{---}} гамильтонов. [[Файл: Redei_kamion_2.png|150px|thumb|center|<font color=## Обозначим через ff2a2a>Красным</font> цветом выделен искомый путь]] Пусть теперь ребро <tex>(u, v_1) \notin ET, v_i</tex> первую вершину {{---}} первая вершина пути <tex> P</tex>, для которой ребро <tex> ( v_0u, v_i ) \in T </tex>,если .Если такая вершина есть. Тогда существует, то в <tex> T </tex> существует ребро ( <tex>(v_{i-1}</tex>, <tex>v_0u) </tex> ) <br> и путь <tex>(v_1...\rightarrow \ldots \rightarrow v_{i-1}v_0v_i...\rightarrow u \rightarrow v_i \rightarrow \ldots v_n) </tex>– {{---}} гамильтонов. [[Файл: Redei_kamion_3.png|180px|thumb|center|<font color=## ff2a2a>Красным</font> цветом выделен искомый путь]] Если такой вершины не существует, то путь <tex>v_i(P \rightarrow u) </tex> нет, тогда гамильтоновым путем будет {{---}} гамильтонов.[[Файл: Redei_kamion_4.png|150px|thumb|center|<texfont color=#ff2a2a>v_1v_2...v_nv_0Красным</texfont>.цветом выделен искомый путь]] ИтакЗначит, в любом случае в турнире существует гамильтонов путь, q.e.d.

|about = Теорема Редеи-Камиона (для цикла )|statement= В любом [[Отношение_связности,_компоненты_связности#.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|гамильтонов цикл]].

Докажем, что в любом сильно связанном турнире есть гамильтонов цикл, по индукции по длине цикла.# <u> ''База индукции: '' <br> Покажем, что в любом сильно связанном турнире T с n вершинами (n /u> {{Утверждение|statement= 3) есть орцикл длины 3. Выберем произвольную вершину Cильно связанный турнир <tex>v_0T </tex> и обозначим через из <tex>W</tex> множество всех вершин <tex>w</tex>, таких, что ребро <tex> ( v_0, w ) n \in T geqslant 3 </tex>, а через <tex>Z</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>z</tex>, таких, что ребро <tex> ( z, v_0 ) \in T 3 </tex>. Так как T сильно связан, то оба множества |proof=Пусть <tex>Wu </tex> и <tex>Z{{---}} произвольная вершина турнира </tex> не пусты и найдется ребро <tex> ( w', z' ) \in T </tex> , где <tex>w' \in W , z' \in Z</tex>. Тогда искомым циклом длины 3 будет Множество вершин <tex>v_0VT - u </tex>,распадается на <tex>w'2 </tex>,<tex>z'</tex>,<tex>v_0</tex>.# Индукционный переход <br> Покажем, что если турнир T с n вершинами имеет орцикл S = <tex>v_1v_2...v_kv_1</tex> длины k < n, то он имеет также орцикл длины k + 1. Рассмотрим 2 случаянепересекающихся множества:## Существует такая вершина * <tex>v_0 V_1 = \notin S </tex> и такая, что найдутся вершины <tex>u , w { v_1 \in S</tex> , такие, что ребра <tex> VT \mid ( v_0 v_1, u ) , ( w , v_0) \in T ET \} </tex>. Обозначим за <tex>v_1</tex> вершину из S, такую, что ребро * <tex> V_2 = \{ v_2 \in VT \mid ( v_1u, v_0 v_2) \in T ET \} </tex>. Пусть [[Файл: Redei_kamion_5.png|290px|thumb|center]] <tex>v_i</tex> – первая вершина при обходе контура S из <tex>v_1T </tex>сильно связен, для которой ребро <br> следовательно:# <tex> ( v_0, v_i ) V_1 \neq \in T </tex>. Тогда ребро ( <tex>v_{i-1}emptyset </tex>, иначе <tex>v_0</tex> ) также содержится в T. Поэтому <tex>v_1v_2...v</tex>_{<tex>i{{---1</tex>}<tex>v_0v_i...v_kv_1</tex> – искомый орцикл длины k+1.}} исток турнира## Пусть такой вершины <tex>v_0V_2 \neq \emptyset </tex> нет. Тогда разобьем вершины, не принадлежащие S, на два непересекающихся подмножества иначе <tex>W</tex> и <tex>Z</tex>, где <tex>Wv </tex> {{--- множество таких вершин }} сток турнира# <tex>w</tex> , что ребро \exists e = ( <tex>v_i</tex>w_2, <tex>w</tex> w_1) для любого <tex>i\in ET </tex> содержится в T, а иначе нет пути из <tex>ZV_2 </tex> – множество таких вершин в <tex>zV_1 </tex>, что ребро ( :#* <tex>zw_1 \in V_1 </tex>, #* <tex>v_iw_2 \in V_2 </tex> ) для любого <tex>i</tex> содержится в T. Так как T сильно связан, то оба множества [[Файл: Redei_kamion_6.png|290px|thumb|center|<texfont color=#ff2a2a>WКрасным</texfont> и цветом выделен цикл длины <tex>Z3 </tex> не пусты и найдется ребро ]] Цикл <tex> S_3: ( w', z' ) u \in T </tex> , где <tex>w' rightarrow w_2 \in W , z' rightarrow w_1 \in Zrightarrow u) </tex>. Тогда {{---}} искомый цикл длины <tex>v_1 w' z' v_3...v_k v_13 </tex> – требуемый орцикл, q.e.Таким образом в любом сильно связанном турнире T с n вершинами будет орцикл длины n, то есть гамильтонов циклd.

<u>'''Следствие'Индукционный переход:''</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>. Рассмотрим два случая:# существует такая вершина <tex> v_0 </tex>,# не существует такой вершины <tex> v_0 </tex>.Заметим, что при <tex> k = n - 1 </tex> такая вершина необходимо существует, так как иначе вершина, не входящая в цикл, будет являться либо стоком, либо истоком. <u> Первый случай: </u> Перенумеруем вершины <tex> S_k </tex> так, чтобы ребро <tex> e = (v_1, v_0) \in ET </tex> для вершины <tex> v_1 \in S_k </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|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> k + 1 </tex> ]] Тогда <tex> S_{k + 1} = (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_{i - 1} \rightarrow v_0 \rightarrow v_i \rightarrow \ldots \rightarrow v_k \rightarrow v_1) </tex> – искомый цикл длины <tex> k + 1 </tex>. <u> Второй случай: </u> Пусть:* <tex> V_1 = \{ u \in VT \mid u \notin S_k, e = (u, v_i) \in ET, \forall i = \overline{1, n} \} </tex>,* <tex> V_2 = \{ u \in VT \mid 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|290px|thumb|center]] Турнир сильно связен, следовательно:* <tex> V_1 \neq \emptyset </tex>, иначе <tex> T </tex> не будет сильно связным, так как тогда нет простых путей с началом в <tex> V_2 </tex> и концом в <tex> S_k </tex>* <brtex>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|290px|thumb|center|<font color=#ff2a2a>Красным</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>. В любом случае утверждение верно, q.e.d. }}Таким образом, любой сильно связанный турнир <tex> T </tex> с <tex> n \geqslant 3 </tex> вершинами содержит цикл длины <tex> n </tex>, то есть гамильтонов цикл, q.e.d.}} {{Теорема|about=Следствие|statement=

==Литература==[[Категория: Алгоритмы и структуры данных]]* Харари, Ф. Теория [[Категория: Обходы графов. — М.]][[Категория: Книжный дом «ЛИБРОКОМ», 2009Гамильтоновы графы]]