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