Изменения

{{ОпределениеЛемма|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> проходит вдоль чёрных стрелок]]

Если в неориентированном графе существует цикл, то в этом графе существует простой цикл.|proof=Выберем в графе минимальный по количеству рёбер цикл (он существует, потому что количество рёбер в любом цикле — натуральное число <ref>[[Натуральные и целые числа#.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.D0.B0|Существование наименьшего элемента в любом подмножестве <tex>\Bbb N</tex>]]</ref>). Предположим, что он не простой. Но тогда он содержит дважды одну и ту же вершину, т. е. содержит в себе цикл меньшего размера, что противоречит тому, что наш цикл минимальный. Таким образом, этот цикл — простой.}} [[Файл:Simple cycle.png|thumb|580px|center|В графе минимальный цикл включает в себя три ребра — например, [2 - 5 - 6] (выделен <font color="red">красным</font>). Согласно теореме, он является простым.<br>]] == Замечания ==* Так как вершинно-простой путь всегда является рёберно-простым, первая теорема справедлива и для вершинно-простых путей (усиление условия).* Так как вершинно-простой цикл всегда является рёберно-простым, первая теорема справедлива и для рёберно-простого цикла (ослабление результата).{{Утверждение|about=неверное|statement=''Если две вершины графа лежат на цикле, то они лежат на простом цикле.''