Бюрократы, editor, Администраторы
422
правки
Изменения
Уууупс
''Индукционный переход:'' <br> Покажем, что если турнир <tex>T</tex> с <tex>n</tex> вершинами имеет орцикл <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>, для которой ребро <tex> ( v_0, v_i ) \in T </tex>. Тогда ребро <tex>(v_{i-1}, v_0)</tex> также содержится в <tex>T</tex>. Поэтому <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, w)</tex> для любого <tex>i</tex> содержится в <tex>T</tex>, а <tex>Z</tex> – множество таких вершин <tex>z</tex>, что ребро <tex>(z, 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_2v_3...v_k v_1</tex> – требуемый орцикл.
Таким образом в любом сильно связанном турнире <tex>T</tex> с <tex>n</tex> вершинами будет орцикл длины <tex>n</tex>, то есть гамильтонов цикл.
}}
