Изменения

|statement=Наличие двух различных рёберно-простых путей между какими-либо двумя вершинами неориентированного [[Основные определения теории графов|графа ]] <tex>G</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'_l_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'_{lk+1} \ldots v</tex> соответственно. Найдем Найдём первую совпадающую вершину <tex>w'</tex> в <tex>s</tex> и <tex>s'</tex>, не равную <tex>w</tex>. Осталось заметить, что замкнутый путь <tex>c</tex>, полученный объединением <tex>w \rightarrow leadsto w'</tex> части пути <tex>s</tex> вместе с <tex>w' \rightarrow leadsto 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>.

Воспользуемся доказанной выше леммой. Так как Выберем в нашем графе минимальный по количеству рёбер цикл (он существует цикл, то существуют два реберно-простых пути между некоторыми вершинами: потому что количество рёбер в любом цикле — натуральное число <texref>v_0e_1v_1e_2v_2 [[Натуральные и целые числа#.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. e_nv_n</tex>, <tex>v'_0e'_1v'_1e'_2v'_2 D0.B8.D0.BC.D0.B5.D0.BD.D1.8C.D1.88.D0.B5.D0. e'_mv'_m</tex>, <tex>v_0 = v'_0</tex>, <tex>v_n = v'_m</tex>B3. Удалим из путей одинаковые префиксы и суффиксы, оставив из тех только последние и первые вершины, соответственноD0. Оставшиеся пути: <tex>v_ae_{a+1} BE_.D1.8D. e_bv_b</tex>, <tex>v'_ae'_{a+1} D0.BB.D0. 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>B5. Рассмотрим конкатенацию первого нового пути и развёрнутого второго нового путиD0. Она будет циклом, так как начальная и конечная вершины совпадают, изначально пути были рёберно-простыми, а в точке соединения, равно как и в точке замыкания цикла, условие различности двух идущих подряд рёбер выполняетсяBC. Мы получили цикл, определим его: <tex>v_0e_1v_1 D0.B5.D0. e_kv_k</tex>, <tex>v_0 = v_k</tex>BD. Дальше будем избавляться от повторных вхождений вершин в наш цикл, действуя по следующему алгоритму: * Алгоритм: 1D1. Для вершины <tex>v_i</tex> найдём момент её последнего вхождения в цикл - <tex>v_j</tex>82. 2D0. Удалим отрезок цикла от B0|Существование наименьшего элемента в любом подмножестве <tex>e_{i+1}\Bbb N</tex> до <tex>v_j]]</texref>). Предположим, включительночто он не простой. Получившаяся последовательность вершин Но тогда он содержит дважды одну и рёбер графа останется цикломту же вершину, и т. е. содержит в нём вершина <tex>v_i</tex> будет содержаться ровно один раз.Начнём процесс с вершины <tex>v_1</tex> и будем повторять его каждый раз для следующей вершины нового цикласебе цикл меньшего размера, что противоречит тому, пока не дойдём до последнейчто наш цикл минимальный. По построениюТаким образом, получившийся этот цикл будет содержать каждую из вершин графа не более одного раза, а значит, будет простым— простой.}}

[[Файл:Simple cycle.png|thumb|580px|center|Из цикла В графе минимальный цикл включает в себя три ребра — например, [2 - 5 - 6 - 4 - 2 - 6 - 7 - 3] получаем цикл [2 - 6 - 7 - 3]. Для вершины 2 находим последнее ее вхождение в цикл и удаляем отрезок цикла, выделенный (выделен <font color=#3771c8ff"red">синим.красным</font>). Согласно теореме, он является простым.<br>]]

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

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