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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Замечания)
Строка 1: Строка 1:
Назовём два пути одинаковыми, если последовательности вершин и рёбер графа, задающие их, совпадают полностью. Иначе будем считать пути различными.
+
{{Определение
 
+
|definition=
{{Теорема
+
Назовём два пути '''одинаковыми''', если последовательности вершин и рёбер графа, задающие их, совпадают полностью. Иначе будем считать пути '''различными'''.
|statement=
+
}}
Если между двумя [[Основные определения теории графов|вершинами неориентированного графа]] существуют два различных рёберно-простых [[Основные определения теории графов|пути]], то в этом графе существует простой цикл.
 
|proof=
 
Для доказательства этой теоремы введём определение.
 
  
 
{{Определение
 
{{Определение
Строка 13: Строка 10:
 
Очевидно, это условие не распространяется на первую и последнюю вершины цикла.
 
Очевидно, это условие не распространяется на первую и последнюю вершины цикла.
  
 
+
{{Теорема
 +
|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_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>.
  

Версия 04:00, 17 января 2011

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


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

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

Теорема:
Если между двумя вершинами неориентированного графа существуют два различных рёберно-простых пути, то в этом графе существует простой цикл.
Доказательство:
[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]

Замечания

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

Если две вершины графа лежат на цикле, то они лежат на простом цикле.

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

См. также