Теорема о существовании простого цикла в случае существования цикла — различия между версиями
м (корректировка ссылок, выставление категорий) |
Shevchen (обсуждение | вклад) |
||
Строка 1: | Строка 1: | ||
+ | Назовём два пути одинаковыми, если последовательности вершин и рёбер графа, задающие их, совпадают полностью. Иначе будем считать пути различными. | ||
+ | |||
+ | {{Теорема | ||
+ | |statement= | ||
+ | Если между двумя [[Основные определения теории графов|вершинами неориентированного графа]] существуют два различных рёберно-простых [[Основные определения теории графов|пути]], то в этом графе существует простой цикл. | ||
+ | |proof= | ||
+ | Для доказательства этой теоремы введём определение. | ||
+ | |||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | '''Простой ( | + | '''Простой (вершинно-простой) цикл''' в графе – [[Основные определения теории графов|цикл]], в котором каждая из вершин графа встречается не более одного раза. |
}} | }} | ||
− | + | Очевидно, это условие не распространяется на первую и последнюю вершины цикла. | |
− | <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> и будем повторять его каждый раз для следующей вершины нового цикла, пока не дойдём до последней. По построению, получившийся цикл будет содержать каждую из вершин графа не более одного раза, а значит, будет простым. | ||
}} | }} | ||
− | + | == Замечания == | |
− | | | + | * Наличие двух различных рёберно-простых путей между какими-либо вершинами графа равносильно наличию [[Основные определения теории графов|цикла]] в этом графе. |
− | Если две вершины графа лежат на цикле, то они лежат на простом цикле. | + | * Так как вершинно-простой путь всегда является рёберно-простым, данная теорема справедлива и для вершинно-простых путей (усиление условия). |
− | + | * Так как вершинно-простой цикл всегда является рёберно-простым, данная теорема справедлива и для рёберно-простого цикла (ослабление результата). | |
− | + | * Утверждение | |
+ | Если две вершины графа лежат на цикле, то они лежат на простом цикле. | ||
+ | в общем случае неверно, так как эти вершины могут лежать в разных компонентах вершинной или рёберной двусвязности: все пути из одной вершины в другую будут содержать одну и ту же точку сочленения или один и тот же мост. | ||
+ | |||
+ | == См. также == | ||
+ | * [[Теорема о существовании простого пути в случае существования пути]] | ||
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Основные определения теории графов]] | [[Категория: Основные определения теории графов]] |
Версия 08:30, 11 октября 2010
Назовём два пути одинаковыми, если последовательности вершин и рёбер графа, задающие их, совпадают полностью. Иначе будем считать пути различными.
Теорема: | ||
Если между двумя вершинами неориентированного графа существуют два различных рёберно-простых пути, то в этом графе существует простой цикл. | ||
Доказательство: | ||
Для доказательства этой теоремы введём определение.
Очевидно, это условие не распространяется на первую и последнюю вершины цикла. Возьмём два существующих пути между нужными нам вершинами: , , , . Удалим из них одинаковые префиксы и суффиксы, оставив из них только последние и первые вершины, соответственно. Оставшиеся пути: , , , , , .Рассмотрим конкатенацию первого нового пути и развёрнутого второго нового пути. Она будет циклом, так как начальная и конечная вершины совпадают, изначально пути были рёберно-простыми, а в точке соединения, равно как и в точке замыкания цикла, условие различности двух идущих подряд рёбер выполняется. Мы получили цикл, определим его: , .
1. Для вершиныНачнём процесс с вершины найдём момент её последнего вхождения в цикл – . 2. Удалим отрезок цикла от до , включительно. Получившаяся последовательность вершин и рёбер графа останется циклом, и в нём вершина будет содержаться ровно один раз. и будем повторять его каждый раз для следующей вершины нового цикла, пока не дойдём до последней. По построению, получившийся цикл будет содержать каждую из вершин графа не более одного раза, а значит, будет простым. | ||
Замечания
- Наличие двух различных рёберно-простых путей между какими-либо вершинами графа равносильно наличию цикла в этом графе.
- Так как вершинно-простой путь всегда является рёберно-простым, данная теорема справедлива и для вершинно-простых путей (усиление условия).
- Так как вершинно-простой цикл всегда является рёберно-простым, данная теорема справедлива и для рёберно-простого цикла (ослабление результата).
- Утверждение
Если две вершины графа лежат на цикле, то они лежат на простом цикле.
в общем случае неверно, так как эти вершины могут лежать в разных компонентах вершинной или рёберной двусвязности: все пути из одной вершины в другую будут содержать одну и ту же точку сочленения или один и тот же мост.