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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 20: Строка 20:
 
Одно из ребер <tex> (u, v_1) </tex> или <tex> (v_1, u) </tex> обязательно содержится в <tex> T </tex>.
 
Одно из ребер <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) \in ET </tex>, то путь <tex> (u \rightarrow P) </tex> {{---}} гамильтонов.
[[Файл: Redei_kamion_2.png|250px|thumb|center|<font color=#ED1C24>Красным</font> цветом выделен искомый путь]]
+
[[Файл: Redei_kamion_2.png|250px|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> (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> – гамильтонов.
 
Если такая вершина существует, то в <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|250px|thumb|center|<font color=#ED1C24>Красным</font> цветом выделен искомый путь]]
+
[[Файл: Redei_kamion_3.png|250px|thumb|center|<font color=#ff2a2a>Красным</font> цветом выделен искомый путь]]
  
 
Если такой вершины не существует, то путь <tex> (P \rightarrow u) </tex> {{---}} гамильтонов.
 
Если такой вершины не существует, то путь <tex> (P \rightarrow u) </tex> {{---}} гамильтонов.
[[Файл: Redei_kamion_4.png|250px|thumb|center|<font color=#ED1C24>Красным</font> цветом выделен искомый путь]]
+
[[Файл: Redei_kamion_4.png|250px|thumb|center|<font color=#ff2a2a>Красным</font> цветом выделен искомый путь]]
  
 
Значит, в любом случае в турнире существует гамильтонов путь, q.e.d.
 
Значит, в любом случае в турнире существует гамильтонов путь, q.e.d.
Строка 57: Строка 57:
 
#* <tex> w_1 \in V_1 </tex>,
 
#* <tex> w_1 \in V_1 </tex>,
 
#* <tex> w_2 \in V_2 </tex>.
 
#* <tex> w_2 \in V_2 </tex>.
[[Файл: Redei_kamion_6.png|350px|thumb|center|<font color=#ED1C24>Красным</font> цветом выделен цикл длины <tex> 3 </tex>]]
+
[[Файл: Redei_kamion_6.png|350px|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.
 
Цикл <tex> S_3: (u \rightarrow w_2 \rightarrow w_1 \rightarrow u) </tex> {{---}} искомый цикл длины <tex> 3 </tex>, q.e.d.
Строка 85: Строка 85:
  
 
Тогда ребро <tex> g = (v_{i - 1}, v_0) \in ET </tex>.
 
Тогда ребро <tex> g = (v_{i - 1}, v_0) \in ET </tex>.
[[Файл: Redei_kamion_8.png|250px|thumb|center|<font color=#ED1C24>Красным</font> цветом выделен искомый цикл длины <tex> k + 1 </tex> ]]
+
[[Файл: Redei_kamion_8.png|250px|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>.
 
Тогда <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>.
Строка 103: Строка 103:
 
** <tex> w_1 \in V_1 </tex>,
 
** <tex> w_1 \in V_1 </tex>,
 
** <tex> w_2 \in V_2 </tex>.
 
** <tex> w_2 \in V_2 </tex>.
[[Файл: Redei_kamion_10.png|350px|thumb|center|<font color=#ED1C24>Красным</font> цветом выделен цикл длины <tex> k + 1 </tex>]]
+
[[Файл: Redei_kamion_10.png|350px|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>.
 
Тогда <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>.
  

Версия 21:18, 23 апреля 2012

Теорема (Редеи-Камиона (для пути)):
Доказательство:
[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 \geq 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 | (v_1, u) \in ET \} [/math],
  • [math] V_2 = \{ v_2 \in VT | (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 \geq 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 | u \notin S_k, e = (u, v_i) \in ET, \forall i = \overline{1, n} \} [/math],
  • [math] V_2 = \{ u \in VT | 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 \geq 3 [/math] вершинами содержит цикл длины [math] n [/math], то есть гамильтонов цикл, q.e.d.
[math]\triangleleft[/math]
Теорема (Следствие):
Турнир является сильно связанным тогда и только тогда, когда он имеет гамильтонов цикл.

См. также

Литература

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