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