Изменения

{{ОпределениеЛемма|definitionstatement='''Простой (Наличие двух различных рёбернопростых путей между какими-простой) цикл''' в графе – либо двумя вершинами неориентированного [[циклОсновные определения теории графов|графа]], <tex>G</tex> равносильно наличию цикла в котором каждое из рёбер графа встречается не более одного разаэтом графе.}}|proof=<tex>\Rightarrow</tex> Для удобства будем считатьПредположим, что цикл задаётся в графе <mathtex>nG</mathtex> существует два различных рёберно простых пути между вершинами <tex>u</tex> и <mathtex>v</tex>. Пусть это будут пути <tex>p = u e_1 v_1\ldots v_{n-1} e_n v</mathtex> рёбрами:и <mathtex>V_0E_1V_1E_2 ... V_p' = u e'_1 v'_1\ldots v'_{n-1}E_ne'_n v</tex>. Пусть их наибольший общий префикс заканчивается в вершине <tex>w = v_k = v'_k</tex>. Заметим, что <tex>w \neq v</mathtex>, – причём ребро т.к. пути различны. Рассмотрим суффиксы путей <tex>p</tex> и <mathtex>E_ip'</mathtex> соединяет вершины : <mathtex>V_s = w e_{i-k+1}\ldots v</mathtex> и <mathtex>V_s' = w e'_{i % nk+1}\ldots v</tex> соответственно. Найдём первую совпадающую вершину <tex>w'</tex> в <tex>s</tex> и <tex>s'</tex>, не равную <tex>w</mathtex>.Осталось заметить, что замкнутый путь <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>G</tex> существует цикл и пусть циклический путь <tex>c = v_0 e_1 v_1 \ldots e_n v_0</tex> {{Определение|definition---}} его представитель. Найдём первую точку <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> проходит вдоль чёрных стрелок]]

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

Возьмём любой из существующих циклов Выберем в графе минимальный по количеству рёбер цикл (он существует, потому что количество рёбер в любом цикле — натуральное число <mathref>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.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. V_{n-1}E_n</math>D0. Для вершины <math>V_i</math> найдём момент её следующего вхождения B0|Существование наименьшего элемента в цикл – <math>V_j</math> – и, если такой нашёлся, удалим отрезки цикла от любом подмножестве <mathtex>V_0\Bbb N</math> до <mathtex>E_i]]</mathref>). Предположим, включительно, что он не простой. Но тогда он содержит дважды одну и от <math>E_{j+1}</math> до <math>E_n</math>ту же вершину, включительнот. е. Получившаяся последовательность вершин и рёбер графа останется цикломсодержит в себе цикл меньшего размера, и в нём вершина <math>V_i</math> будет содержаться ровно один раз. Начнём процесс с вершины <math>V_0</math> и будем повторять его каждый раз для следующей вершины нового циклачто противоречит тому, пока не дойдём до последнейчто наш цикл минимальный. По построениюТаким образом, получившийся этот цикл будет содержать каждую из вершин графа не более одного раза, а значит, будет простым— простой.}}

''Альтернативное:''== Замечания ==* Так как вершинно-простой путь всегда является рёберно-простым, первая теорема справедлива и для вершинно-простых путей (усиление условия).Выберем из всех циклов в графе * Так как вершинно-простой цикл наименьшей длинывсегда является рёберно-простым, первая теорема справедлива и для рёберно-простого цикла (ослабление результата). Пусть он не простой; тогда в нём содержатся {{Утверждение|about=неверное|statement=''Если две одинаковые вершины <math>V_i</math> и <math>V_j</math>графа лежат на цикле, <math>i < j</math>то они лежат на простом цикле. Удалим ''|proof=В общем случае неверно, так как эти вершины могут лежать в разных компонентах вершинной или рёберной двусвязности: все пути из исходного цикла отрезки от <math>V_0</math> до <math>E_i</math>, включительно, одной вершины в другую будут содержать одну и от <math>E_{j+1}</math> до <math>E_n</math>ту же [[Точка сочленения, включительно. Конечная последовательность также будет циклом эквивалентные определения|точку сочленения]] или один и станет короче исходной. Значит, исходный цикл не был кратчайшим; предположение невернотот же [[Мост, выбранный цикл – простойэквивалентные определения|мост]].