Изменения

|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|гамильтонов путь]].

Докажем,что в любом турнире есть гамильтонов путь по индукции по числу вершин <texu>n''База индукции:'' </texu>.

''База индукции:'' <br> Очевидно, для <tex>n = 3</tex> утверждение верно.

<u> ''Индукционный переход:'' <br/u> Предположим, что теорема верна  Пусть предположение верно для всех турниров с количеством вершин не более <tex>n</tex> вершинами. Рассмотрим турнир <tex>T</tex> с <tex>n + 1</tex> вершинами.  Пусть <tex>v_0u </tex> – {{---}} произвольная вершина турнира <tex>T</tex>. Тогда турнир <tex>T</tex> – <tex>v_0- u </tex> имеет <tex>n</tex> вершин, значит, в нем есть гамильтонов путь <tex>P</tex>: <tex>v_1v_2...(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</tex>, <tex>v_0u) </tex> ) обязательно содержится в <tex>T</tex>. Рассмотрим 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> ( v_0u, v_1 ) \notin T </tex>. Обозначим через <tex>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|гамильтонов цикл]].

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

''База индукции:'' <br> Покажем, что в любом сильно связанном турнире <tex>T</tex> с сильно связен, следовательно:# <tex>n</tex> вершинами <tex>n V_1 \neq \ge 3emptyset </tex> есть орцикл длины 3. Выберем произвольную вершину , иначе <tex>v_0v </tex> и обозначим через {{---}} исток турнира# <tex>W</tex> множество всех вершин <tex>w</tex>, таких, что ребро <tex>(v_0, w) V_2 \neq \in T emptyset </tex>, а через иначе <tex>Zv </tex> – множество всех вершин <tex>z</tex>, таких, что ребро {{---}} сток турнира# <tex>\exists e = (zw_2, v_0w_1) \in T ET </tex>. Так как <tex>T</tex> сильно связан, то оба множества иначе нет пути из <tex>WV_2 </tex> и в <tex>ZV_1 </tex> не пусты и найдется ребро :#* <tex>(w', z') w_1 \in T V_1 </tex> , где #* <tex>w' \in W, z' w_2 \in ZV_2 </tex>. Тогда искомым циклом длины 3 будет [[Файл: Redei_kamion_6.png|290px|thumb|center|<texfont color=#ff2a2a>v_0Красным</texfont>,цветом выделен цикл длины <tex>w'3 </tex>,<tex>z'</tex>,<tex>v_0</tex>.]]

''Индукционный переход:'' <br> Покажем, что если турнир <tex>T</tex> с <tex>n</tex> вершинами имеет орцикл <tex>S = v_1v_2...v_kv_1</tex> длины <tex>k < nЦикл </tex>, то он имеет также орцикл длины <tex>k + 1</tex>. Рассмотрим 2 случаяS_3:# Существует такая вершина <tex>v_0 \notin S </tex> такая, что найдутся вершины <tex>(u , w \in S</tex> , такие, что ребра <tex> (v_0 , u) , (w , v_0) rightarrow w_2 \in T </tex>. Обозначим за <tex>v_1</tex> вершину из <tex>S</tex>, такую, что ребро <tex> ( v_1, v_0 ) rightarrow w_1 \in T </tex>. Пусть <tex>v_i</tex> – первая вершина при обходе контура <tex>S</tex> из <tex>v_1</tex>, для которой ребро <tex> ( v_0, v_i rightarrow u) \in T </tex>. Тогда ребро <tex>(v_{i{---1}, v_0)</tex> также содержится в <tex>T</tex>. Поэтому <tex>v_1v_2...v_{i-1}v_0v_i...v_kv_1</tex> – искомый орцикл цикл длины <tex>k+13 </tex>.# Пусть такой вершины <tex>v_0</tex> нет. Тогда разобьем вершины, не принадлежащие <tex>S</tex>, на два непересекающихся подмножества <tex>W</tex> и <tex>Z</tex>, где <tex>W</tex> - множество таких вершин <tex>w</tex> , что ребро <tex>(v_i, w)</tex> для любого <tex>i</tex> содержится в <tex>T</tex>, а <tex>Z</tex> – множество таких вершин <tex>z</tex>, что ребро <tex>(z, v_i)</tex> для любого <tex>i</tex> содержится в <tex>T</tex>q. Так как <tex>T</tex> сильно связан, то оба множества <tex>W</tex> и <tex>Z</tex> не пусты и найдется ребро <tex> (w', z') \in T </tex> , где <tex>w' \in W , z' \in Z</tex>e. Тогда <tex>v_1 w' z' v_3...v_k v_1</tex> – требуемый орцикл.Таким образом в любом сильно связанном турнире <tex>T</tex> с <tex>n</tex> вершинами будет орцикл длины <tex>n</tex>, то есть гамильтонов цикл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>. Рассмотрим два случая:# существует такая вершина <tex> v_0 </tex>,# не существует такой вершины <tex> v_0 </tex>.Заметим, что при <tex> k = n - 1 </tex> такая вершина необходимо существует, так как иначе вершина, не входящая в цикл, будет являться либо стоком, либо истоком. <u> Первый случай: </u>

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