|
|
| (не показаны 2 промежуточные версии 2 участников) |
| Строка 1: |
Строка 1: |
| − | {{Лемма
| |
| − | |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=
| |
| − | Выберем в графе минимальный по количеству рёбер цикл (он существует, потому что количество рёбер — натуральное число <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 - 4 - 2 - 6 - 7 - 3] получаем цикл [2 - 6 - 7 - 3]. Для вершины 2 находим последнее ее вхождение в цикл и удаляем отрезок цикла, выделенный <font color=#3771c8ff>синим.</font><br>]]
| |
| − |
| |
| − | == Замечания ==
| |
| − | * Так как вершинно-простой путь всегда является рёберно-простым, первая теорема справедлива и для вершинно-простых путей (усиление условия).
| |
| − | * Так как вершинно-простой цикл всегда является рёберно-простым, первая теорема справедлива и для рёберно-простого цикла (ослабление результата).
| |
| − | * Утверждение
| |
| − | ''Если две вершины графа лежат на цикле, то они лежат на простом цикле.''
| |
| − |
| |
| − | в общем случае неверно, так как эти вершины могут лежать в разных компонентах вершинной или рёберной двусвязности: все пути из одной вершины в другую будут содержать одну и ту же точку сочленения или один и тот же мост.
| |
| − |
| |
| − | == Примечания ==
| |
| − | <references/>
| |
| − |
| |
| − | == См. также ==
| |
| − | * [[Основные определения теории графов]]
| |
| − | * [[Теорема о существовании простого пути в случае существования пути]]
| |
| − | * [[Отношение реберной двусвязности]]
| |
| − | * [[Отношение вершинной двусвязности]]
| |
| − |
| |
| − |
| |
| − | [[Категория: Алгоритмы и структуры данных]]
| |
| − | [[Категория: Основные определения теории графов]]
| |
