272
правки
Изменения
Нет описания правки
Пусть предположение верно для всех турниров с количеством вершин не более <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>.
Одно из ребер <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> - гамильтонов.
# Ребро <tex> (u, v_1) \notin ET </tex>. Пусть <tex> 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> – гамильтонов. ## Если такой вершины не существует, то путь <tex> (P \rightarrow u ) </tex> - гамильтонов.
Значит, в любом случае в турнире существует гамильтонов путь, q.e.d.
}}
#* <tex> v'_1 \in V_1 </tex>
#* <tex> v'_2 \in V_2 </tex>
Цикл <tex> P: (u \rightarrow v'_1 \rightarrow v'_2 \rightarrow u ) </tex> - искомый орцикл длины <tex> 3 </tex>, q.e.d.
}}
