Изменения

Докажем,что в любом турнире есть гамильтонов путь по индукции по числу вершин <tex>n</tex>.# ''База индукции: n = 3 '' <br> Очевидно, для <tex>n = 3 </tex> утверждение верно.# ''Индукционный переход :'' <br> Предположим, что теорема верна для всех турниров с <tex>n </tex> вершинами. Рассмотрим турнир <tex>T </tex> с <tex>n + 1 </tex> вершинами. Пусть <tex>v_0</tex> – произвольная вершина турнира <tex>T</tex>. Тогда турнир <tex>T </tex> – <tex>v_0</tex> имеет <tex>n </tex> вершин, значит, в нем есть гамильтонов путь <tex>P</tex>: <tex>v_1v_2...v_n</tex> . Одно из ребер ( <tex>v_0</tex>, <tex>v_1</tex> ) или ( <tex>v_1v_n</tex>, <tex>v_0</tex> ) обязательно содержится в <tex>T</tex>. Рассмотрим 3 случая: ## Ребро <tex> ( v_0, v_1 ) \in T </tex>. Тогда путь <tex>v_0v_1v_2...v_n</tex> является гамильтоновым. ## Ребро <tex> ( v_0, v_1 ) \notin T </tex>. Обозначим через <tex>v_i</tex> первую вершину пути <tex>P</tex>, для которой ребро <tex> ( v_0, v_i ) \in T </tex>,если такая вершина есть. Тогда в <tex>T </tex> существует ребро ( <tex>v_{i-1}</tex>, <tex>v_0</tex> ) <br> и путь <tex>v_1...v_{i-1}v_0v_i...v_n</tex>– гамильтонов. ## Если такой вершины <tex>v_i</tex> нет, тогда гамильтоновым путем будет <tex>v_1v_2...v_nv_0</tex>.

# ''База индукции: '' <br> Покажем, что в любом сильно связанном турнире <tex>T </tex> с <tex>n </tex> вершинами (<tex>n \ge 3</tex>= 3) есть орцикл длины 3. Выберем произвольную вершину <tex>v_0</tex> и обозначим через <tex>W</tex> множество всех вершин <tex>w</tex>, таких, что ребро <tex> ( v_0, w ) \in T </tex>, а через <tex>Z</tex> – множество всех вершин <tex>z</tex>, таких, что ребро <tex> ( z, v_0 ) \in T </tex>. Так как <tex>T </tex> сильно связан, то оба множества <tex>W</tex> и <tex>Z</tex> не пусты и найдется ребро <tex> ( w', z' ) \in T </tex> , где <tex>w' \in W , z' \in Z</tex>. Тогда искомым циклом длины 3 будет <tex>v_0</tex>,<tex>w'</tex>,<tex>z'</tex>,<tex>v_0</tex>.# ''Индукционный переход :'' <br> Покажем, что если турнир <tex>T </tex> с <tex>n </tex> вершинами имеет орцикл S = <tex>S = v_1v_2...v_kv_1</tex> длины <tex>k < n</tex>, то он имеет также орцикл длины <tex>k + 1</tex>. Рассмотрим 2 случая:## Существует такая вершина <tex>v_0 \notin S </tex> и такая, что найдутся вершины <tex>u , w \in S</tex> , такие, что ребра <tex> ( v_0 , u ) , ( w , v_0) \in T </tex>. Обозначим за <tex>v_1</tex> вершину из <tex>S</tex>, такую, что ребро <tex> ( v_1, v_0 ) \in T </tex>. Пусть <tex>v_i</tex> – первая вершина при обходе контура <tex>S </tex> из <tex>v_1</tex>, для которой ребро <br> <tex> ( v_0, v_i ) \in T </tex>. Тогда ребро ( <tex>(v_{i-1}, v_0)</tex>, также содержится в <tex>v_0T</tex> ) также содержится в T. Поэтому <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>(v_i</tex>, <tex>w)</tex> ) для любого <tex>i</tex> содержится в <tex>T</tex>, а <tex>Z</tex> – множество таких вершин <tex>z</tex>, что ребро ( <tex>(z</tex>, <tex>v_i)</tex> ) для любого <tex>i</tex> содержится в <tex>T</tex>. Так как <tex>T </tex> сильно связан, то оба множества <tex>W</tex> и <tex>Z</tex> не пусты и найдется ребро <tex> ( w', z' ) \in T </tex> , где <tex>w' \in W , z' \in Z</tex>. Тогда <tex>v_1 w' z' v_3...v_k v_1</tex> – требуемый орцикл.Таким образом в любом сильно связанном турнире <tex>T </tex> с <tex>n </tex> вершинами будет орцикл длины <tex>n</tex>, то есть гамильтонов цикл.

<u>'''Следствие'''</u> <br>