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

Материал из Викиконспекты
Перейти к: навигация, поиск
(формулировка теоремы для пути и для цикла и ее доказательства)
(нет различий)

Версия 10:07, 12 октября 2010

Теорема Редеи-Камиона

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

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

  1. База индукции: n = 3
    Очевидно, для n = 3 утверждение верно.
  2. Индукционный переход
    Предположим, что теорема верна для всех турниров с 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 случая:
    1. Ребро ( [math]v_0[/math], [math]v_1[/math] ) принадлежит Т . Тогда путь [math]v_0v_1v_2...v_n[/math] является гамильтоновым.
    2. Обозначим через [math]v_i[/math] первую вершину пути P, для которой ребро ( [math]v_0[/math], [math]v_i[/math] ) принадлежит T ,если такая вершина есть. Тогда в T существует ребро ( [math]v[/math][math]i-1[/math], [math]v_0[/math] )
      и путь [math]v_1...v[/math][math]i-1[/math][math]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]

Докажем, что в любом сильно связанном турнире есть гамильтонов цикл, по индукции по длине цикла.

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