Фундаментальные циклы графа

2012-04-26T16:06:59Z

92.100.200.178:

== Определение ==
{{Определение
|definition =
Рассмотрим каркас <tex>T</tex> графа <tex>G</tex>. <tex>e_1,...,e_{s}</tex> — все ребра графа <tex>G</tex>, которые не входят в каркас <tex>T</tex>. При добавлении <math>e_{i}</math> образуется простой цикл <tex>C_{i}</tex>. Семейство циклов <tex>C_1 ... C_{s}</tex> называется '''фундаментальными циклами графа <tex>G</tex> относительно каркаса <tex>T</tex>'''
}}

[[Файл:Fundomential.png|380px|центр|thumb|Пример фундаментального цикла в графе.]]

== Свойства ==
{{Теорема
|statement =
Множество всех фундаментальных циклов относительно любого каркаса <tex>T</tex> графа <tex>G</tex> образует базис циклического пространства этого графа.
|proof =

Рассмотрим каркас <tex>T</tex> графа <tex>G</tex> и фундаментальные циклы <tex> C_1 ... C_s </tex> относительно каркаса <tex>T</tex>. В каждом цикле есть ребро <tex>e_i</tex>, которое принадлежит ровно одному из <tex> C_1 ... C_{s} </tex>. Поэтому сумма различных фундаментальных циклов относительно каркаса <tex>T</tex> не является пустым графом, из чего следует, что <tex> C_1 ... C_s </tex> линейно независимы.

Докажем, что любой цикл из циклического пространства графа <tex>G</tex> является суммой фундаментальных циклов. Пусть <tex>Z</tex> — цикл циклического пространства графа <tex>G</tex>, <tex> e_1 ... e_{k} </tex> ребра принадлежащие <tex>Z</tex> и не принадлежащие <tex>T</tex>. Рассмотрим граф <tex> F = Z \oplus C_1 \oplus ... \oplus C_{k} </tex>. Каждое из ребер <tex> e_{t} , t = 1,..,k </tex> встречается ровно в двух слагаемых — <tex>Z</tex> и <tex>C_{k}</tex>. Значит <tex>F</tex> содержит только ребра из <tex>T</tex>. Так как <tex> C_1 ... C_{k} </tex> простые циклы, то степени всех их вершин четны, степени вершин <tex>Z</tex> тоже четны по [[Циклическое пространство графа|лемме]], значит степени всех вершин <tex>F</tex> четны. Если <tex>F</tex> непустой граф, то в <tex>F</tex> есть цикл, значит цикл есть и в <tex>T</tex>. Значит <tex>F</tex> пустой граф, откуда следует что <tex>Z = C_1 \oplus ... \oplus C_{k} </tex>.
}}

== Литература ==
Харари Ф. Теория графов / пер. с англ. — изд. 4-е — М.: Книжный дом «ЛИБРОКОМ», 2009. — с.55. — ISBN 978-5-397-00622-4.

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Основные определения теории графов]]

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

2012-04-26T15:54:28Z

92.100.200.178:

{{В разработке}}

{{Лемма
|statement=Наличие двух различных рёберно-простых путей между какими-либо двумя вершинами графа <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'_l</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'_{l+1} \ldots v</tex> соответственно. Найдем первую совпадающую вершину <tex>w'</tex> в <tex>s</tex> и <tex>s'</tex>, не равную <tex>w</tex>. Осталось заметить, что замкнутый путь <tex>c</tex>, полученный объединением <tex>w \rightarrow w'</tex> части пути <tex>s</tex> вместе с <tex>w' \rightarrow w</tex> частью цепи <tex>s'</tex> является циклическим путем. Действительно, т. r. в путях <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> {{---}} его представитель. Найдем первую точку <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>.
}}

{{Теорема
|statement=
Если в неориентированном графе существует цикл, то в этом графе существует простой цикл.
|proof=
Воспользуемся доказанной выше леммой. Так как в нашем графе существует цикл, то существуют два реберно-простых пути между некоторыми вершинами: <tex>v_0e_1v_1e_2v_2 ... e_nv_n</tex>, <tex>v'_0e'_1v'_1e'_2v'_2 ... e'_mv'_m</tex>, <tex>v_0 = v'_0</tex>, <tex>v_n = v'_m</tex>. Удалим из путей одинаковые префиксы и суффиксы, оставив из тех только последние и первые вершины, соответственно. Оставшиеся пути: <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|500px|center|Из цикла [2 - 5 - 6 - 4 - 2 - 6 - 7 - 3] получаем цикл [2 - 6 - 7 - 3]. Для вершины 2 находим последнее ее вхождение в цикл и удаляем отрезок цикла, выделенный <font color=#22B14C>зеленым.</font><br>]]

== Замечания ==
* Так как вершинно-простой путь всегда является рёберно-простым, первая теорема справедлива и для вершинно-простых путей (усиление условия).
* Так как вершинно-простой цикл всегда является рёберно-простым, первая теорема справедлива и для рёберно-простого цикла (ослабление результата).
* Утверждение
''Если две вершины графа лежат на цикле, то они лежат на простом цикле.''

в общем случае неверно, так как эти вершины могут лежать в разных компонентах вершинной или рёберной двусвязности: все пути из одной вершины в другую будут содержать одну и ту же точку сочленения или один и тот же мост.

== См. также ==
* [[Основные определения теории графов]]
* [[Теорема о существовании простого пути в случае существования пути]]
* [[Отношение реберной двусвязности]]
* [[Отношение вершинной двусвязности]]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Основные определения теории графов]]

Викиконспекты - Вклад участника [ru]

Фундаментальные циклы графа

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