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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 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>
Строка 30: Строка 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>
  
Пусть <tex> T </tex> - сильно связанный турнир из <tex> n \geq 3 </tex> вершин.
 
 
{{Утверждение
 
{{Утверждение
 
|statement=
 
|statement=
В турнире <tex> T </tex> есть орцикл длины <tex> 3 </tex>.
+
Cильно связанный турнир <tex> T </tex> из <tex> n \geq 3 </tex> вершин содержит орцикл длины <tex> 3 </tex>.
 
|proof=
 
|proof=
 
Пусть <tex> u </tex> - произвольная вершина турнира <tex> T , V_1 = \{ v_1 \in VT | (u, v_1) \in ET \}, V_2 = \{ v_2 \in VT | (v_2, u) \in ET \} </tex>.
 
Пусть <tex> u </tex> - произвольная вершина турнира <tex> T , V_1 = \{ v_1 \in VT | (u, v_1) \in ET \}, V_2 = \{ v_2 \in VT | (v_2, u) \in ET \} </tex>.
Строка 47: Строка 46:
 
#* <tex> v'_1 \in V_1 </tex>
 
#* <tex> v'_1 \in V_1 </tex>
 
#* <tex> v'_2 \in V_2 </tex>
 
#* <tex> v'_2 \in V_2 </tex>
Цикл <tex> P: (u \rightarrow v'_1 \rightarrow v'_2 \rightarrow u) </tex> - искомый орцикл длины <tex> 3 </tex>, q.e.d.
+
Цикл <tex> S_3: (u \rightarrow v'_1 \rightarrow v'_2 \rightarrow u) </tex> - искомый орцикл длины <tex> 3 </tex>, q.e.d.
 
}}
 
}}
  
 
<u> ''Индукционный переход:'' </u>
 
<u> ''Индукционный переход:'' </u>
  
Покажем, что если турнир <tex> T </tex> с <tex>n</tex> вершинами имеет орцикл <tex> S = v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_k \rightarrow v_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>.
+
|statement=
# Пусть такой вершины <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> – требуемый орцикл.
+
Если сильно связанный турнир <tex> T </tex> из <tex> n \geq 3 </tex> вершин содержит орцикл <tex> S_k </tex> длины <tex> k </tex>, то он содержит и цикл длины <tex> k + 1 </tex>.
Таким образом в любом сильно связанном турнире <tex>T</tex> с <tex>n</tex> вершинами будет орцикл длины <tex>n</tex>, то есть гамильтонов цикл.
+
|proof=
 +
Пусть <tex> S_k = (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_k \rightarrow v_1) </tex>.
 +
Пусть <tex> v_0 \notin S </tex> такая, что <tex> \exists u, w \in S </tex>:
 +
* <tex> (v_0, u) \in ET </tex>
 +
* <tex> (w, v_0) \in ET </tex>.
 +
# Существует такая вершина <tex> v_0 </tex>. <br> Пусть <tex> v_1 </tex> - вершина из <tex> S </tex> такая, что ребро <tex> e = (v_1, v_0 ) \in ET </tex>. Пусть <tex> v_i </tex> – первая вершина при обходе контура <tex> S </tex> из <tex> v_1 </tex>, для которой ребро <tex> f = (v_0, v_i ) \in ET </tex>. Тогда ребро <tex> g = (v_{i - 1}, v_0) </tex> также содержится в <tex> T </tex>. <br> Тогда <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>.
 +
# Не существует такой вершины <tex> v_0 </tex>.
 +
: Пусть:
 +
:* <tex> U = \{ u \in VT | u \notin S, e = (v_i, u) \in ET, \forall i = \overline{1, n} \} </tex>
 +
:* <tex> W = \{ w \in VT | w \notin S, f = (w, v_i) \in ET, \forall i = \overline{1, n} \} </tex>
 +
:* <tex> U \cap W = \emptyset </tex>
 +
: Турнир сильно связен, следовательно:
 +
:* <tex> U \neq \emptyset </tex>
 +
:* <tex> W \neq \emptyset </tex>
 +
:* <tex> \exists g = (u', w') \in T: </tex>
 +
:** <tex> u' \in U </tex>
 +
:** <tex> w' \in W </tex>.
 +
: Тогда <tex> S_{k + 1} = (v_1 \rightarrow u' \rightarrow w' \rightarrow v_3 \rightarrow \ldots \rightarrow v_k \rightarrow v_1</tex> – искомый орцикл длины <tex> k + 1 </tex>.
 +
 
 +
Цикл <tex> S_{k + 1} </tex> - искомый орцикл длины <tex> k + 1 </tex>, q.e.d.
 +
 
 +
}}
 +
Таким образом, в любой сильно связанный турнир <tex> T </tex> из <tex> n \geq 3 </tex> вершин содержит орцикл длины <tex> n </tex>, то есть гамильтонов цикл, q.e.d.
 
}}
 
}}
  

Версия 11:19, 20 ноября 2011

Теорема (Редеи-Камиона (для пути)):
Доказательство:
[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]. Одно из ребер [math] (u, v_1) [/math] или [math] (v_1, u) [/math] обязательно содержится в [math] T [/math].

  1. Ребро [math] (u, v_1) \in ET [/math]. Тогда путь [math] (u \rightarrow P) [/math] - гамильтонов.
  2. Ребро [math] (u, v_1) \notin ET [/math]. Пусть [math] v_i [/math] - первая вершина пути [math] P [/math], для которой ребро [math] (u, v_i) \in T [/math].
    1. Если такая вершина существует, то в [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] – гамильтонов.
    2. Если такой вершины не существует, то путь [math] (P \rightarrow u) [/math] - гамильтонов.
Значит, в любом случае в турнире существует гамильтонов путь, q.e.d.
[math]\triangleleft[/math]
Теорема (Редеи-Камиона (для цикла)):
Доказательство:
[math]\triangleright[/math]

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

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

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

Пусть [math] u [/math] - произвольная вершина турнира [math] T , V_1 = \{ v_1 \in VT | (u, v_1) \in ET \}, V_2 = \{ v_2 \in VT | (v_2, u) \in ET \} [/math].

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

  1. [math] V_1 \neq \emptyset [/math]
  2. [math] V_2 \neq \emptyset [/math]
  3. [math] \exists e = (v'_1, v'_2) \in ET : [/math]
    • [math] v'_1 \in V_1 [/math]
    • [math] v'_2 \in V_2 [/math]
Цикл [math] S_3: (u \rightarrow v'_1 \rightarrow v'_2 \rightarrow u) [/math] - искомый орцикл длины [math] 3 [/math], q.e.d.
[math]\triangleleft[/math]

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

Утверждение:
Если сильно связанный турнир [math] T [/math] из [math] n \geq 3 [/math] вершин содержит орцикл [math] S_k [/math] длины [math] k [/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 \notin S [/math] такая, что [math] \exists u, w \in S [/math]:

  • [math] (v_0, u) \in ET [/math]
  • [math] (w, v_0) \in ET [/math].
  1. Существует такая вершина [math] v_0 [/math].
    Пусть [math] v_1 [/math] - вершина из [math] S [/math] такая, что ребро [math] e = (v_1, v_0 ) \in ET [/math]. Пусть [math] v_i [/math] – первая вершина при обходе контура [math] S [/math] из [math] v_1 [/math], для которой ребро [math] f = (v_0, v_i ) \in ET [/math]. Тогда ребро [math] g = (v_{i - 1}, v_0) [/math] также содержится в [math] T [/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].
  2. Не существует такой вершины [math] v_0 [/math].
Пусть:
  • [math] U = \{ u \in VT | u \notin S, e = (v_i, u) \in ET, \forall i = \overline{1, n} \} [/math]
  • [math] W = \{ w \in VT | w \notin S, f = (w, v_i) \in ET, \forall i = \overline{1, n} \} [/math]
  • [math] U \cap W = \emptyset [/math]
Турнир сильно связен, следовательно:
  • [math] U \neq \emptyset [/math]
  • [math] W \neq \emptyset [/math]
  • [math] \exists g = (u', w') \in T: [/math]
    • [math] u' \in U [/math]
    • [math] w' \in W [/math].
Тогда [math] S_{k + 1} = (v_1 \rightarrow u' \rightarrow w' \rightarrow v_3 \rightarrow \ldots \rightarrow v_k \rightarrow v_1[/math] – искомый орцикл длины [math] k + 1 [/math].
Цикл [math] S_{k + 1} [/math] - искомый орцикл длины [math] k + 1 [/math], q.e.d.
[math]\triangleleft[/math]
Таким образом, в любой сильно связанный турнир [math] T [/math] из [math] n \geq 3 [/math] вершин содержит орцикл длины [math] n [/math], то есть гамильтонов цикл, q.e.d.
[math]\triangleleft[/math]
Лемма (Следствие):
Турнир является сильно связанным тогда и только тогда, когда он имеет гамильтонов цикл.

Литература

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