Теорема о существовании простого цикла в случае существования цикла — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Добавлена иллюстрация к лемме)
м
 
(не показаны 2 промежуточные версии 2 участников)
Строка 4: Строка 4:
 
<tex>\Rightarrow</tex>
 
<tex>\Rightarrow</tex>
  
Предположим, что в графе <tex>G</tex> существует два различных рёберно простых пути между вершинами <tex>u</tex> и <tex>v</tex>. Пусть это будут пути <tex>p = u e_1 v_1\ldots v_{n-1} e_n v</tex> и <tex>p' = u e'_1 v'_1\ldots v'_{n-1} e'_n v</tex>. Пусть их наибольший общий префикс заканчивается в вершине <tex>w = v_k = v'_k</tex>. Заметим, что <tex>w \neq v</tex>, т.к. пути различны. Рассмотрим суффиксы путей <tex>p</tex> и <tex>p'</tex>: <tex>s = w e_{k+1} \ldots  v</tex> и <tex>s' = w e'_{k+1} \ldots v</tex> соответственно. Найдем первую совпадающую вершину  <tex>w'</tex> в <tex>s</tex> и <tex>s'</tex>, не равную <tex>w</tex>. Осталось заметить, что замкнутый путь <tex>c</tex>, полученный объединением <tex>w \leadsto w'</tex> части пути <tex>s</tex> вместе с <tex>w' \leadsto w</tex> частью цепи <tex>s'</tex>, является циклическим путем. Действительно, в  путях <tex>s</tex> и <tex>s'</tex> двух одинаковых рёбер подряд не бывает, т.к. это рёберно простые пути, а рёбра, смежные с <tex>w</tex> и <tex>w'</tex>, не совпадают по построению. Циклический путь <tex>c</tex> является представителем некоторого цикла в графе <tex>G</tex>.
+
Предположим, что в графе <tex>G</tex> существует два различных рёберно простых пути между вершинами <tex>u</tex> и <tex>v</tex>. Пусть это будут пути <tex>p = u e_1 v_1\ldots v_{n-1} e_n v</tex> и <tex>p' = u e'_1 v'_1\ldots v'_{n-1} e'_n v</tex>. Пусть их наибольший общий префикс заканчивается в вершине <tex>w = v_k = v'_k</tex>. Заметим, что <tex>w \neq v</tex>, т.к. пути различны. Рассмотрим суффиксы путей <tex>p</tex> и <tex>p'</tex>: <tex>s = w e_{k+1} \ldots  v</tex> и <tex>s' = w e'_{k+1} \ldots v</tex> соответственно. Найдём первую совпадающую вершину  <tex>w'</tex> в <tex>s</tex> и <tex>s'</tex>, не равную <tex>w</tex>. Осталось заметить, что замкнутый путь <tex>c</tex>, полученный объединением <tex>w \leadsto w'</tex> части пути <tex>s</tex> вместе с <tex>w' \leadsto w</tex> частью цепи <tex>s'</tex>, является циклическим путем. Действительно, в  путях <tex>s</tex> и <tex>s'</tex> двух одинаковых рёбер подряд не бывает, т.к. это рёберно простые пути, а рёбра, смежные с <tex>w</tex> и <tex>w'</tex>, не совпадают по построению. Циклический путь <tex>c</tex> является представителем некоторого цикла в графе <tex>G</tex>.
  
 
<tex>\Leftarrow</tex>
 
<tex>\Leftarrow</tex>
  
Предположим, что в графе <tex>G</tex> существует цикл и пусть циклический путь <tex>c = v_0 e_1 v_1 \ldots e_n v_0</tex> {{---}}  его представитель. Найдем первую точку <tex>w = v_k = v_l (l > k)</tex> пересечения <tex>c</tex> с самим собой.  Такая точка существует, т.к. путь замкнутый. Рассмотрим циклический путь <tex>v_k e_{k+1} \ldots e_l v_l</tex>: он простой, т. к. если это неверно и существует вершина <tex>v_j = v_j' (k < j < j' < l)</tex>, то в <tex>c</tex> вершина <tex>v_j'</tex> повторяется раньше, чем <tex>v_l</tex>. Теперь элементарно взяв две вершины <tex>v_k</tex> и <tex>v_{k+1}</tex> легко заметить, что существует два различных рёберно непересекающихся пути между ними: <tex>v_k e_{k+1} v_{k+1}</tex> и <tex>v_k e_l v_{l - 1} \ldots v_k</tex>.
+
Предположим, что в графе <tex>G</tex> существует цикл и пусть циклический путь <tex>c = v_0 e_1 v_1 \ldots e_n v_0</tex> {{---}}  его представитель. Найдём первую точку <tex>w = v_k = v_l (l > k)</tex> пересечения <tex>c</tex> с самим собой.  Такая точка существует, т.к. путь замкнутый. Рассмотрим циклический путь <tex>v_k e_{k+1} \ldots e_l v_l</tex>: он простой, т. к. если это неверно и существует вершина <tex>v_j = v_j' (k < j < j' < l)</tex>, то в <tex>c</tex> вершина <tex>v_j'</tex> повторяется раньше, чем <tex>v_l</tex>. Теперь элементарно взяв две вершины <tex>v_k</tex> и <tex>v_{k+1}</tex> легко заметить, что существует два различных рёберно непересекающихся пути между ними: <tex>v_k e_{k+1} v_{k+1}</tex> и <tex>v_k e_l v_{l - 1} \ldots v_k</tex>.
 
  }}
 
  }}
 
[[Файл:2_paths_and_a_cycle.png|600px|thumb|center|Иллюстрация к лемме: пути отмечены соответственно <font color="f00000">красным</font> и <font color="0000f0">синим</font> (их общий префикс отмечен пунктиром), а циклический путь <tex>c</tex> проходит вдоль чёрных стрелок]]
 
[[Файл:2_paths_and_a_cycle.png|600px|thumb|center|Иллюстрация к лемме: пути отмечены соответственно <font color="f00000">красным</font> и <font color="0000f0">синим</font> (их общий префикс отмечен пунктиром), а циклический путь <tex>c</tex> проходит вдоль чёрных стрелок]]
Строка 18: Строка 18:
 
Выберем в графе минимальный по количеству рёбер цикл (он существует, потому что количество рёбер в любом цикле — натуральное число <ref>[[Натуральные и целые числа#.D0.A1.D1.83.D1.89.D0.B5.D1.81.D1.82.D0.B2.D0.BE.D0.B2.D0.B0.D0.BD.D0.B8.D0.B5_.D0.BD.D0.B0.D0.B8.D0.BC.D0.B5.D0.BD.D1.8C.D1.88.D0.B5.D0.B3.D0.BE_.D1.8D.D0.BB.D0.B5.D0.BC.D0.B5.D0.BD.D1.82.D0.B0|Существование наименьшего элемента в любом подмножестве <tex>\Bbb N</tex>]]</ref>). Предположим, что он не простой. Но тогда он содержит дважды одну и ту же вершину, т. е. содержит в себе цикл меньшего размера, что противоречит тому, что наш цикл минимальный. Таким образом, этот цикл — простой.}}
 
Выберем в графе минимальный по количеству рёбер цикл (он существует, потому что количество рёбер в любом цикле — натуральное число <ref>[[Натуральные и целые числа#.D0.A1.D1.83.D1.89.D0.B5.D1.81.D1.82.D0.B2.D0.BE.D0.B2.D0.B0.D0.BD.D0.B8.D0.B5_.D0.BD.D0.B0.D0.B8.D0.BC.D0.B5.D0.BD.D1.8C.D1.88.D0.B5.D0.B3.D0.BE_.D1.8D.D0.BB.D0.B5.D0.BC.D0.B5.D0.BD.D1.82.D0.B0|Существование наименьшего элемента в любом подмножестве <tex>\Bbb N</tex>]]</ref>). Предположим, что он не простой. Но тогда он содержит дважды одну и ту же вершину, т. е. содержит в себе цикл меньшего размера, что противоречит тому, что наш цикл минимальный. Таким образом, этот цикл — простой.}}
  
[[Файл:Simple cycle.png|thumb|580px|center|В графе минимальный цикл включает в себя четыре ребра — таких цикла два: [2 - 6 - 7 - 3] (выделен <font color="red">красным</font>) и [2 - 5 - 6 - 4] (выделен <font color=#3771c8ff>синим</font>). Согласно теореме, оба они просты.<br>]]
+
[[Файл:Simple cycle.png|thumb|580px|center|В графе минимальный цикл включает в себя три ребра — например, [2 - 5 - 6] (выделен <font color="red">красным</font>). Согласно теореме, он является простым.<br>]]
  
 
== Замечания ==
 
== Замечания ==
 
* Так как вершинно-простой путь всегда является рёберно-простым, первая теорема справедлива и для вершинно-простых путей (усиление условия).
 
* Так как вершинно-простой путь всегда является рёберно-простым, первая теорема справедлива и для вершинно-простых путей (усиление условия).
 
* Так как вершинно-простой цикл всегда является рёберно-простым, первая теорема справедлива и для рёберно-простого цикла (ослабление результата).
 
* Так как вершинно-простой цикл всегда является рёберно-простым, первая теорема справедлива и для рёберно-простого цикла (ослабление результата).
* {{Утверждение
+
{{Утверждение
  |statement=''Если две вершины графа лежат на цикле, то они лежат на простом цикле.''
+
|about=неверное
 +
|statement=''Если две вершины графа лежат на цикле, то они лежат на простом цикле.''
 +
|proof=
 +
В общем случае неверно, так как эти вершины могут лежать в разных компонентах вершинной или рёберной двусвязности: все пути из одной вершины в другую будут содержать одну и ту же [[Точка сочленения, эквивалентные определения|точку сочленения]] или один и тот же [[Мост, эквивалентные определения|мост]].
 
}}
 
}}
в общем случае неверно, так как эти вершины могут лежать в разных компонентах вершинной или рёберной двусвязности: все пути из одной вершины в другую будут содержать одну и ту же [[Точка сочленения, эквивалентные определения|точку сочленения]] или один и тот же [[Мост, эквивалентные определения|мост]].
 
  
 
== Примечания ==
 
== Примечания ==
Строка 33: Строка 35:
 
== См. также ==
 
== См. также ==
 
* [[Теорема о существовании простого пути в случае существования пути]]
 
* [[Теорема о существовании простого пути в случае существования пути]]
* [[Отношение реберной двусвязности]]
+
* [[Отношение рёберной двусвязности]]
 
* [[Отношение вершинной двусвязности]]
 
* [[Отношение вершинной двусвязности]]
  

Текущая версия на 16:24, 1 февраля 2017

Лемма:
Наличие двух различных рёберно простых путей между какими-либо двумя вершинами неориентированного графа [math]G[/math] равносильно наличию цикла в этом графе.
Доказательство:
[math]\triangleright[/math]

[math]\Rightarrow[/math]

Предположим, что в графе [math]G[/math] существует два различных рёберно простых пути между вершинами [math]u[/math] и [math]v[/math]. Пусть это будут пути [math]p = u e_1 v_1\ldots v_{n-1} e_n v[/math] и [math]p' = u e'_1 v'_1\ldots v'_{n-1} e'_n v[/math]. Пусть их наибольший общий префикс заканчивается в вершине [math]w = v_k = v'_k[/math]. Заметим, что [math]w \neq v[/math], т.к. пути различны. Рассмотрим суффиксы путей [math]p[/math] и [math]p'[/math]: [math]s = w e_{k+1} \ldots v[/math] и [math]s' = w e'_{k+1} \ldots v[/math] соответственно. Найдём первую совпадающую вершину [math]w'[/math] в [math]s[/math] и [math]s'[/math], не равную [math]w[/math]. Осталось заметить, что замкнутый путь [math]c[/math], полученный объединением [math]w \leadsto w'[/math] части пути [math]s[/math] вместе с [math]w' \leadsto w[/math] частью цепи [math]s'[/math], является циклическим путем. Действительно, в путях [math]s[/math] и [math]s'[/math] двух одинаковых рёбер подряд не бывает, т.к. это рёберно простые пути, а рёбра, смежные с [math]w[/math] и [math]w'[/math], не совпадают по построению. Циклический путь [math]c[/math] является представителем некоторого цикла в графе [math]G[/math].

[math]\Leftarrow[/math]

Предположим, что в графе [math]G[/math] существует цикл и пусть циклический путь [math]c = v_0 e_1 v_1 \ldots e_n v_0[/math] — его представитель. Найдём первую точку [math]w = v_k = v_l (l \gt k)[/math] пересечения [math]c[/math] с самим собой. Такая точка существует, т.к. путь замкнутый. Рассмотрим циклический путь [math]v_k e_{k+1} \ldots e_l v_l[/math]: он простой, т. к. если это неверно и существует вершина [math]v_j = v_j' (k \lt j \lt j' \lt l)[/math], то в [math]c[/math] вершина [math]v_j'[/math] повторяется раньше, чем [math]v_l[/math]. Теперь элементарно взяв две вершины [math]v_k[/math] и [math]v_{k+1}[/math] легко заметить, что существует два различных рёберно непересекающихся пути между ними: [math]v_k e_{k+1} v_{k+1}[/math] и [math]v_k e_l v_{l - 1} \ldots v_k[/math].
[math]\triangleleft[/math]
Иллюстрация к лемме: пути отмечены соответственно красным и синим (их общий префикс отмечен пунктиром), а циклический путь [math]c[/math] проходит вдоль чёрных стрелок
Теорема:
Если в неориентированном графе существует цикл, то в этом графе существует простой цикл.
Доказательство:
[math]\triangleright[/math]
Выберем в графе минимальный по количеству рёбер цикл (он существует, потому что количество рёбер в любом цикле — натуральное число [1]). Предположим, что он не простой. Но тогда он содержит дважды одну и ту же вершину, т. е. содержит в себе цикл меньшего размера, что противоречит тому, что наш цикл минимальный. Таким образом, этот цикл — простой.
[math]\triangleleft[/math]
В графе минимальный цикл включает в себя три ребра — например, [2 - 5 - 6] (выделен красным). Согласно теореме, он является простым.

Замечания[править]

  • Так как вершинно-простой путь всегда является рёберно-простым, первая теорема справедлива и для вершинно-простых путей (усиление условия).
  • Так как вершинно-простой цикл всегда является рёберно-простым, первая теорема справедлива и для рёберно-простого цикла (ослабление результата).
Утверждение (неверное):
Если две вершины графа лежат на цикле, то они лежат на простом цикле.
[math]\triangleright[/math]
В общем случае неверно, так как эти вершины могут лежать в разных компонентах вершинной или рёберной двусвязности: все пути из одной вершины в другую будут содержать одну и ту же точку сочленения или один и тот же мост.
[math]\triangleleft[/math]

Примечания[править]

См. также[править]