Изменения

Перейти к: навигация, поиск

Теорема о существовании простого цикла в случае существования цикла

1506 байт убрано, 21:16, 8 января 2015
Тикет 1-4: доказательство заменено на более простое, иллюстрация соответствующим образом изменена
{{Лемма
|statement=Наличие двух различных рёберно-простых путей между какими-либо двумя вершинами неориентированного графа <tex>G</tex> равносильно наличию цикла в этом графе.
|proof=
"<tex>\Rightarrow</tex>"
Если в неориентированном графе существует цикл, то в этом графе существует простой цикл.
|proof=
Воспользуемся доказанной выше леммой. Так как Выберем в нашем графе минимальный по количеству рёбер цикл (он существует цикл, то существуют два реберно-простых пути между некоторыми вершинами: потому что количество рёбер в любом цикле — натуральное число <texref>v_0e_1v_1e_2v_2 [[Натуральные и целые числа#.D0.A1. e_nv_n</tex>, <tex>v'_0e'_1v'_1e'_2v'_2 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. 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>.
Рассмотрим конкатенацию первого нового пути и развёрнутого второго нового пути. Она будет циклом, так как начальная и конечная вершины совпадают, изначально пути были рёберно-простыми, а в точке соединения, равно как и в точке замыкания цикла, условие различности двух идущих подряд рёбер выполняется. Мы получили цикл, определим его: <tex>v_0e_1v_1 ... e_kv_k</tex>, <tex>v_0 = v_k</tex>. Дальше будем избавляться от повторных вхождений вершин в наш цикл, действуя по следующему алгоритму: * Алгоритм: 1. Для вершины <tex>v_i</tex> найдём момент её последнего вхождения в цикл - <tex>v_j</tex>. 2. Удалим отрезок цикла от <tex>e_{i+1}</tex> до <tex>v_j</tex>, включительно. Получившаяся последовательность вершин и рёбер графа останется циклом, и в нём вершина <tex>v_i</tex> будет содержаться ровно один раз.Начнём процесс с вершины <tex>v_1</tex> и будем повторять его каждый раз для следующей вершины нового цикла, пока не дойдём до последней. По построению, получившийся цикл будет содержать каждую из вершин графа не более одного раза, а значит, будет простым.}} [[Файл:Simple cycle.png|thumb|580px|center|Из В графе минимальный цикл включает в себя четыре ребра — таких цикла два: [2 - 5 - 6 - 4 - 2 - 6 - 7 - 3] получаем цикл (выделен <font color="red">красным</font>) и [2 - 5 - 6 - 7 - 34]. Для вершины 2 находим последнее ее вхождение в цикл и удаляем отрезок цикла, выделенный (выделен <font color=#3771c8ff>синим.</font>). Согласно теореме, оба они просты.<br>]]
== Замечания ==
в общем случае неверно, так как эти вершины могут лежать в разных компонентах вершинной или рёберной двусвязности: все пути из одной вершины в другую будут содержать одну и ту же точку сочленения или один и тот же мост.
 
== Примечания ==
<references/>
== См. также ==
Iloskutov
130
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/43661»

Навигация