Редактирование: Теорема Редеи-Камиона

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 5: Строка 5:
 
В любом [[Турниры|турнире]] есть [[Гамильтоновы_графы#.D0.9E.D1.81.D0.BD.D0.BE.D0.B2.D0.BD.D1.8B.D0.B5_.D0.BE.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|гамильтонов путь]].
 
В любом [[Турниры|турнире]] есть [[Гамильтоновы_графы#.D0.9E.D1.81.D0.BD.D0.BE.D0.B2.D0.BD.D1.8B.D0.B5_.D0.BE.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|гамильтонов путь]].
 
|proof=  
 
|proof=  
Приведем доказательство по индукции по числу вершин в графе. Пусть <tex> n </tex> {{---}} количество вершин в графе.
+
Приведем доказательство по индукции по числу вершин. Пусть <tex> n </tex> - количество вершин в графе.
  
<u> ''База индукции:'' </u>
+
<u> ''База индукции:'' </u>
  
 
Очевидно, для <tex> n = 3 </tex> утверждение верно.
 
Очевидно, для <tex> n = 3 </tex> утверждение верно.
Строка 15: Строка 15:
 
Пусть предположение верно для всех турниров с количеством вершин не более <tex> n </tex>. Рассмотрим турнир <tex> T </tex> с <tex> n + 1 </tex> вершинами.
 
Пусть предположение верно для всех турниров с количеством вершин не более <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 </tex> произвольная вершина турнира <tex> T </tex>. Тогда турнир <tex> T - u </tex> имеет <tex> n </tex> вершин, значит, в нем есть гамильтонов путь <tex> P: v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_n </tex>.  
[[Файл: Redei_kamion_1.png|150px|thumb|center]]
+
Одно из ребер <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) </tex> или <tex> (v_1, u) </tex> обязательно содержится в <tex> T </tex>.
+
# Ребро <tex> (u, v_1) \notin ET </tex>. Пусть <tex> v_i </tex> - первая вершина пути <tex> P </tex>, для которой ребро <tex> (u, v_i) \in T </tex>.
Если ребро <tex> (u, v_1) \in ET </tex>, то путь <tex> (u \rightarrow P) </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> гамильтонов.  
[[Файл: Redei_kamion_2.png|150px|thumb|center|<font color=#ff2a2a>Красным</font> цветом выделен искомый путь]]
+
## Если такой вершины не существует, то путь <tex> P \rightarrow u </tex> - гамильтонов.
 
 
Пусть теперь ребро <tex> (u, v_1) \notin ET, 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> {{---}} гамильтонов.
 
[[Файл: Redei_kamion_3.png|180px|thumb|center|<font color=#ff2a2a>Красным</font> цветом выделен искомый путь]]
 
 
 
Если такой вершины не существует, то путь <tex> (P \rightarrow u) </tex> {{---}} гамильтонов.
 
[[Файл: Redei_kamion_4.png|150px|thumb|center|<font color=#ff2a2a>Красным</font> цветом выделен искомый путь]]
 
 
 
 
Значит, в любом случае в турнире существует гамильтонов путь, q.e.d.
 
Значит, в любом случае в турнире существует гамильтонов путь, q.e.d.
 
}}
 
}}
Строка 38: Строка 30:
 
В любом [[Отношение_связности,_компоненты_связности#.D0.A1.D0.B8.D0.BB.D1.8C.D0.BD.D0.B0.D1.8F_.D1.81.D0.B2.D1.8F.D0.B7.D0.BD.D0.BE.D1.81.D1.82.D1.8C|сильно связанном]] турнире есть [[Гамильтоновы_графы#.D0.9E.D1.81.D0.BD.D0.BE.D0.B2.D0.BD.D1.8B.D0.B5_.D0.BE.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|гамильтонов цикл]].
 
В любом [[Отношение_связности,_компоненты_связности#.D0.A1.D0.B8.D0.BB.D1.8C.D0.BD.D0.B0.D1.8F_.D1.81.D0.B2.D1.8F.D0.B7.D0.BD.D0.BE.D1.81.D1.82.D1.8C|сильно связанном]] турнире есть [[Гамильтоновы_графы#.D0.9E.D1.81.D0.BD.D0.BE.D0.B2.D0.BD.D1.8B.D0.B5_.D0.BE.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|гамильтонов цикл]].
 
|proof=  
 
|proof=  
Приведем доказательство по индукции по числу вершин в цикле. Пусть <tex> n </tex> {{---}} количество вершин в графе.
+
Приведем доказательство по индукции по числу вершин. Пусть <tex> n </tex> - количество вершин в графе.
 
 
<u> ''База индукции:'' </u>
 
  
{{Утверждение
+
<u> ''База  индукции:'' </u>
|statement=
 
Cильно связанный турнир <tex> T </tex> из <tex> n \geqslant 3 </tex> вершин содержит [[Основные_определения_теории_графов#.D0.9E.D1.80.D0.B8.D0.B5.D0.BD.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.BD.D1.8B.D0.B5_.D0.B3.D1.80.D0.B0.D1.84.D1.8B|цикл]] длины <tex> 3 </tex>.
 
|proof=
 
Пусть <tex> u </tex> {{---}} произвольная вершина турнира <tex> T </tex>. Множество вершин <tex> VT - u </tex> распадается на <tex> 2 </tex> непересекающихся множества:
 
* <tex> V_1 = \{ v_1 \in VT \mid (v_1, u) \in ET \} </tex>,
 
* <tex> V_2 = \{ v_2 \in VT \mid (u, v_2) \in ET \} </tex>.
 
[[Файл: Redei_kamion_5.png|290px|thumb|center]]
 
  
<tex> T </tex> сильно связен, следовательно:
+
Покажем, что в любом сильно связанном турнире <tex>T</tex> с <tex>n</tex> вершинами <tex>n \ge 3</tex> есть орцикл длины 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>.
# <tex> V_1 \neq \emptyset </tex>, иначе <tex> v </tex> {{---}} исток турнира
 
# <tex> V_2 \neq \emptyset </tex>, иначе <tex> v </tex> {{---}} сток турнира
 
# <tex> \exists e = (w_2, w_1) \in ET </tex>, иначе нет пути из <tex> V_2 </tex> в <tex> V_1 </tex>:
 
#* <tex> w_1 \in V_1 </tex>,
 
#* <tex> w_2 \in V_2 </tex>.
 
[[Файл: Redei_kamion_6.png|290px|thumb|center|<font color=#ff2a2a>Красным</font> цветом выделен цикл длины <tex> 3 </tex>]]
 
 
 
Цикл <tex> S_3: (u \rightarrow w_2 \rightarrow w_1 \rightarrow u) </tex> {{---}} искомый цикл длины <tex> 3 </tex>, q.e.d.
 
}}
 
  
 
<u> ''Индукционный переход:'' </u>
 
<u> ''Индукционный переход:'' </u>
  
{{Утверждение
+
Покажем, что если турнир <tex>T</tex> с <tex>n</tex> вершинами имеет орцикл <tex>S = v_1v_2...v_kv_1</tex> длины <tex>k < n</tex>, то он имеет также орцикл длины <tex>k + 1</tex>. Рассмотрим 2 случая:
|statement=
+
# Существует такая вершина <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> T </tex> из <tex> n \geqslant 3 </tex> вершин содержит цикл <tex> S_k </tex> длины <tex> k, (k < n)</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_3...v_k v_1</tex> – требуемый орцикл.
|proof=
+
Таким образом в любом сильно связанном турнире <tex>T</tex> с <tex>n</tex> вершинами будет орцикл длины <tex>n</tex>, то есть гамильтонов цикл.
Пусть <tex> S_k = (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_k \rightarrow v_1) </tex>.
 
 
 
Пусть <tex> v_0 : v_0 \notin S_k </tex> и верно, что <tex> \exists u, w \in S_k </tex>:
 
* <tex> (v_0, u) \in ET </tex>,
 
* <tex> (w, v_0) \in ET </tex>.
 
 
 
Рассмотрим два случая:
 
# существует такая вершина <tex> v_0 </tex>,
 
# не существует такой вершины <tex> v_0 </tex>.
 
Заметим, что при <tex> k = n - 1 </tex> такая вершина необходимо существует, так как иначе вершина, не входящая в цикл, будет являться либо стоком, либо истоком.
 
 
 
<u> Первый случай: </u>
 
 
 
Перенумеруем вершины <tex> S_k </tex> так, чтобы ребро <tex> e = (v_1, v_0) \in ET </tex> для вершины <tex> v_1 \in S_k </tex>. Пусть <tex> v_i </tex> – первая вершина при обходе <tex> S_k </tex> из <tex> v_1 </tex>, для которой ребро <tex> f = (v_0, v_i) \in ET </tex>.
 
[[Файл: Redei_kamion_7.png|150px|thumb|center]]
 
 
 
Тогда ребро <tex> g = (v_{i - 1}, v_0) \in ET </tex>.
 
[[Файл: Redei_kamion_8.png|150px|thumb|center|<font color=#ff2a2a>Красным</font> цветом выделен искомый цикл длины <tex> k + 1 </tex> ]]
 
 
 
Тогда <tex> S_{k + 1} = (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_{i - 1} \rightarrow v_0 \rightarrow v_i \rightarrow \ldots \rightarrow v_k \rightarrow v_1) </tex> – искомый цикл длины <tex> k + 1 </tex>.
 
 
 
<u> Второй случай: </u>
 
 
 
Пусть:
 
* <tex> V_1 = \{ u \in VT \mid u \notin S_k, e = (u, v_i) \in ET, \forall i = \overline{1, n} \} </tex>,
 
* <tex> V_2 = \{ u \in VT \mid u \notin S_k, f = (v_i, u) \in ET, \forall i = \overline{1, n} \} </tex>.
 
Тогда <tex> V_1 \cap V_2 = \emptyset </tex>.
 
[[Файл: Redei_kamion_9.png|290px|thumb|center]]
 
 
 
Турнир сильно связен, следовательно:
 
* <tex> V_1 \neq \emptyset </tex>, иначе <tex> T </tex> не будет сильно связным, так как тогда нет простых путей с началом в <tex> V_2 </tex> и концом в <tex> S_k </tex>
 
* <tex> V_2 \neq \emptyset </tex>, иначе <tex> T </tex> не будет сильно связным, так как тогда нет простых путей с началом в <tex> S_k </tex> и концом в <tex> V_1 </tex>
 
* <tex> \exists g = (w_2, w_1) \in ET </tex>, иначе <tex> T </tex> не будет сильно связным, так как тогда нет простых путей с началом в <tex> V_2 </tex> и концом в <tex> V_1 </tex>):
 
** <tex> w_1 \in V_1 </tex>,
 
** <tex> w_2 \in V_2 </tex>.
 
[[Файл: Redei_kamion_10.png|290px|thumb|center|<font color=#ff2a2a>Красным</font> цветом выделен цикл длины <tex> k + 1 </tex>]]
 
Тогда <tex> S_{k + 1} = (v_1 \rightarrow w_2 \rightarrow w_1 \rightarrow v_3 \rightarrow \ldots \rightarrow v_k \rightarrow v_1) </tex> – искомый цикл длины <tex> k + 1 </tex>.
 
 
 
В любом случае утверждение верно, q.e.d.
 
 
 
}}
 
Таким образом, любой сильно связанный турнир <tex> T </tex> с <tex> n \geqslant 3 </tex> вершинами содержит цикл длины <tex> n </tex>, то есть гамильтонов цикл, q.e.d.
 
 
}}
 
}}
  
{{Теорема
+
{{Лемма
 
|about=
 
|about=
 
Следствие
 
Следствие
Строка 119: Строка 51:
 
}}
 
}}
  
==См. также==
+
== Литература ==
* [[Гамильтоновы графы]]
 
* [[Турниры]]
 
 
 
== Источники информации ==
 
 
* Асанов М., Баранский В., Расин В.: ''Дискретная математика: Графы, матроиды, алгоритмы''
 
* Асанов М., Баранский В., Расин В.: ''Дискретная математика: Графы, матроиды, алгоритмы''
 
* Ф. Харари: ''Теория графов''
 
* Ф. Харари: ''Теория графов''
Строка 129: Строка 57:
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Обходы графов]]
 
[[Категория: Обходы графов]]
[[Категория: Гамильтоновы графы]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: