Изменения

Докажем,что в любом турнире есть гамильтонов путь Приведем доказательство по индукции по числу вершин в графе. Пусть <tex>n</tex>{{---}} количество вершин в графе.

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

Очевидно, для <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.

Докажем, что в любом сильно связанном турнире есть гамильтонов цикл, Приведем доказательство по индукции по длине циклачислу вершин в цикле.Пусть <tex> n </tex> {{---}} количество вершин в графе. <u> ''База индукции:'' </u>

''База индукции:'' <br> Покажем, что в любом сильно связанном турнире {{Утверждение|statement=Cильно связанный турнир <tex>T</tex> с <tex>n</tex> вершинами из <tex>n \ge 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|цикл]] длины 3. Выберем произвольную вершину <tex>v_03 </tex> и обозначим через <tex>W</tex> множество всех вершин .|proof=Пусть <tex>wu </tex>, таких, что ребро {{---}} произвольная вершина турнира <tex>(v_0, w) \in T </tex>, а через . Множество вершин <tex>ZVT - u </tex> – множество всех вершин распадается на <tex>z2 </tex>, таких, что ребро непересекающихся множества:* <tex>(z, v_0) V_1 = \{ v_1 \in T </tex>. Так как <tex>T</tex> сильно связан, то оба множества <tex>W</tex> и <tex>Z</tex> не пусты и найдется ребро <tex>VT \mid (w'v_1, z'u) \in T ET \} </tex> , где * <tex>w' V_2 = \{ v_2 \in WVT \mid (u, z' v_2) \in ZET \} </tex>. Тогда искомым циклом длины 3 будет <tex>v_0</tex>,<tex>w'</tex>,<tex>z'</tex>,<tex>v_0</tex>[[Файл: Redei_kamion_5.png|290px|thumb|center]]

''Индукционный переход:'' <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 случаяследовательно:# Существует такая вершина <tex>v_0 V_1 \notin S neq \emptyset </tex> такая, что найдутся вершины иначе <tex>u , w \in Sv </tex> , такие, что ребра {{---}} исток турнира# <tex> (v_0 , u) , (w , v_0) V_2 \in T </tex>. Обозначим за <tex>v_1</tex> вершину из <tex>S</tex>, такую, что ребро <tex> ( v_1, v_0 ) neq \in T </tex>. Пусть <tex>v_i</tex> – первая вершина при обходе контура <tex>S</tex> из <tex>v_1emptyset </tex>, для которой ребро иначе <tex> ( v_0, v_i ) \in T v </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+1</tex>.сток турнира# Пусть такой вершины <tex>v_0</tex> нет. Тогда разобьем вершины, не принадлежащие <tex>S</tex>, на два непересекающихся подмножества <tex>W</tex> и <tex>Z</tex>, где <tex>W</tex> - множество таких вершин <tex>w</tex> , что ребро <tex>\exists e = (v_iw_2, ww_1)</tex> для любого <tex>i</tex> содержится в <tex>T\in ET </tex>, а <tex>Z</tex> – множество таких вершин <tex>z</tex>, что ребро иначе нет пути из <tex>(z, v_i)V_2 </tex> для любого <tex>i</tex> содержится в <tex>TV_1 </tex>. Так как <tex>T</tex> сильно связан, то оба множества <tex>W</tex> и <tex>Z</tex> не пусты и найдется ребро :#* <tex> (w', z') w_1 \in T V_1 </tex> , где #* <tex>w' \in W , z' w_2 \in ZV_2 </tex>. Тогда [[Файл: Redei_kamion_6.png|290px|thumb|center|<texfont color=#ff2a2a>v_1 w' z' v_3...v_k v_1Красным</texfont> – требуемый орцикл.Таким образом в любом сильно связанном турнире цветом выделен цикл длины <tex>T3 </tex> с ]] Цикл <tex>nS_3: (u \rightarrow w_2 \rightarrow w_1 \rightarrow u) </tex> вершинами будет орцикл {{---}} искомый цикл длины <tex>n3 </tex>, то есть гамильтонов циклq.e.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>.

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