Изменения

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

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