Изменения

{{В разработке}} {{ТеоремаЛемма|statement=Если в неориентированном графе существует цикл, то Наличие двух различных рёберно простых путей между какими-либо двумя вершинами неориентированного [[Основные определения теории графов|графа]] <tex>G</tex> равносильно наличию цикла в этом графе существует простой цикл.

Возьмём Предположим, что в графе <tex>G</tex> существует два существующих различных рёберно простых пути между нужными нам вершинами: <tex>V_0E_1V_1E_2V_2 ... E_nV_nu</tex>, и <tex>v</tex>v_0e_1v_1e_2v_2 ... e_mv_mПусть это будут пути <tex>p = u e_1 v_1\ldots v_{n-1} e_n v</tex>, и <tex>V_0 p' = v_0u e'_1 v'_1\ldots v'_{n-1} e'_n v</tex>, . Пусть их наибольший общий префикс заканчивается в вершине <tex>V_n w = v_mv_k = v'_k</tex>. Удалим из путей одинаковые префиксы и суффиксыЗаметим, оставив из тех только последние и первые вершинычто <tex>w \neq v</tex>, соответственнот.к. Оставшиеся путиразличны. Рассмотрим суффиксы путей <tex>p</tex> и <tex>p'</tex>: <tex>V_aE_s = w e_{ak+1} ... E_bV_b\ldots v</tex>, и <tex>v_ae_s' = w e'_{ak+1} \ldots v</tex> соответственно.Найдём первую совпадающую вершину <tex>w'</tex> в <tex>s</tex> и <tex>s'</tex>, не равную <tex>w</tex>.. e_cv_cОсталось заметить, что замкнутый путь <tex>c</tex>, полученный объединением <tex>w \leadsto w'</tex> части пути <tex>s</tex> вместе с <tex>w' \leadsto w</tex>V_a = v_aчастью цепи <tex>s'</tex>, является циклическим путем. Действительно, в путях <tex>s</tex> и <tex>V_b = v_cs'</tex>двух одинаковых рёбер подряд не бывает, т.к. это рёберно простые пути, а рёбра, смежные с <tex>w</tex>E_{a+1} \neq e_{a+1}и <tex>w'</tex>, не совпадают по построению. Циклический путь <tex>c</tex>E_b \neq e_cявляется представителем некоторого цикла в графе <tex>G</tex>.

Рассмотрим конкатенацию первого нового пути и развёрнутого второго нового пути. Она будет циклом, так как начальная и конечная вершины совпадают, изначально пути были рёберно-простыми, а в точке соединения, равно как и в точке замыкания цикла, условие различности двух идущих подряд рёбер выполняется. Мы получили цикл, определим его: <tex>V_0E_1V_1 ... E_kV_k\Leftarrow</tex>, <tex>V_0 = V_k</tex>.

* Алгоритм:Предположим, что в графе <tex>G</tex> существует цикл и пусть циклический путь <tex>c = v_0 e_1 v_1 \ldots e_n v_0</tex> {{---}} 1его представитель. Для вершины Найдём первую точку <tex>V_iw = v_k = v_l (l > k)</tex> найдём момент её последнего вхождения в цикл - пересечения <tex>V_jc</tex>с самим собой. 2Такая точка существует, т. Удалим отрезок цикла от к. путь замкнутый. Рассмотрим циклический путь <tex>E_v_k e_{ik+1}\ldots e_l v_l</tex> до : он простой, т. к. если это неверно и существует вершина <tex>V_jv_j = v_j' (k < j < j' < l)</tex>, включительно. Получившаяся последовательность вершин и рёбер графа останется циклом, и то в нём <tex>c</tex> вершина <tex>V_iv_j'</tex> повторяется раньше, чем <tex>v_l</tex> будет содержаться ровно один раз.Начнём процесс с Теперь элементарно взяв две вершины <tex>V_1v_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> проходит вдоль чёрных стрелок]]

[[Файл: 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> равносильно наличию цикла Если в неориентированном графе существует цикл, то в этом графесуществует простой цикл.

"<tex>\Rightarrow</tex>" ПредположимВыберем в графе минимальный по количеству рёбер цикл (он существует, потому что количество рёбер в графе <tex>G</tex> существует два различных реберно-простых пути между вершинами любом цикле — натуральное число <tex>u</texref> [[Натуральные и <tex>v</tex>целые числа#.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. Пусть это будут пути <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>B5. Пусть их наибольший общий префикс заканчивается в вершине <tex>w = v_k = v'_l</tex>D0. Заметим, что <tex>w \neq v</tex>, тBD. кD1. пути различны82. Рассмотрим суффиксы путей <tex>p</tex> и <tex>p'</tex>: <tex>s = w e_{k+1} \ldots v</tex> и <tex>s' = w e'_{l+1} \ldots v</tex> соответственноD0. Найдем первую совпадающую вершину <tex>w'</tex> B0|Существование наименьшего элемента в любом подмножестве <tex>s</tex> и <tex>s'\Bbb N</tex>, не равную <tex>w]]</texref>). Осталось заметитьПредположим, что замкнутый путь <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>этот цикл — простой.}}

[[Файл:Simple cycle.png|thumb|580px|center|В графе минимальный цикл включает в себя три ребра — например, [2 - 5 - 6] (выделен <font color="red">красным<tex/font>\Leftarrow). Согласно теореме, он является простым.</texbr>"]]

* {{Утверждение|about=неверное|statement=''Если две вершины графа лежат на цикле, то они лежат на простом цикле.''|proof=В общем случае неверно, так как эти вершины могут лежать в разных компонентах вершинной или рёберной двусвязности: все пути из одной вершины в другую будут содержать одну и ту же [[Точка сочленения, эквивалентные определения|точку сочленения]] или один и тот же [[Мост, эквивалентные определения|мост]].}}

* [[Отношение реберной рёберной двусвязности]]