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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (корректировка ссылок, выставление категорий)
Строка 1: Строка 1:
 +
Назовём два пути одинаковыми, если последовательности вершин и рёбер графа, задающие их, совпадают полностью. Иначе будем считать пути различными.
 +
 +
{{Теорема
 +
|statement=
 +
Если между двумя [[Основные определения теории графов|вершинами неориентированного графа]] существуют два различных рёберно-простых [[Основные определения теории графов|пути]], то в этом графе существует простой цикл.
 +
|proof=
 +
Для доказательства этой теоремы введём определение.
 +
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
'''Простой (рёберно-простой) цикл''' в графе – [[Основные_определения_теории_графов#Цикл|цикл]], в котором каждое из рёбер графа встречается не более одного раза.
+
'''Простой (вершинно-простой) цикл''' в графе – [[Основные определения теории графов|цикл]], в котором каждая из вершин графа встречается не более одного раза.
 
}}
 
}}
−
Для удобства будем считать, что цикл задаётся <math>n</math> вершинами и <math>n</math> рёбрами:
+
Очевидно, это условие не распространяется на первую и последнюю вершины цикла.
−
<math>V_0E_1V_1E_2 ... V_{n-1}E_n</math>, – причём ребро <math>E_i</math> соединяет вершины <math>V_{i-1}</math> и <math>V_{i % n}</math>.
+
 
 +
Возьмём два существующих пути между нужными нам вершинами: <math>V_0E_1V_1E_2V_2 ... E_nV_n</math>, <math>v_0e_1v_1e_2v_2 ... e_mv_m</math>, <math>V_0 = v_0</math>, <math>V_n = v_m</math>. Удалим из них одинаковые префиксы и суффиксы, оставив из них только последние и первые вершины, соответственно. Оставшиеся пути: <math>V_aE_{a+1} ... E_bV_b</math>, <math>v_ae_{a+1} ... e_cv_c</math>, <math>V_a = v_a</math>, <math>V_b = v_c</math>, <math>E_{a+1} \neq e_{a+1}</math>, <math>E_b \neq e_c</math>.
 +
 
 +
Рассмотрим конкатенацию первого нового пути и развёрнутого второго нового пути. Она будет циклом, так как начальная и конечная вершины совпадают, изначально пути были рёберно-простыми, а в точке соединения, равно как и в точке замыкания цикла, условие различности двух идущих подряд рёбер выполняется. Мы получили цикл, определим его: <math>V_0E_1V_1 ... E_kV_k</math>, <math>V_0 = V_k</math>.
  
−
{{Определение
+
* Алгоритм:
−
|definition=
+
1. Для вершины <math>V_i</math> найдём момент её последнего вхождения в цикл – <math>V_j</math>.
−
'''Длина цикла''' – количество рёбер, входящих в последовательность, задающую этот цикл.
+
2. Удалим отрезок цикла от <math>E_{i+1}</math> до <math>V_j</math>, включительно.
 +
Получившаяся последовательность вершин и рёбер графа останется циклом, и в нём вершина <math>V_i</math> будет содержаться ровно один раз.
 +
Начнём процесс с вершины <math>V_1</math> и будем повторять его каждый раз для следующей вершины нового цикла, пока не дойдём до последней. По построению, получившийся цикл будет содержать каждую из вершин графа не более одного раза, а значит, будет простым.
 
}}
 
}}
  
−
{{Теорема
+
== Замечания ==
−
|statement=
+
* Наличие двух различных рёберно-простых путей между какими-либо вершинами графа равносильно наличию [[Основные определения теории графов|цикла]] в этом графе.
−
Если две вершины графа лежат на цикле, то они лежат на простом цикле.
+
* Так как вершинно-простой путь всегда является рёберно-простым, данная теорема справедлива и для вершинно-простых путей (усиление условия).
−
|proof=
+
* Так как вершинно-простой цикл всегда является рёберно-простым, данная теорема справедлива и для рёберно-простого цикла (ослабление результата).
−
}}
+
* Утверждение
 +
Если две вершины графа лежат на цикле, то они лежат на простом цикле.
 +
в общем случае неверно, так как эти вершины могут лежать в разных компонентах вершинной или рёберной двусвязности: все пути из одной вершины в другую будут содержать одну и ту же точку сочленения или один и тот же мост.
 +
 
 +
== См. также ==
 +
* [[Теорема о существовании простого пути в случае существования пути]]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Основные определения теории графов]]
 
[[Категория: Основные определения теории графов]]

Версия 08:30, 11 октября 2010

Назовём два пути одинаковыми, если последовательности вершин и рёбер графа, задающие их, совпадают полностью. Иначе будем считать пути различными.

Теорема:
Если между двумя вершинами неориентированного графа существуют два различных рёберно-простых пути, то в этом графе существует простой цикл.
Доказательство:
[math]\triangleright[/math]

Для доказательства этой теоремы введём определение.


Определение:
Простой (вершинно-простой) цикл в графе – цикл, в котором каждая из вершин графа встречается не более одного раза.

Очевидно, это условие не распространяется на первую и последнюю вершины цикла.

Возьмём два существующих пути между нужными нам вершинами: [math]V_0E_1V_1E_2V_2 ... E_nV_n[/math], [math]v_0e_1v_1e_2v_2 ... e_mv_m[/math], [math]V_0 = v_0[/math], [math]V_n = v_m[/math]. Удалим из них одинаковые префиксы и суффиксы, оставив из них только последние и первые вершины, соответственно. Оставшиеся пути: [math]V_aE_{a+1} ... E_bV_b[/math], [math]v_ae_{a+1} ... e_cv_c[/math], [math]V_a = v_a[/math], [math]V_b = v_c[/math], [math]E_{a+1} \neq e_{a+1}[/math], [math]E_b \neq e_c[/math].

Рассмотрим конкатенацию первого нового пути и развёрнутого второго нового пути. Она будет циклом, так как начальная и конечная вершины совпадают, изначально пути были рёберно-простыми, а в точке соединения, равно как и в точке замыкания цикла, условие различности двух идущих подряд рёбер выполняется. Мы получили цикл, определим его: [math]V_0E_1V_1 ... E_kV_k[/math], [math]V_0 = V_k[/math].

  • Алгоритм:
1. Для вершины [math]V_i[/math] найдём момент её последнего вхождения в цикл – [math]V_j[/math].
2. Удалим отрезок цикла от [math]E_{i+1}[/math] до [math]V_j[/math], включительно.
Получившаяся последовательность вершин и рёбер графа останется циклом, и в нём вершина [math]V_i[/math] будет содержаться ровно один раз.
Начнём процесс с вершины [math]V_1[/math] и будем повторять его каждый раз для следующей вершины нового цикла, пока не дойдём до последней. По построению, получившийся цикл будет содержать каждую из вершин графа не более одного раза, а значит, будет простым.
[math]\triangleleft[/math]

Замечания

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

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

См. также

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Теорема_о_существовании_простого_цикла_в_случае_существования_цикла&oldid=3643»