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

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 +
{{В разработке}}
 +
 
{{Лемма
 
{{Лемма
|statement=Наличие двух различных рёберно простых путей между какими-либо двумя вершинами неориентированного [[Основные определения теории графов|графа]] <tex>G</tex> равносильно наличию цикла в этом графе.
+
|statement=Наличие двух различных рёберно-простых путей между какими-либо двумя вершинами графа <tex>G</tex> равносильно наличию цикла в этом графе.
 
|proof=
 
|proof=
<tex>\Rightarrow</tex>
+
"<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>.
+
Предположим, что в графе <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>\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>.
+
Предположим, что в графе <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>.
 
  }}
 
  }}
[[Файл:2_paths_and_a_cycle.png|600px|thumb|center|Иллюстрация к лемме: пути отмечены соответственно <font color="f00000">красным</font> и <font color="0000f0">синим</font> (их общий префикс отмечен пунктиром), а циклический путь <tex>c</tex> проходит вдоль чёрных стрелок]]
+
 
  
 
{{Теорема
 
{{Теорема
Строка 16: Строка 18:
 
Если в неориентированном графе существует цикл, то в этом графе существует простой цикл.
 
Если в неориентированном графе существует цикл, то в этом графе существует простой цикл.
 
|proof=
 
|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>). Предположим, что он не простой. Но тогда он содержит дважды одну и ту же вершину, т. е. содержит в себе цикл меньшего размера, что противоречит тому, что наш цикл минимальный. Таким образом, этот цикл — простой.}}
+
Воспользуемся доказанной выше леммой. Так как в нашем графе существует цикл, то существуют два реберно-простых пути между некоторыми вершинами: <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>. Дальше будем избавляться от повторных вхождений вершин в наш цикл, действуя по следующему алгоритму:
  
[[Файл:Simple cycle.png|thumb|580px|center|В графе минимальный цикл включает в себя три ребра — например, [2 - 5 - 6] (выделен <font color="red">красным</font>). Согласно теореме, он является простым.<br>]]
+
* Алгоритм:
 +
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> и будем повторять его каждый раз для следующей вершины нового цикла, пока не дойдём до последней. По построению, получившийся цикл будет содержать каждую из вершин графа не более одного раза, а значит, будет простым.
 +
}}
 +
 
 +
[[Файл: Prostoy cikl.png|thumb|600px|center|Для вершины 2 находим последнее ее вхождение в цикл и удаляем отрезок цикла, выделенный <font color=#22B14C>зеленым.</font><br>[(2, 5) - 5 - (5, 6) - 6 - (6, 4) - 4 - (4, 2) - 2]]]
  
 
== Замечания ==
 
== Замечания ==
 
* Так как вершинно-простой путь всегда является рёберно-простым, первая теорема справедлива и для вершинно-простых путей (усиление условия).
 
* Так как вершинно-простой путь всегда является рёберно-простым, первая теорема справедлива и для вершинно-простых путей (усиление условия).
 
* Так как вершинно-простой цикл всегда является рёберно-простым, первая теорема справедлива и для рёберно-простого цикла (ослабление результата).
 
* Так как вершинно-простой цикл всегда является рёберно-простым, первая теорема справедлива и для рёберно-простого цикла (ослабление результата).
{{Утверждение
+
* Утверждение
|about=неверное
+
''Если две вершины графа лежат на цикле, то они лежат на простом цикле.''
|statement=''Если две вершины графа лежат на цикле, то они лежат на простом цикле.''
 
|proof=
 
В общем случае неверно, так как эти вершины могут лежать в разных компонентах вершинной или рёберной двусвязности: все пути из одной вершины в другую будут содержать одну и ту же [[Точка сочленения, эквивалентные определения|точку сочленения]] или один и тот же [[Мост, эквивалентные определения|мост]].
 
}}
 
  
== Примечания ==
+
в общем случае неверно, так как эти вершины могут лежать в разных компонентах вершинной или рёберной двусвязности: все пути из одной вершины в другую будут содержать одну и ту же точку сочленения или один и тот же мост.
<references/>
 
  
 
== См. также ==
 
== См. также ==
 +
* [[Основные определения теории графов]]
 
* [[Теорема о существовании простого пути в случае существования пути]]
 
* [[Теорема о существовании простого пути в случае существования пути]]
* [[Отношение рёберной двусвязности]]
+
* [[Отношение реберной двусвязности]]
 
* [[Отношение вершинной двусвязности]]
 
* [[Отношение вершинной двусвязности]]
  

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)