Теорема о существовании простого цикла в случае существования цикла — различия между версиями
Shevchen (обсуждение | вклад) (Новая страница: «{{Определение |definition= '''Простой (вершинно-простой) цикл''' в графе – цикл, в котором каждая …») |
Shevchen (обсуждение | вклад) |
||
Строка 13: | Строка 13: | ||
{{Теорема | {{Теорема | ||
|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> и будем повторять его каждый раз для следующей вершины нового цикла, пока не дойдём до последней. По построению, получившийся цикл будет содержать каждую из вершин графа не более одного раза, а значит, будет простым. |
Версия 00:29, 2 октября 2010
Определение: |
Простой (вершинно-простой) цикл в графе – цикл, в котором каждая из вершин графа встречается не более одного раза. |
Для удобства будем считать, что цикл задаётся
вершинами и рёбрами: , – причём ребро соединяет вершины и .
Определение: |
Длина цикла – количество вершин, входящих в последовательность, задающую этот цикл. |
Теорема: |
Если в графе существует цикл, то в этом графе существует простой цикл. |
Доказательство: |
Возьмём любой из существующих циклов . Для вершины найдём момент её следующего вхождения в цикл – – и, если такой нашёлся, удалим отрезки цикла от до , включительно, и от до , включительно. Получившаяся последовательность вершин и рёбер графа останется циклом, и в нём вершина будет содержаться ровно один раз. Начнём процесс с вершины и будем повторять его каждый раз для следующей вершины нового цикла, пока не дойдём до последней. По построению, получившийся цикл будет содержать каждую из вершин графа не более одного раза, а значит, будет простым.
|