26
правок
Изменения
формулировка теоремы для пути и для цикла и ее доказательства
==Теорема Редеи-Камиона==
{{Теорема
|about = Теорема Редеи-Камиона для пути
|statement= В любом турнире есть гамильтонов путь.
|proof=
Докажем,что в любом турнире есть гамильтонов путь по индукции по числу вершин n.
# База индукции: n = 3 <br> Очевидно, для n = 3 утверждение верно.
# Индукционный переход <br> Предположим, что теорема верна для всех турниров с n вершинами. Рассмотрим турнир T с n + 1 вершинами. Пусть <math>v_0</math> – произвольная вершина турнира T. Тогда турнир T – <math>v_0</math> имеет n вершин, значит, в нем есть гамильтонов путь P: <math>v_1v_2...v_n</math> . Одно из ребер ( <math>v_0</math>, <math>v_1</math> ) или ( <math>v_1</math>, <math>v_0</math> ) обязательно принадлежит T. Рассмотрим 3 случая:
## Ребро ( <math>v_0</math>, <math>v_1</math> ) принадлежит Т . Тогда путь <math>v_0v_1v_2...v_n</math> является гамильтоновым.
## Обозначим через <math>v_i</math> первую вершину пути P, для которой ребро ( <math>v_0</math>, <math>v_i</math> ) принадлежит T ,если такая вершина есть. Тогда в T существует ребро ( <math>v</math><sub><math>i-1</math></sub>, <math>v_0</math> ) <br> и путь <math>v_1...v</math><sub><math>i-1</math></sub><math>v_0v_i...v_n</math>– гамильтонов.
## Если такой вершины <math>v_i</math> нет, тогда гамильтоновым путем будет <math>v_1v_2...v_nv_0</math>.
Итак, в любом случае в турнире существует гамильтонов путь.
}}
{{Теорема
|about = Теорема Редеи-Камиона для цикла
|statement= В любом сильно связанном турнире есть гамильтонов цикл.
|proof=
Докажем, что в любом сильно связанном турнире есть гамильтонов цикл, по индукции по длине цикла.
# База индукции: <br> Покажем, что в любом сильно связанном турнире T с n вершинами (n >= 3) есть орцикл длины 3. Выберем произвольную вершину <math>v_0</math> и обозначим через <math>W</math> множество всех вершин <math>w</math>, таких, что ребро ( <math>v_0</math>, <math>w</math> ) в T, а через <math>Z</math> – множество всех вершин <math>z</math>, таких, что ребро ( <math>z</math>, <math>v_0</math> ) в T. Так как T сильно связан, то оба множества <math>W</math> и <math>Z</math> не пусты и найдется ребро ( <math>w'</math>, <math>z'</math> ) , где <math>w'</math> принадлежит <math>W</math>, <math>z'</math> принадлежит <math>Z</math>. Тогда искомым циклом длины 3 будет <math>v_0</math>,<math>w'</math>,<math>z'</math>,<math>v_0</math>.
# Индукционный переход <br> Покажем, что если турнир T с n вершинами имеет орцикл S = <math>v_1v_2...v_kv_1</math> длины k < n, то он имеет также орцикл длины k + 1. Рассмотрим 2 случая:
## Существует такая вершина <math>v_0</math> , не принадлежащая орциклу S и такая, что найдутся вершины <math>u</math> и <math>w</math>, принадлежащие орциклу S, такие, что ребра ( <math>v_0</math>, <math>u</math> ) и ( <math>w</math>, <math>v_0</math> ) содержатся в T. Обозначим за <math>v_1</math> вершину из S, такую, что ребро ( <math>v_1</math>, <math>v_0</math> ) содержится в T. Пусть <math>v_i</math> – первая вершина при обходе контура S из <math>v_1</math>, для которой ребро <br> ( <math>v_0</math>, <math>v_i</math> ) принадлежит Т. Тогда ребро ( <math>v</math><sub><math>i-1</math></sub>, <math>v_0</math> ) также содержится в T. Поэтому <math>v_1v_2...v</math><sub><math>i-1</math></sub><math>v_0v_i...v_kv_1</math> – искомый орцикл длины k+1.
## Пусть такой вершины <math>v_0</math> нет. Тогда разобьем вершины, не принадлежащие S, на два непересекающихся подмножества <math>W</math> и <math>Z</math>, где <math>W</math> - множество таких вершин <math>w</math> , что ребро ( <math>v_i</math>, <math>w</math> ) для любого <math>i</math> содержится в T, а <math>Z</math> – множество таких вершин <math>z</math>, что ребро ( <math>z</math>, <math>v_i</math> ) для любого <math>i</math> содержится в T. Так как T сильно связан, то оба множества <math>W</math> и <math>Z</math> не пусты и найдется ребро ( <math>w'</math>, <math>z'</math> ) , где <math>w'</math> принадлежит <math>W</math>, <math>z'</math> принадлежит <math>Z</math>. Тогда <math>v_1w'z'v_3...v_kv_1</math> – требуемый орцикл.
Таким образом в любом сильно связанном турнире T с n вершинами будет орцикл длины n, то есть гамильтонов цикл.
}}
{{Теорема
|about = Теорема Редеи-Камиона для пути
|statement= В любом турнире есть гамильтонов путь.
|proof=
Докажем,что в любом турнире есть гамильтонов путь по индукции по числу вершин n.
# База индукции: n = 3 <br> Очевидно, для n = 3 утверждение верно.
# Индукционный переход <br> Предположим, что теорема верна для всех турниров с n вершинами. Рассмотрим турнир T с n + 1 вершинами. Пусть <math>v_0</math> – произвольная вершина турнира T. Тогда турнир T – <math>v_0</math> имеет n вершин, значит, в нем есть гамильтонов путь P: <math>v_1v_2...v_n</math> . Одно из ребер ( <math>v_0</math>, <math>v_1</math> ) или ( <math>v_1</math>, <math>v_0</math> ) обязательно принадлежит T. Рассмотрим 3 случая:
## Ребро ( <math>v_0</math>, <math>v_1</math> ) принадлежит Т . Тогда путь <math>v_0v_1v_2...v_n</math> является гамильтоновым.
## Обозначим через <math>v_i</math> первую вершину пути P, для которой ребро ( <math>v_0</math>, <math>v_i</math> ) принадлежит T ,если такая вершина есть. Тогда в T существует ребро ( <math>v</math><sub><math>i-1</math></sub>, <math>v_0</math> ) <br> и путь <math>v_1...v</math><sub><math>i-1</math></sub><math>v_0v_i...v_n</math>– гамильтонов.
## Если такой вершины <math>v_i</math> нет, тогда гамильтоновым путем будет <math>v_1v_2...v_nv_0</math>.
Итак, в любом случае в турнире существует гамильтонов путь.
}}
{{Теорема
|about = Теорема Редеи-Камиона для цикла
|statement= В любом сильно связанном турнире есть гамильтонов цикл.
|proof=
Докажем, что в любом сильно связанном турнире есть гамильтонов цикл, по индукции по длине цикла.
# База индукции: <br> Покажем, что в любом сильно связанном турнире T с n вершинами (n >= 3) есть орцикл длины 3. Выберем произвольную вершину <math>v_0</math> и обозначим через <math>W</math> множество всех вершин <math>w</math>, таких, что ребро ( <math>v_0</math>, <math>w</math> ) в T, а через <math>Z</math> – множество всех вершин <math>z</math>, таких, что ребро ( <math>z</math>, <math>v_0</math> ) в T. Так как T сильно связан, то оба множества <math>W</math> и <math>Z</math> не пусты и найдется ребро ( <math>w'</math>, <math>z'</math> ) , где <math>w'</math> принадлежит <math>W</math>, <math>z'</math> принадлежит <math>Z</math>. Тогда искомым циклом длины 3 будет <math>v_0</math>,<math>w'</math>,<math>z'</math>,<math>v_0</math>.
# Индукционный переход <br> Покажем, что если турнир T с n вершинами имеет орцикл S = <math>v_1v_2...v_kv_1</math> длины k < n, то он имеет также орцикл длины k + 1. Рассмотрим 2 случая:
## Существует такая вершина <math>v_0</math> , не принадлежащая орциклу S и такая, что найдутся вершины <math>u</math> и <math>w</math>, принадлежащие орциклу S, такие, что ребра ( <math>v_0</math>, <math>u</math> ) и ( <math>w</math>, <math>v_0</math> ) содержатся в T. Обозначим за <math>v_1</math> вершину из S, такую, что ребро ( <math>v_1</math>, <math>v_0</math> ) содержится в T. Пусть <math>v_i</math> – первая вершина при обходе контура S из <math>v_1</math>, для которой ребро <br> ( <math>v_0</math>, <math>v_i</math> ) принадлежит Т. Тогда ребро ( <math>v</math><sub><math>i-1</math></sub>, <math>v_0</math> ) также содержится в T. Поэтому <math>v_1v_2...v</math><sub><math>i-1</math></sub><math>v_0v_i...v_kv_1</math> – искомый орцикл длины k+1.
## Пусть такой вершины <math>v_0</math> нет. Тогда разобьем вершины, не принадлежащие S, на два непересекающихся подмножества <math>W</math> и <math>Z</math>, где <math>W</math> - множество таких вершин <math>w</math> , что ребро ( <math>v_i</math>, <math>w</math> ) для любого <math>i</math> содержится в T, а <math>Z</math> – множество таких вершин <math>z</math>, что ребро ( <math>z</math>, <math>v_i</math> ) для любого <math>i</math> содержится в T. Так как T сильно связан, то оба множества <math>W</math> и <math>Z</math> не пусты и найдется ребро ( <math>w'</math>, <math>z'</math> ) , где <math>w'</math> принадлежит <math>W</math>, <math>z'</math> принадлежит <math>Z</math>. Тогда <math>v_1w'z'v_3...v_kv_1</math> – требуемый орцикл.
Таким образом в любом сильно связанном турнире T с n вершинами будет орцикл длины n, то есть гамильтонов цикл.
}}
