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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 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> - количество вершин в графе.
  
''База  индукции:'' <br> Очевидно, для <tex>n = 3</tex> утверждение верно.
+
<u> ''База  индукции:'' </u>
  
''Индукционный переход:'' <br> Предположим, что теорема верна для всех турниров с <tex>n</tex> вершинами. Рассмотрим турнир <tex>T</tex> с <tex>n + 1</tex> вершинами. Пусть <tex>v_0</tex> – произвольная вершина турнира <tex>T</tex>.  Тогда турнир <tex>T</tex> – <tex>v_0</tex> имеет <tex>n</tex> вершин, значит, в нем есть гамильтонов путь <tex>P</tex>: <tex>v_1v_2...v_n</tex> . Одно из ребер ( <tex>v_0</tex>, <tex>v_1</tex> ) или ( <tex>v_1</tex>, <tex>v_0</tex> ) обязательно содержится в <tex>T</tex>. Рассмотрим 3 случая:
+
Очевидно, для <tex> n = 3 </tex> утверждение верно.
# Ребро <tex> ( v_0, v_1 ) \in T </tex>. Тогда путь <tex>v_0v_1v_2...v_n</tex> является гамильтоновым.  
+
 
# Ребро <tex> ( v_0, v_1 ) \notin T </tex>. Обозначим через <tex>v_i</tex> первую вершину пути <tex>P</tex>,  для которой ребро <tex> ( v_0, v_i ) \in T </tex>,если такая вершина есть. Тогда в <tex>T</tex> существует ребро ( <tex>v_{i-1}</tex>, <tex>v_0</tex> ) <br> и путь <tex>v_1...v_{i-1}v_0v_i...v_n</tex>– гамильтонов.  
+
<u> ''Индукционный переход:'' </u>
# Если такой вершины <tex>v_i</tex> нет, тогда гамильтоновым путем будет <tex>v_1v_2...v_nv_0</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, 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) \notin ET </tex>. Пусть <tex> 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> P \rightarrow u </tex> - гамильтонов.
 +
Значит, в любом случае в турнире существует гамильтонов путь, q.e.d.
 
}}
 
}}
  
Строка 36: Строка 44:
 
Турнир является сильно связанным тогда и только тогда, когда он имеет гамильтонов цикл.
 
Турнир является сильно связанным тогда и только тогда, когда он имеет гамильтонов цикл.
  
==Литература==
+
== Литература ==
* Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009
+
* Асанов М., Баранский В., Расин В.: ''Дискретная математика: Графы, матроиды, алгоритмы''
 +
* Ф. Харари: ''Теория графов''
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Обходы графов]]
 
[[Категория: Обходы графов]]

Версия 08:27, 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]T[/math] с [math]n[/math] вершинами [math]n \ge 3[/math] есть орцикл длины 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]. Так как [math]T[/math] сильно связан, то оба множества [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].

Индукционный переход:
Покажем, что если турнир [math]T[/math] с [math]n[/math] вершинами имеет орцикл [math]S = v_1v_2...v_kv_1[/math] длины [math]k \lt n[/math], то он имеет также орцикл длины [math]k + 1[/math]. Рассмотрим 2 случая:

  1. Существует такая вершина [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] вершину из [math]S[/math], такую, что ребро [math] ( v_1, v_0 ) \in T [/math]. Пусть [math]v_i[/math] – первая вершина при обходе контура [math]S[/math] из [math]v_1[/math], для которой ребро [math] ( v_0, v_i ) \in T [/math]. Тогда ребро [math](v_{i-1}, v_0)[/math] также содержится в [math]T[/math]. Поэтому [math]v_1v_2...v_{i-1}v_0v_i...v_kv_1[/math] – искомый орцикл длины [math]k+1[/math].
  2. Пусть такой вершины [math]v_0[/math] нет. Тогда разобьем вершины, не принадлежащие [math]S[/math], на два непересекающихся подмножества [math]W[/math] и [math]Z[/math], где [math]W[/math] - множество таких вершин [math]w[/math] , что ребро [math](v_i, w)[/math] для любого [math]i[/math] содержится в [math]T[/math], а [math]Z[/math] – множество таких вершин [math]z[/math], что ребро [math](z, v_i)[/math] для любого [math]i[/math] содержится в [math]T[/math]. Так как [math]T[/math] сильно связан, то оба множества [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] – требуемый орцикл.
Таким образом в любом сильно связанном турнире [math]T[/math] с [math]n[/math] вершинами будет орцикл длины [math]n[/math], то есть гамильтонов цикл.
[math]\triangleleft[/math]

Следствие

Турнир является сильно связанным тогда и только тогда, когда он имеет гамильтонов цикл.

Литература

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