Изменения

|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> вершинами.  Пусть <mathtex>v_0u </mathtex> – {{---}} произвольная вершина турнира <tex> T</tex>. Тогда турнир T – <mathtex>v_0T - u </mathtex> имеет <tex> n </tex> вершин, значит, в нем есть гамильтонов путь <tex> P: <math>v_1v_2...(v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_n) </mathtex> . [[Файл: Redei_kamion_1.png|150px|thumb|center]] Одно из ребер ( рёбер <math>v_0</mathtex>(u, <math>v_1) </mathtex> ) или ( <mathtex>(v_1, u) </mathtex>, обязательно содержится в <mathtex>v_0T </mathtex> ) обязательно содержится в T. Рассмотрим 3 случая: ## Ребро Если ребро <mathtex> ( v_0u, v_1 ) \in T ET </mathtex>. Тогда , то путь <mathtex>v_0v_1v_2(u \rightarrow P) </tex> {{---}} гамильтонов.[[Файл: Redei_kamion_2..v_npng|150px|thumb|center|<font color=#ff2a2a>Красным</mathfont> является гамильтоновым. цветом выделен искомый путь]] ## Обозначим через Пусть теперь ребро <mathtex>(u, v_1) \notin ET, v_i</mathtex> первую вершину {{---}} первая вершина пути <tex> P</tex>, для которой ребро <mathtex> ( v_0u, v_i ) \in T </mathtex>,если .Если такая вершина есть. Тогда существует, то в T существует ребро ( <mathtex>vT </mathtex>существует ребро _{<mathtex>(v_{i-1</math>}}, <math>v_0u) </math> ) <brtex> и путь <mathtex>(v_1...v</math>_{<math>\rightarrow \ldots \rightarrow v_{i-1} \rightarrow u \rightarrow v_i \rightarrow \ldots v_n) </mathtex>{{---}} гамильтонов.[[Файл: Redei_kamion_3.png|180px|thumb|center|}<mathfont color=#ff2a2a>v_0v_i...v_nКрасным</mathfont>– гамильтонов. цветом выделен искомый путь]] ## Если такой вершины не существует, то путь <mathtex>v_i(P \rightarrow u) </mathtex> нет, тогда гамильтоновым путем будет {{---}} гамильтонов.[[Файл: Redei_kamion_4.png|150px|thumb|center|<mathfont color=#ff2a2a>v_1v_2...v_nv_0Красным</mathfont>.цветом выделен искомый путь]] ИтакЗначит, в любом случае в турнире существует гамильтонов путь, 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ильно связанный турнир <mathtex>v_0T </mathtex> и обозначим через из <mathtex>Wn \geqslant 3 </mathtex> множество всех вершин содержит [[Основные_определения_теории_графов#.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|цикл]] длины <mathtex>w3 </mathtex>, таких, что ребро .|proof=Пусть <mathtex> ( v_0, w ) \in T u </mathtex>, а через {{---}} произвольная вершина турнира <mathtex>ZT </mathtex> – множество всех . Множество вершин <mathtex>zVT - u </mathtex>, таких, что ребро распадается на <mathtex> ( z, v_0 ) \in T 2 </mathtex>. Так как T сильно связан, то оба непересекающихся множества :* <math>W</math> и <math>Z</math> не пусты и найдется ребро <mathtex> V_1 = \{ v_1 \in VT \mid ( w'v_1, z' u) \in T ET \} </mathtex> , где * <mathtex>w' V_2 = \{ v_2 \in W VT \mid (u, z' v_2) \in ZET \} </mathtex>. Тогда искомым циклом длины 3 будет <math>v_0</math>,<math>w'</math>,<math>z'</math>,<math>v_0</math>[[Файл: Redei_kamion_5.png|290px|thumb|center]] # Индукционный переход <brtex> Покажем, что если турнир T с n вершинами имеет орцикл S = <math>v_1v_2...v_kv_1</mathtex> длины k < nсильно связен, то он имеет также орцикл длины k + 1. Рассмотрим 2 случаяследовательно:## Существует такая вершина <mathtex>v_0 V_1 \neq \notin S emptyset </mathtex> и такая, что найдутся вершины иначе <mathtex>u , w \in Sv </mathtex> , такие, что ребра {{---}} исток турнира# <mathtex> ( v_0 , u ) , ( w , v_0) V_2 \in T </math>. Обозначим за <math>v_1</math> вершину из S, такую, что ребро <math> ( v_1, v_0 ) neq \in T </math>. Пусть <math>v_iemptyset </math> – первая вершина при обходе контура S из <math>v_1</mathtex>, для которой ребро <br> иначе <math> ( v_0, v_i ) \in T </math>. Тогда ребро ( <mathtex>v</mathtex>_{<math>i{{--1</math>}, <math>v_0</math> ) также содержится в T. Поэтому <math>v_1v_2...v</math>_{<math>i-1</math>}<math>v_0v_i...v_kv_1</math> – искомый орцикл длины k+1.}} сток турнира## Пусть такой вершины <mathtex>v_0</math> нет. Тогда разобьем вершины, не принадлежащие S, на два непересекающихся подмножества <math>W</math> и <math>Z</math>, где <math>W</math> - множество таких вершин <math>w</math> , что ребро \exists e = ( <math>v_i</math>w_2, <math>w</math> w_1) для любого <math>i\in ET </mathtex> содержится в T, а иначе нет пути из <mathtex>ZV_2 </mathtex> – множество таких вершин в <mathtex>zV_1 </mathtex>, что ребро ( :#* <mathtex>zw_1 \in V_1 </mathtex>, #* <mathtex>v_iw_2 \in V_2 </mathtex> ) для любого <math>i</math> содержится в T. Так как T сильно связан, то оба множества [[Файл: Redei_kamion_6.png|290px|thumb|center|<mathfont color=#ff2a2a>WКрасным</mathfont> и цветом выделен цикл длины <mathtex>Z3 </mathtex> не пусты и найдется ребро ]] Цикл <mathtex> S_3: ( w', z' ) u \in T </math> , где <math>w' rightarrow w_2 \in W , z' rightarrow w_1 \in Zrightarrow u) </mathtex>. Тогда {{---}} искомый цикл длины <mathtex>v_1 w' z' v_3...v_k v_13 </mathtex> – требуемый орцикл, q.Таким образом в любом сильно связанном турнире T с n вершинами будет орцикл длины n, то есть гамильтонов циклe.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Гамильтоновы графы]]