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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Простой (вершинно-простой) цикл''' в графе – [[цикл]], в котором каждая из вершин графа встречается не более одного раза.
+
'''Простой (рёберно-простой) цикл''' в графе – [[цикл]], в котором каждое из рёбер графа встречается не более одного раза.
 
}}
 
}}
 
Для удобства будем считать, что цикл задаётся <math>n</math> вершинами и <math>n</math> рёбрами:
 
Для удобства будем считать, что цикл задаётся <math>n</math> вершинами и <math>n</math> рёбрами:
Строка 8: Строка 8:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Длина цикла''' – количество вершин, входящих в последовательность, задающую этот цикл.
+
'''Длина цикла''' – количество рёбер, входящих в последовательность, задающую этот цикл.
 
}}
 
}}
  
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Если в графе существует цикл, то в этом графе существует простой цикл.
+
Если две вершины графа лежат на цикле, то они лежат на простом цикле.
 
|proof=
 
|proof=
 
Возьмём любой из существующих циклов <math>V_0E_1V_1E_2V_2 ... V_{n-1}E_n</math>. Для вершины <math>V_i</math> найдём момент её следующего вхождения в цикл – <math>V_j</math> – и, если такой нашёлся, удалим отрезки цикла от <math>V_0</math> до <math>E_i</math>, включительно, и от <math>E_{j+1}</math> до <math>E_n</math>, включительно. Получившаяся последовательность вершин и рёбер графа останется циклом, и в нём вершина <math>V_i</math> будет содержаться ровно один раз. Начнём процесс с вершины <math>V_0</math> и будем повторять его каждый раз  для следующей вершины нового цикла, пока не дойдём до последней. По построению, получившийся цикл будет содержать каждую из вершин графа не более одного раза, а значит, будет простым.
 
Возьмём любой из существующих циклов <math>V_0E_1V_1E_2V_2 ... V_{n-1}E_n</math>. Для вершины <math>V_i</math> найдём момент её следующего вхождения в цикл – <math>V_j</math> – и, если такой нашёлся, удалим отрезки цикла от <math>V_0</math> до <math>E_i</math>, включительно, и от <math>E_{j+1}</math> до <math>E_n</math>, включительно. Получившаяся последовательность вершин и рёбер графа останется циклом, и в нём вершина <math>V_i</math> будет содержаться ровно один раз. Начнём процесс с вершины <math>V_0</math> и будем повторять его каждый раз  для следующей вершины нового цикла, пока не дойдём до последней. По построению, получившийся цикл будет содержать каждую из вершин графа не более одного раза, а значит, будет простым.

Версия 06:35, 9 октября 2010

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

Для удобства будем считать, что цикл задаётся [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]\triangleright[/math]

Возьмём любой из существующих циклов [math]V_0E_1V_1E_2V_2 ... V_{n-1}E_n[/math]. Для вершины [math]V_i[/math] найдём момент её следующего вхождения в цикл – [math]V_j[/math] – и, если такой нашёлся, удалим отрезки цикла от [math]V_0[/math] до [math]E_i[/math], включительно, и от [math]E_{j+1}[/math] до [math]E_n[/math], включительно. Получившаяся последовательность вершин и рёбер графа останется циклом, и в нём вершина [math]V_i[/math] будет содержаться ровно один раз. Начнём процесс с вершины [math]V_0[/math] и будем повторять его каждый раз для следующей вершины нового цикла, пока не дойдём до последней. По построению, получившийся цикл будет содержать каждую из вершин графа не более одного раза, а значит, будет простым.


Альтернативное:

Выберем из всех циклов в графе цикл наименьшей длины. Пусть он не простой; тогда в нём содержатся две одинаковые вершины [math]V_i[/math] и [math]V_j[/math], [math]i \lt j[/math]. Удалим из исходного цикла отрезки от [math]V_0[/math] до [math]E_i[/math], включительно, и от [math]E_{j+1}[/math] до [math]E_n[/math], включительно. Конечная последовательность также будет циклом и станет короче исходной. Значит, исходный цикл не был кратчайшим; предположение неверно, выбранный цикл – простой.
[math]\triangleleft[/math]