Изменения

Перейти к: навигация, поиск
м
Нет описания правки
{{ОпределениеЛемма|definitionstatement=Наличие двух различных рёберно простых путей между какими-либо двумя вершинами неориентированного [[Основные определения теории графов|графа]] <tex>G</tex> равносильно наличию цикла в этом графе.Назовём |proof=<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'_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>.}}
{{Определение|definition='''Простой (вершинно-простой) цикл''' в графе – [[Основные определения теории графов|цикл]], в котором каждая из вершин графа встречается не более одного раза.}}Очевидно, это условие не распространяется на первую и последнюю вершины цикла.<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>: prime_c1он простой, т.png|thumb|300px|left|Неориентированный графк. если это неверно и существует вершина <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}<br/tex>и <font color=#ED1C24tex>Краснымv_k e_l v_{l - 1} \ldots v_k</fonttex> выделен цикл]]. }}[[Файл: prime_c22_paths_and_a_cycle.png|600px|thumb|300px|center|Неориентированный графИллюстрация к лемме: пути отмечены соответственно <brfont color="f00000">красным</font> и <font color=#22B14C"0000f0">Зеленымсиним</font> выделен простой цикл(их общий префикс отмечен пунктиром), а циклический путь <tex>c</tex> проходит вдоль чёрных стрелок]]
{{Теорема
|statement=
Если между двумя [[Основные определения теории графов|вершинами неориентированного графа]] существуют два различных рёберно-простых [[Основные определения теории графов|пути]]в неориентированном графе существует цикл, то в этом графе существует простой цикл.
|proof=
Возьмём два существующих пути между нужными нам вершинами: Выберем в графе минимальный по количеству рёбер цикл (он существует, потому что количество рёбер в любом цикле — натуральное число <texref>V_0E_1V_1E_2V_2 [[Натуральные и целые числа#.D0.A1.D1.83.D1.89.D0.B5.D1. E_nV_n</tex>, <tex>v_0e_1v_1e_2v_2 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. e_mv_mB0|Существование наименьшего элемента в любом подмножестве </tex>, <tex>V_0 = v_0\Bbb N</tex>, <tex>V_n = v_m]]</texref>). Удалим из путей одинаковые префиксы и суффиксыПредположим, оставив из тех только последние что он не простой. Но тогда он содержит дважды одну и первые вершиныту же вершину, соответственнот. Оставшиеся пути: <tex>V_aE_{a+1} е.содержит в себе цикл меньшего размера, что противоречит тому, что наш цикл минимальный.. E_bV_b</tex>Таким образом, <tex>v_ae_{a+1} ..этот цикл — простой. 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>.
Рассмотрим конкатенацию первого нового пути и развёрнутого второго нового пути[[Файл:Simple cycle. Она будет цикломpng|thumb|580px|center|В графе минимальный цикл включает в себя три ребра — например, так как начальная и конечная вершины совпадают, изначально пути были рёберно[2 - 5 -простыми, а в точке соединения, равно как и в точке замыкания цикла, условие различности двух идущих подряд рёбер выполняется. Мы получили цикл, определим его: 6] (выделен <texfont color="red">V_0E_1V_1 ... E_kV_kкрасным</texfont>). Согласно теореме, он является простым.<tex>V_0 = V_k</texbr>.]]
== Замечания ==* Алгоритм:Так как вершинно-простой путь всегда является рёберно-простым, первая теорема справедлива и для вершинно-простых путей (усиление условия). 1. Для вершины <tex>V_i</tex> найдём момент её последнего вхождения в * Так как вершинно-простой цикл – <tex>V_j</tex>всегда является рёберно-простым, первая теорема справедлива и для рёберно-простого цикла (ослабление результата). 2. Удалим отрезок цикла от <tex>E_{i+1}</tex> до <tex>V_j</tex>, включительно.{Утверждение|about=неверное Получившаяся последовательность вершин и рёбер |statement=''Если две вершины графа останется цикломлежат на цикле, и в нём вершина <tex>V_i</tex> будет содержаться ровно один разто они лежат на простом цикле.''Начнём процесс с |proof=В общем случае неверно, так как эти вершины <tex>V_1</tex> и будем повторять его каждый раз для следующей могут лежать в разных компонентах вершинной или рёберной двусвязности: все пути из одной вершины нового цикла, пока не дойдём до последней. По построению, получившийся цикл будет в другую будут содержать каждую из вершин графа не более одного разаодну и ту же [[Точка сочленения, а значитэквивалентные определения|точку сочленения]] или один и тот же [[Мост, будет простымэквивалентные определения|мост]].
}}
== Замечания Примечания ==* Наличие двух различных рёберно-простых путей между какими-либо вершинами графа равносильно наличию цикла в этом графе.* Так как вершинно-простой путь всегда является рёберно-простым, данная теорема справедлива и для вершинно-простых путей (усиление условия).* Так как вершинно-простой цикл всегда является рёберно-простым, данная теорема справедлива и для рёберно-простого цикла (ослабление результата).* Утверждение''Если две вершины графа лежат на цикле, то они лежат на простом цикле.'' в общем случае неверно, так как эти вершины могут лежать в разных компонентах вершинной или рёберной двусвязности: все пути из одной вершины в другую будут содержать одну и ту же точку сочленения или один и тот же мост.<references/>
== См. также ==
* [[Основные определения теории графов]]
* [[Теорема о существовании простого пути в случае существования пути]]
* [[Отношение рёберной двусвязности]]
* [[Отношение вершинной двусвязности]]
 
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Основные определения теории графов]]

Навигация