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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (корректировка ссылок, выставление категорий)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Простой (рёберно-простой) цикл''' в графе – [[цикл]], в котором каждое из рёбер графа встречается не более одного раза.
+
'''Простой (рёберно-простой) цикл''' в графе – [[Основные_определения_теории_графов#Цикл|цикл]], в котором каждое из рёбер графа встречается не более одного раза.
 
}}
 
}}
 
Для удобства будем считать, что цикл задаётся <math>n</math> вершинами и <math>n</math> рёбрами:
 
Для удобства будем считать, что цикл задаётся <math>n</math> вершинами и <math>n</math> рёбрами:
Строка 16: Строка 16:
 
|proof=
 
|proof=
 
}}
 
}}
 +
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Основные определения теории графов]]

Версия 07:45, 11 октября 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].


Определение:
Длина цикла – количество рёбер, входящих в последовательность, задающую этот цикл.


Теорема:
Если две вершины графа лежат на цикле, то они лежат на простом цикле.