|
|
| Строка 15: |
Строка 15: |
| | Если две вершины графа лежат на цикле, то они лежат на простом цикле. | | Если две вершины графа лежат на цикле, то они лежат на простом цикле. |
| | |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_i</math> и <math>V_j</math>, <math>i < j</math>. Удалим из исходного цикла отрезки от <math>V_0</math> до <math>E_i</math>, включительно, и от <math>E_{j+1}</math> до <math>E_n</math>, включительно. Конечная последовательность также будет циклом и станет короче исходной. Значит, исходный цикл не был кратчайшим; предположение неверно, выбранный цикл – простой.
| |
| | }} | | }} |
Версия 06:51, 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].
| Определение: |
| Длина цикла – количество рёбер, входящих в последовательность, задающую этот цикл. |
| Теорема: |
Если две вершины графа лежат на цикле, то они лежат на простом цикле. |
