748
правок
Изменения
Нет описания правки
Пусть предположение верно для всех турниров с количеством вершин не более <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|150px|thumb|center]]
Пусть теперь ребро <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|180px|thumb|center|<font color=#ff2a2a>Красным</font> цветом выделен искомый путь]]
|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]]
Пусть:
* <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]]
