Изменения

|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_0(u, v_1) \in ET </mathtex>, то путь <mathtex>v_1(u \rightarrow P) </mathtex> ) принадлежит Т {{---}} гамильтонов.[[Файл: Redei_kamion_2. Тогда путь png|150px|thumb|center|<mathfont color=#ff2a2a>v_0v_1v_2...v_nКрасным</mathfont> является гамильтоновым. цветом выделен искомый путь]] ## Обозначим через Пусть теперь ребро <mathtex>(u, v_1) \notin ET, v_i</mathtex> первую вершину {{---}} первая вершина пути <tex> P</tex>, для которой ребро ( <math>v_0</mathtex>(u, <math>v_i) \in T </mathtex> ) принадлежит T ,если .Если такая вершина есть. Тогда существует, то в 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|гамильтонов цикл]].

Докажем, что в любом сильно связанном турнире есть гамильтонов цикл, по индукции по длине цикла.# База индукции: Цикл <brtex> Покажем, что в любом сильно связанном турнире T с n вершинами S_3: (n >= 3) есть орцикл длины 3. Выберем произвольную вершину <math>v_0</math> и обозначим через <math>W</math> множество всех вершин <math>w</math>, таких, что ребро ( <math>v_0</math>, <math>w</math> ) в T, а через <math>Z</math> – множество всех вершин <math>z</math>, таких, что ребро ( <math>z</math>, <math>v_0</math> ) в T. Так как T сильно связан, то оба множества <math>W</math> и <math>Z</math> не пусты и найдется ребро ( <math>w'</math>, <math>z'</math> ) , где <math>w'</math> принадлежит <math>W</math>, <math>z'</math> принадлежит <math>Z</math>. Тогда искомым циклом длины 3 будет <math>v_0</math>,<math>w'</math>,<math>z'</math>,<math>v_0</math>.# Индукционный переход <br> Покажем, что если турнир T с n вершинами имеет орцикл S = <math>v_1v_2...v_kv_1</math> длины k < n, то он имеет также орцикл длины k + 1. Рассмотрим 2 случая:## Существует такая вершина <math>v_0</math> , не принадлежащая орциклу S и такая, что найдутся вершины <math>u</math> и <math>w</math>, принадлежащие орциклу S, такие, что ребра ( <math>v_0</math>, <math>\rightarrow w_2 \rightarrow w_1 \rightarrow u</math> ) и ( <math>w</mathtex>, <math>v_0</math> ) содержатся в T. Обозначим за <math>v_1</math> вершину из S, такую, что ребро ( <math>v_1</math>, <math>v_0</math> ) содержится в T. Пусть <math>v_i</math> – первая вершина при обходе контура S из <math>v_1</math>, для которой ребро <br> ( <math>v_0</math>, <math>v_i</math> ) принадлежит Т. Тогда ребро ( <math>v</math>_{<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> , что ребро ( <math>v_i</math>, <math>w</math> ) для любого <math>i3 </mathtex> содержится в T, а <math>Z</math> – множество таких вершин <math>z</math>, что ребро ( <math>z</math>, <math>v_i</math> ) для любого <math>i</math> содержится в Tq. Так как T сильно связан, то оба множества <math>W</math> и <math>Z</math> не пусты и найдется ребро ( <math>w'</math>, <math>z'</math> ) , где <math>w'</math> принадлежит <math>W</math>, <math>z'</math> принадлежит <math>Z</math>. Тогда <math>v_1w'z'v_3e...v_kv_1</math> – требуемый орцикл.Таким образом в любом сильно связанном турнире T с n вершинами будет орцикл длины n, то есть гамильтонов циклd.