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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{В разработке}}
 
{{В разработке}}
 +
 +
{{Лемма
 +
|statement=Наличие двух различных рёберно-простых путей между какими-либо двумя вершинами графа <tex>G</tex> равносильно наличию цикла в этом графе.
 +
|proof=
 +
"<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'_l</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'_{l+1} \ldots v</tex> соответственно. Найдем первую совпадающую вершину  <tex>w'</tex> в <tex>s</tex> и <tex>s'</tex>, не равную <tex>w</tex>. Осталось заметить, что замкнутый путь <tex>c</tex>, полученный объединением <tex>w \rightarrow w'</tex> части пути <tex>s</tex> вместе с  <tex>w' \rightarrow w</tex> частью цепи <tex>s'</tex> является циклическим путем. Действительно, т. r. в  путях <tex>s</tex> и <tex>s'</tex>  двух ребер подряд не бывает, т.к. это реберно простые пути, а ребра, смежные с <tex>w</tex> и <tex>w'</tex> не совпадают по построению. Циклический путь <tex>c</tex> является представителем некоторого цикла в графе <tex>G</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>.
 +
}}
 +
  
 
{{Теорема
 
{{Теорема
Строка 5: Строка 18:
 
Если в неориентированном графе существует цикл, то в этом графе существует простой цикл.
 
Если в неориентированном графе существует цикл, то в этом графе существует простой цикл.
 
|proof=
 
|proof=
Заметим, что наличие цикла в графе равносильно существованию двух реберно-простых путей между некоторыми вершинами в этом графе.
+
Воспользуемся доказанной выше леммой. Так как в нашем графе существует цикл, то существуют два реберно-простых пути между некоторыми вершинами: <tex>v_0e_1v_1e_2v_2 ... e_nv_n</tex>, <tex>v'_0e'_1v'_1e'_2v'_2 ... e'_mv'_m</tex>, <tex>v_0 = v'_0</tex>, <tex>v_n = v'_m</tex>. Удалим из путей одинаковые префиксы и суффиксы, оставив из тех только последние и первые вершины, соответственно. Оставшиеся пути: <tex>v_ae_{a+1} ... e_bv_b</tex>, <tex>v'_ae'_{a+1} ... e'_cv'_c</tex>, <tex>v_a = v'_a</tex>, <tex>v_b = v'_c</tex>, <tex>e_{a+1} \neq e'_{a+1}</tex>, <tex>e_b \neq e'_c</tex>.
  
Возьмём два существующих пути между нужными нам вершинами: <tex>V_0E_1V_1E_2V_2 ... E_nV_n</tex>, <tex>v_0e_1v_1e_2v_2 ... e_mv_m</tex>, <tex>V_0 = v_0</tex>, <tex>V_n = v_m</tex>. Удалим из путей одинаковые префиксы и суффиксы, оставив из тех только последние и первые вершины, соответственно. Оставшиеся пути: <tex>V_aE_{a+1} ... E_bV_b</tex>, <tex>v_ae_{a+1} ... e_cv_c</tex>, <tex>V_a = v_a</tex>, <tex>V_b = v_c</tex>, <tex>E_{a+1} \neq e_{a+1}</tex>, <tex>E_b \neq e_c</tex>.
+
Рассмотрим конкатенацию первого нового пути и развёрнутого второго нового пути. Она будет циклом, так как начальная и конечная вершины совпадают, изначально пути были рёберно-простыми, а в точке соединения, равно как и в точке замыкания цикла, условие различности двух идущих подряд рёбер выполняется. Мы получили цикл, определим его: <tex>v_0e_1v_1 ... e_kv_k</tex>, <tex>v_0 = v_k</tex>.
 
 
Рассмотрим конкатенацию первого нового пути и развёрнутого второго нового пути. Она будет циклом, так как начальная и конечная вершины совпадают, изначально пути были рёберно-простыми, а в точке соединения, равно как и в точке замыкания цикла, условие различности двух идущих подряд рёбер выполняется. Мы получили цикл, определим его: <tex>V_0E_1V_1 ... E_kV_k</tex>, <tex>V_0 = V_k</tex>.
 
  
 
* Алгоритм:
 
* Алгоритм:
  1. Для вершины <tex>V_i</tex> найдём момент её последнего вхождения в цикл - <tex>V_j</tex>.
+
  1. Для вершины <tex>v_i</tex> найдём момент её последнего вхождения в цикл - <tex>v_j</tex>.
  2. Удалим отрезок цикла от <tex>E_{i+1}</tex> до <tex>V_j</tex>, включительно.
+
  2. Удалим отрезок цикла от <tex>e_{i+1}</tex> до <tex>v_j</tex>, включительно.
  Получившаяся последовательность вершин и рёбер графа останется циклом, и в нём вершина <tex>V_i</tex> будет содержаться ровно один раз.
+
  Получившаяся последовательность вершин и рёбер графа останется циклом, и в нём вершина <tex>v_i</tex> будет содержаться ровно один раз.
Начнём процесс с вершины <tex>V_1</tex> и будем повторять его каждый раз для следующей вершины нового цикла, пока не дойдём до последней. По построению, получившийся цикл будет содержать каждую из вершин графа не более одного раза, а значит, будет простым.
+
Начнём процесс с вершины <tex>v_1</tex> и будем повторять его каждый раз для следующей вершины нового цикла, пока не дойдём до последней. По построению, получившийся цикл будет содержать каждую из вершин графа не более одного раза, а значит, будет простым.
 
}}
 
}}
  
 
[[Файл: prime_c.png|thumb|600px|center|Для вершины 2 находим последнее ее вхождение в цикл и удаляем отрезок цикла, выделенный <font color=#22B14C>зеленым.</font><br>[(2, 5) - 5 - (5, 6) - 6 - (6, 4) - 4 - (4, 2) - 2]]]
 
[[Файл: prime_c.png|thumb|600px|center|Для вершины 2 находим последнее ее вхождение в цикл и удаляем отрезок цикла, выделенный <font color=#22B14C>зеленым.</font><br>[(2, 5) - 5 - (5, 6) - 6 - (6, 4) - 4 - (4, 2) - 2]]]
  
{{Лемма
 
|statement=Наличие двух различных рёберно-простых путей между какими-либо двумя вершинами графа <tex>G</tex> равносильно наличию цикла в этом графе.
 
|proof=
 
"<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'_l</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'_{l+1} \ldots v</tex> соответственно. Найдем первую совпадающую вершину  <tex>w'</tex> в <tex>s</tex> и <tex>s'</tex>, не равную <tex>w</tex>. Осталось заметить, что замкнутый путь <tex>c</tex>, полученный объединением <tex>w \rightarrow w'</tex> части пути <tex>s</tex> вместе с  <tex>w' \rightarrow w</tex> частью цепи <tex>s'</tex> является циклическим путем. Действительно, т. r. в  путях <tex>s</tex> и <tex>s'</tex>  двух ребер подряд не бывает, т.к. это реберно простые пути, а ребра, смежные с <tex>w</tex> и <tex>w'</tex> не совпадают по построению. Циклический путь <tex>c</tex> является представителем некоторого цикла в графе <tex>G</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>.
 
}}
 
 
== Замечания ==
 
== Замечания ==
 
* Так как вершинно-простой путь всегда является рёберно-простым, первая теорема справедлива и для вершинно-простых путей (усиление условия).
 
* Так как вершинно-простой путь всегда является рёберно-простым, первая теорема справедлива и для вершинно-простых путей (усиление условия).

Версия 01:46, 25 февраля 2012

Эта статья находится в разработке!
Лемма:
Наличие двух различных рёберно-простых путей между какими-либо двумя вершинами графа [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'_l[/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'_{l+1} \ldots v[/math] соответственно. Найдем первую совпадающую вершину [math]w'[/math] в [math]s[/math] и [math]s'[/math], не равную [math]w[/math]. Осталось заметить, что замкнутый путь [math]c[/math], полученный объединением [math]w \rightarrow w'[/math] части пути [math]s[/math] вместе с [math]w' \rightarrow w[/math] частью цепи [math]s'[/math] является циклическим путем. Действительно, т. r. в путях [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]\triangleright[/math]

Воспользуемся доказанной выше леммой. Так как в нашем графе существует цикл, то существуют два реберно-простых пути между некоторыми вершинами: [math]v_0e_1v_1e_2v_2 ... e_nv_n[/math], [math]v'_0e'_1v'_1e'_2v'_2 ... e'_mv'_m[/math], [math]v_0 = v'_0[/math], [math]v_n = v'_m[/math]. Удалим из путей одинаковые префиксы и суффиксы, оставив из тех только последние и первые вершины, соответственно. Оставшиеся пути: [math]v_ae_{a+1} ... e_bv_b[/math], [math]v'_ae'_{a+1} ... e'_cv'_c[/math], [math]v_a = v'_a[/math], [math]v_b = v'_c[/math], [math]e_{a+1} \neq e'_{a+1}[/math], [math]e_b \neq e'_c[/math].

Рассмотрим конкатенацию первого нового пути и развёрнутого второго нового пути. Она будет циклом, так как начальная и конечная вершины совпадают, изначально пути были рёберно-простыми, а в точке соединения, равно как и в точке замыкания цикла, условие различности двух идущих подряд рёбер выполняется. Мы получили цикл, определим его: [math]v_0e_1v_1 ... e_kv_k[/math], [math]v_0 = v_k[/math].

  • Алгоритм:
1. Для вершины [math]v_i[/math] найдём момент её последнего вхождения в цикл - [math]v_j[/math].
2. Удалим отрезок цикла от [math]e_{i+1}[/math] до [math]v_j[/math], включительно.
Получившаяся последовательность вершин и рёбер графа останется циклом, и в нём вершина [math]v_i[/math] будет содержаться ровно один раз.
Начнём процесс с вершины [math]v_1[/math] и будем повторять его каждый раз для следующей вершины нового цикла, пока не дойдём до последней. По построению, получившийся цикл будет содержать каждую из вершин графа не более одного раза, а значит, будет простым.
[math]\triangleleft[/math]
Для вершины 2 находим последнее ее вхождение в цикл и удаляем отрезок цикла, выделенный зеленым.
[(2, 5) - 5 - (5, 6) - 6 - (6, 4) - 4 - (4, 2) - 2]

Замечания

  • Так как вершинно-простой путь всегда является рёберно-простым, первая теорема справедлива и для вершинно-простых путей (усиление условия).
  • Так как вершинно-простой цикл всегда является рёберно-простым, первая теорема справедлива и для рёберно-простого цикла (ослабление результата).
  • Утверждение

Если две вершины графа лежат на цикле, то они лежат на простом цикле.

в общем случае неверно, так как эти вершины могут лежать в разных компонентах вершинной или рёберной двусвязности: все пути из одной вершины в другую будут содержать одну и ту же точку сочленения или один и тот же мост.

См. также