Теорема Редеи-Камиона — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теорема Редеи-Камиона)
м (rollbackEdits.php mass rollback)
 
(не показаны 62 промежуточные версии 8 участников)
Строка 1: Строка 1:
 
{{Теорема
 
{{Теорема
|about = Теорема Редеи-Камиона для пути  
+
|about=
|statement= В любом турнире есть гамильтонов путь.
+
Редеи-Камиона (для пути)
 +
|statement=
 +
В любом [[Турниры|турнире]] есть [[Гамильтоновы_графы#.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> {{---}} количество вершин в графе.
  
Докажем,что в любом турнире есть гамильтонов путь по индукции по числу вершин n.
+
<u> ''База индукции:'' </u>
# База индукции: 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 случая:
+
Очевидно, для <tex> n = 3 </tex> утверждение верно.
## Ребро <math> ( v_0, v_1 ) \in T </math>. Тогда путь <math>v_0v_1v_2...v_n</math> является гамильтоновым.
+
 
## Обозначим через <math>v_i</math> первую вершину пути P, для которой ребро <math> ( v_0, v_i ) \in T </math>,если такая вершина есть. Тогда в 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>– гамильтонов.
+
<u> ''Индукционный переход:'' </u>
## Если такой вершины <math>v_i</math> нет, тогда гамильтоновым путем будет <math>v_1v_2...v_nv_0</math>.
+
 
Итак, в любом случае в турнире существует гамильтонов путь.
+
Пусть предположение верно для всех турниров с количеством вершин не более <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>.
 +
[[Файл: 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> {{---}} гамильтонов.
 +
[[Файл: Redei_kamion_2.png|150px|thumb|center|<font color=#ff2a2a>Красным</font> цветом выделен искомый путь]]
 +
 
 +
Пусть теперь ребро <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.
 
}}
 
}}
  
 
{{Теорема
 
{{Теорема
|about = Теорема Редеи-Камиона для цикла  
+
|about=
|statement= В любом сильно связанном турнире есть гамильтонов цикл.
+
Редеи-Камиона (для цикла)
 +
|statement=
 +
В любом [[Отношение_связности,_компоненты_связности#.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> {{---}} количество вершин в графе.
  
Докажем, что в любом сильно связанном турнире есть гамильтонов цикл, по индукции по длине цикла.
+
<u> ''База индукции:'' </u>
# База индукции: <br> Покажем, что в любом сильно связанном турнире T с n вершинами (n >= 3) есть орцикл длины 3. Выберем произвольную вершину <math>v_0</math> и обозначим через <math>W</math> множество всех вершин <math>w</math>, таких, что ребро <math> ( v_0, w  ) \in T </math>, а через <math>Z</math> – множество всех вершин <math>z</math>, таких, что ребро <math> ( z, v_0  ) \in T </math>. Так как T сильно связан, то оба множества <math>W</math> и <math>Z</math> не пусты и найдется ребро  <math> ( w', z' ) \in T </math> , где <math>w' \in W , z' \in 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 \notin S </math> и такая, что найдутся вершины <math>u , w \in S</math> , такие, что ребра <math> ( v_0 , u ) , ( w , v_0) \in T </math>. Обозначим за <math>v_1</math> вершину из S, такую, что ребро  <math> ( v_1, v_0  ) \in T </math>. Пусть <math>v_i</math> – первая вершина при обходе контура S из <math>v_1</math>, для которой ребро <br>  <math> ( v_0, v_i  ) \in T </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.
+
|statement=
## Пусть такой вершины <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', z' ) \in T </math> , где <math>w' \in W , z' \in Z</math>. Тогда <math>v_1 w' z' v_3...v_k v_1</math> – требуемый орцикл.
+
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>.
Таким образом в любом сильно связанном турнире T с n вершинами будет орцикл длины n, то есть гамильтонов цикл.
+
|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> 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> <br>
+
<u> ''Индукционный переход:'' </u>
 +
 
 +
{{Утверждение
 +
|statement=
 +
Если сильно связанный турнир <tex> T </tex> из <tex> n \geqslant 3 </tex> вершин содержит цикл <tex> S_k </tex> длины <tex> k, (k < n)</tex>, то он содержит и цикл длины <tex> k + 1 </tex>.
 +
|proof=
 +
Пусть <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=
 +
Следствие
 +
|statement=
 
Турнир является сильно связанным тогда и только тогда, когда он имеет гамильтонов цикл.
 
Турнир является сильно связанным тогда и только тогда, когда он имеет гамильтонов цикл.
 +
}}
 +
 +
==См. также==
 +
* [[Гамильтоновы графы]]
 +
* [[Турниры]]
 +
 +
== Источники информации ==
 +
* Асанов М., Баранский В., Расин В.: ''Дискретная математика: Графы, матроиды, алгоритмы''
 +
* Ф. Харари: ''Теория графов''
  
==Литература==
+
[[Категория: Алгоритмы и структуры данных]]
*  Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009
+
[[Категория: Обходы графов]]
 +
[[Категория: Гамильтоновы графы]]

Текущая версия на 19:07, 4 сентября 2022

Теорема (Редеи-Камиона (для пути)):
Доказательство:
[math]\triangleright[/math]

Приведем доказательство по индукции по числу вершин в графе. Пусть [math] n [/math] — количество вершин в графе.

База индукции:

Очевидно, для [math] n = 3 [/math] утверждение верно.

Индукционный переход:

Пусть предположение верно для всех турниров с количеством вершин не более [math] n [/math]. Рассмотрим турнир [math] T [/math] с [math] n + 1 [/math] вершинами.

Пусть [math] u [/math] — произвольная вершина турнира [math] T [/math]. Тогда турнир [math] T - u [/math] имеет [math] n [/math] вершин, значит, в нем есть гамильтонов путь [math] P: (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_n) [/math].

Redei kamion 1.png

Одно из рёбер [math] (u, v_1) [/math] или [math] (v_1, u) [/math] обязательно содержится в [math] T [/math]. Если ребро [math] (u, v_1) \in ET [/math], то путь [math] (u \rightarrow P) [/math] — гамильтонов.

Красным цветом выделен искомый путь

Пусть теперь ребро [math] (u, v_1) \notin ET, v_i [/math] — первая вершина пути [math] P [/math], для которой ребро [math] (u, v_i) \in T [/math]. Если такая вершина существует, то в [math] T [/math] существует ребро [math] (v_{i - 1}, u) [/math] и путь [math] (v_1 \rightarrow \ldots \rightarrow v_{i - 1} \rightarrow u \rightarrow v_i \rightarrow \ldots v_n) [/math] — гамильтонов.

Красным цветом выделен искомый путь

Если такой вершины не существует, то путь [math] (P \rightarrow u) [/math] — гамильтонов.

Красным цветом выделен искомый путь
Значит, в любом случае в турнире существует гамильтонов путь, q.e.d.
[math]\triangleleft[/math]
Теорема (Редеи-Камиона (для цикла)):
Доказательство:
[math]\triangleright[/math]

Приведем доказательство по индукции по числу вершин в цикле. Пусть [math] n [/math] — количество вершин в графе.

База индукции:

Утверждение:
Cильно связанный турнир [math] T [/math] из [math] n \geqslant 3 [/math] вершин содержит цикл длины [math] 3 [/math].
[math]\triangleright[/math]

Пусть [math] u [/math] — произвольная вершина турнира [math] T [/math]. Множество вершин [math] VT - u [/math] распадается на [math] 2 [/math] непересекающихся множества:

  • [math] V_1 = \{ v_1 \in VT \mid (v_1, u) \in ET \} [/math],
  • [math] V_2 = \{ v_2 \in VT \mid (u, v_2) \in ET \} [/math].
Redei kamion 5.png

[math] T [/math] сильно связен, следовательно:

  1. [math] V_1 \neq \emptyset [/math], иначе [math] v [/math] — исток турнира
  2. [math] V_2 \neq \emptyset [/math], иначе [math] v [/math] — сток турнира
  3. [math] \exists e = (w_2, w_1) \in ET [/math], иначе нет пути из [math] V_2 [/math] в [math] V_1 [/math]:
    • [math] w_1 \in V_1 [/math],
    • [math] w_2 \in V_2 [/math].
Красным цветом выделен цикл длины [math] 3 [/math]
Цикл [math] S_3: (u \rightarrow w_2 \rightarrow w_1 \rightarrow u) [/math] — искомый цикл длины [math] 3 [/math], q.e.d.
[math]\triangleleft[/math]

Индукционный переход:

Утверждение:
Если сильно связанный турнир [math] T [/math] из [math] n \geqslant 3 [/math] вершин содержит цикл [math] S_k [/math] длины [math] k, (k \lt n)[/math], то он содержит и цикл длины [math] k + 1 [/math].
[math]\triangleright[/math]

Пусть [math] S_k = (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_k \rightarrow v_1) [/math].

Пусть [math] v_0 : v_0 \notin S_k [/math] и верно, что [math] \exists u, w \in S_k [/math]:

  • [math] (v_0, u) \in ET [/math],
  • [math] (w, v_0) \in ET [/math].

Рассмотрим два случая:

  1. существует такая вершина [math] v_0 [/math],
  2. не существует такой вершины [math] v_0 [/math].

Заметим, что при [math] k = n - 1 [/math] такая вершина необходимо существует, так как иначе вершина, не входящая в цикл, будет являться либо стоком, либо истоком.

Первый случай:

Перенумеруем вершины [math] S_k [/math] так, чтобы ребро [math] e = (v_1, v_0) \in ET [/math] для вершины [math] v_1 \in S_k [/math]. Пусть [math] v_i [/math] – первая вершина при обходе [math] S_k [/math] из [math] v_1 [/math], для которой ребро [math] f = (v_0, v_i) \in ET [/math].

Redei kamion 7.png

Тогда ребро [math] g = (v_{i - 1}, v_0) \in ET [/math].

Красным цветом выделен искомый цикл длины [math] k + 1 [/math]

Тогда [math] 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) [/math] – искомый цикл длины [math] k + 1 [/math].

Второй случай:

Пусть:

  • [math] V_1 = \{ u \in VT \mid u \notin S_k, e = (u, v_i) \in ET, \forall i = \overline{1, n} \} [/math],
  • [math] V_2 = \{ u \in VT \mid u \notin S_k, f = (v_i, u) \in ET, \forall i = \overline{1, n} \} [/math].

Тогда [math] V_1 \cap V_2 = \emptyset [/math].

Redei kamion 9.png

Турнир сильно связен, следовательно:

  • [math] V_1 \neq \emptyset [/math], иначе [math] T [/math] не будет сильно связным, так как тогда нет простых путей с началом в [math] V_2 [/math] и концом в [math] S_k [/math]
  • [math] V_2 \neq \emptyset [/math], иначе [math] T [/math] не будет сильно связным, так как тогда нет простых путей с началом в [math] S_k [/math] и концом в [math] V_1 [/math]
  • [math] \exists g = (w_2, w_1) \in ET [/math], иначе [math] T [/math] не будет сильно связным, так как тогда нет простых путей с началом в [math] V_2 [/math] и концом в [math] V_1 [/math]):
    • [math] w_1 \in V_1 [/math],
    • [math] w_2 \in V_2 [/math].
Красным цветом выделен цикл длины [math] k + 1 [/math]

Тогда [math] S_{k + 1} = (v_1 \rightarrow w_2 \rightarrow w_1 \rightarrow v_3 \rightarrow \ldots \rightarrow v_k \rightarrow v_1) [/math] – искомый цикл длины [math] k + 1 [/math].

В любом случае утверждение верно, q.e.d.
[math]\triangleleft[/math]
Таким образом, любой сильно связанный турнир [math] T [/math] с [math] n \geqslant 3 [/math] вершинами содержит цикл длины [math] n [/math], то есть гамильтонов цикл, q.e.d.
[math]\triangleleft[/math]
Теорема (Следствие):
Турнир является сильно связанным тогда и только тогда, когда он имеет гамильтонов цикл.

См. также

Источники информации

  • Асанов М., Баранский В., Расин В.: Дискретная математика: Графы, матроиды, алгоритмы
  • Ф. Харари: Теория графов