1632
правки
Изменения
м
rollbackEdits.php mass rollback
Приведем доказательство по индукции по числу вершин в графе. Пусть <tex> n </tex> {{---}} количество вершин в графе.
<u> ''База индукции:'' </u>
Очевидно, для <tex> n = 3 </tex> утверждение верно.
Пусть предположение верно для всех турниров с количеством вершин не более <tex> n </tex>. Рассмотрим турнир <tex> T </tex> с <tex> n + 1 </tex> вершинами.
Пусть <tex> u </tex> – {{---}} произвольная вершина турнира <tex> T </tex>. Тогда турнир <tex> T - u </tex> имеет <tex> n </tex> вершин, значит, в нем есть гамильтонов путь <tex> P: (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_n) </tex>.[[Файл: Redei_kamion_1.png|250px150px|thumb|center]]
Одно из ребер рёбер <tex> (u, v_1) </tex> или <tex> (v_1, u) </tex> обязательно содержится в <tex> T </tex>.
Если ребро <tex> (u, v_1) \in ET </tex>, то путь <tex> (u \rightarrow P) </tex> {{---}} гамильтонов.
[[Файл: Redei_kamion_2.png|250px150px|thumb|center|<font color=#ff2a2a>Красным</font> цветом выделен искомый путь]]
Пусть теперь ребро <tex> (u, v_1) \notin ET, v_i </tex> {{---}} первая вершина пути <tex> P </tex>, для которой ребро <tex> (u, v_i) \in T </tex>.Если такая вершина существует, то в <tex> T </tex> существует ребро <tex> (v_{i - 1}, u) </tex> и путь <tex> (v_1 \rightarrow \ldots \rightarrow v_{i - 1} \rightarrow u \rightarrow v_i \rightarrow \ldots v_n) </tex> – {{---}} гамильтонов.[[Файл: Redei_kamion_3.png|250px180px|thumb|center|<font color=#ff2a2a>Красным</font> цветом выделен искомый путь]]
Если такой вершины не существует, то путь <tex> (P \rightarrow u) </tex> {{---}} гамильтонов.
[[Файл: Redei_kamion_4.png|250px150px|thumb|center|<font color=#ff2a2a>Красным</font> цветом выделен искомый путь]]
Значит, в любом случае в турнире существует гамильтонов путь, q.e.d.
Приведем доказательство по индукции по числу вершин в цикле. Пусть <tex> n </tex> {{---}} количество вершин в графе.
<u> ''База индукции:'' </u>
{{Утверждение
|statement=
Cильно связанный турнир <tex> T </tex> из <tex> n \geq 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|350px290px|thumb|center]]
<tex> T </tex> сильно связен, следовательно:
#* <tex> w_1 \in V_1 </tex>,
#* <tex> w_2 \in V_2 </tex>.
[[Файл: Redei_kamion_6.png|350px290px|thumb|center|<font color=#ff2a2a>Красным</font> цветом выделен цикл длины <tex> 3 </tex>]]
Цикл <tex> S_3: (u \rightarrow w_2 \rightarrow w_1 \rightarrow u) </tex> {{---}} искомый цикл длины <tex> 3 </tex>, q.e.d.
{{Утверждение
|statement=
Если сильно связанный турнир <tex> T </tex> из <tex> n \geq 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> 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|250px150px|thumb|center]]
Тогда ребро <tex> g = (v_{i - 1}, v_0) \in ET </tex>.
[[Файл: Redei_kamion_8.png|250px150px|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>.
Пусть:
* <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|350px290px|thumb|center]]
Турнир сильно связен, следовательно:
** <tex> w_1 \in V_1 </tex>,
** <tex> w_2 \in V_2 </tex>.
[[Файл: Redei_kamion_10.png|350px290px|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>.
}}
Таким образом, любой сильно связанный турнир <tex> T </tex> с <tex> n \geq geqslant 3 </tex> вершинами содержит цикл длины <tex> n </tex>, то есть гамильтонов цикл, q.e.d.
}}
* [[Турниры]]
== Литература Источники информации ==
* Асанов М., Баранский В., Расин В.: ''Дискретная математика: Графы, матроиды, алгоритмы''
* Ф. Харари: ''Теория графов''
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обходы графов]]
[[Категория: Гамильтоновы графы]]
