Изменения

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

Предположим, что в графе <tex>G</tex> существует два различных рёберно простых пути между вершинами <tex>u</tex> и <tex>v</tex>. Пусть это будут пути <tex>p = u e_1 v_1\ldots v_{{Определение|definitionn-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>V_0E_1V_1E_2V_2 ... E_nV_nG</tex>, существует цикл и пусть циклический путь <tex>v_0e_1v_1e_2v_2 ... e_mv_mc = v_0 e_1 v_1 \ldots e_n v_0</tex>, {{---}} его представитель. Найдём первую точку <tex>V_0 w = v_k = v_0v_l (l > k)</tex>, пересечения <tex>V_n = v_mc</tex>с самим собой. Удалим из путей одинаковые префиксы и суффиксы Такая точка существует, оставив из тех только последние и первые вершины, соответственнот.к. путь замкнутый. Оставшиеся пути: Рассмотрим циклический путь <tex>V_aE_v_k e_{ak+1} \ldots e_l v_l</tex>: он простой, т.к.. E_bV_bесли это неверно и существует вершина <tex>v_j = v_j' (k < j < j' < l)</tex>, то в <tex>v_ae_{a+1} ... e_cv_cc</tex> вершина <tex>v_j'</tex>повторяется раньше, чем <tex>v_l</tex>. Теперь элементарно взяв две вершины <tex>V_a = v_av_k</tex>, и <tex>V_b = v_cv_{k+1}</tex>легко заметить, что существует два различных рёберно непересекающихся пути между ними: <tex>E_v_k e_{ak+1} \neq e_v_{ak+1}</tex>, и <tex>E_b v_k e_l v_{l - 1} \neq e_cldots v_k</tex>. }}[[Файл:2_paths_and_a_cycle.png|600px|thumb|center|Иллюстрация к лемме: пути отмечены соответственно <font color="f00000">красным</font> и <font color="0000f0">синим</font> (их общий префикс отмечен пунктиром), а циклический путь <tex>c</tex> проходит вдоль чёрных стрелок]]

Рассмотрим конкатенацию первого нового пути и развёрнутого второго нового пути. Она будет циклом{{Теорема|statement=Если в неориентированном графе существует цикл, так как начальная и конечная вершины совпадают, изначально пути были рёберно-простыми, а то в точке соединения, равно как и этом графе существует простой цикл.|proof=Выберем в точке замыкания цикла, условие различности двух идущих подряд графе минимальный по количеству рёбер выполняется. Мы получили цикл(он существует, определим его: потому что количество рёбер в любом цикле — натуральное число <texref>V_0E_1V_1 [[Натуральные и целые числа#.D0.A1. E_kV_kD1.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>V_0 = V_k]]</texref>). Предположим, что он не простой. Но тогда он содержит дважды одну и ту же вершину, т. е. содержит в себе цикл меньшего размера, что противоречит тому, что наш цикл минимальный. Таким образом, этот цикл — простой.}}

* Алгоритм[[Файл: 1Simple cycle. Для вершины <tex>V_i</tex> найдём момент её последнего вхождения png|thumb|580px|center|В графе минимальный цикл включает в цикл – <tex>V_j</tex>. себя три ребра — например, [2. Удалим отрезок цикла от - 5 - 6] (выделен <texfont color="red">E_{i+1}красным</tex> до <texfont>V_j</tex>, включительно). Получившаяся последовательность вершин и рёбер графа останется цикломСогласно теореме, и в нём вершина <tex>V_i</tex> будет содержаться ровно один разон является простым.Начнём процесс с вершины <texbr>V_1</tex> и будем повторять его каждый раз для следующей вершины нового цикла, пока не дойдём до последней. По построению, получившийся цикл будет содержать каждую из вершин графа не более одного раза, а значит, будет простым.}}]]

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