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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 26: Строка 26:
 
''Индукционный переход:'' <br> Покажем, что если турнир <tex>T</tex> с <tex>n</tex> вершинами имеет орцикл <tex>S = v_1v_2...v_kv_1</tex> длины <tex>k < n</tex>, то он имеет также орцикл длины <tex>k + 1</tex>.  Рассмотрим 2 случая:
 
''Индукционный переход:'' <br> Покажем, что если турнир <tex>T</tex> с <tex>n</tex> вершинами имеет орцикл <tex>S = v_1v_2...v_kv_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>.
 
# Существует такая вершина <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>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>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_2...v_k v_1</tex> – требуемый орцикл.
 
Таким образом в любом сильно связанном турнире <tex>T</tex> с <tex>n</tex> вершинами будет орцикл длины <tex>n</tex>, то есть гамильтонов цикл.
 
Таким образом в любом сильно связанном турнире <tex>T</tex> с <tex>n</tex> вершинами будет орцикл длины <tex>n</tex>, то есть гамильтонов цикл.
 
}}
 
}}

Версия 00:09, 26 января 2011

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

Докажем,что в любом турнире есть гамильтонов путь по индукции по числу вершин [math]n[/math].

База индукции:
Очевидно, для [math]n = 3[/math] утверждение верно.

Индукционный переход:
Предположим, что теорема верна для всех турниров с [math]n[/math] вершинами. Рассмотрим турнир [math]T[/math] с [math]n + 1[/math] вершинами. Пусть [math]v_0[/math] – произвольная вершина турнира [math]T[/math]. Тогда турнир [math]T[/math][math]v_0[/math] имеет [math]n[/math] вершин, значит, в нем есть гамильтонов путь [math]P[/math]: [math]v_1v_2...v_n[/math] . Одно из ребер ( [math]v_0[/math], [math]v_1[/math] ) или ( [math]v_1[/math], [math]v_0[/math] ) обязательно содержится в [math]T[/math]. Рассмотрим 3 случая:

  1. Ребро [math] ( v_0, v_1 ) \in T [/math]. Тогда путь [math]v_0v_1v_2...v_n[/math] является гамильтоновым.
  2. Ребро [math] ( v_0, v_1 ) \notin T [/math]. Обозначим через [math]v_i[/math] первую вершину пути [math]P[/math], для которой ребро [math] ( v_0, v_i ) \in T [/math],если такая вершина есть. Тогда в [math]T[/math] существует ребро ( [math]v_{i-1}[/math], [math]v_0[/math] )
    и путь [math]v_1...v_{i-1}v_0v_i...v_n[/math]– гамильтонов.
  3. Если такой вершины [math]v_i[/math] нет, тогда гамильтоновым путем будет [math]v_1v_2...v_nv_0[/math].
Итак, в любом случае в турнире существует гамильтонов путь.
[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_2...v_k v_1[/math] – требуемый орцикл.
Таким образом в любом сильно связанном турнире [math]T[/math] с [math]n[/math] вершинами будет орцикл длины [math]n[/math], то есть гамильтонов цикл.
[math]\triangleleft[/math]

Следствие

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

Литература

  • Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009