Ци́кл (в теорії графів) — ланцюг x0u1x1u2x2…xl−1ulx0, в якому перша та остання вершина збігаються.
Якщо відсутні інші збіжності вершин, то такий цикл називається простим. Цикл, який містить всі ребра графа називається ейлеровим, а простий цикл, який містить всі вершини графа — гамільтоновим. Якщо кожне ребро ui — дуга від xi−1 до xi (i = 1, 2, …, l; xl = x0), то цикл називається орієнтованим, або орциклом. Дозволяючи повторення ребер, отримаємо визначення циклічного (замкненого) шляху.
Пошук циклів Нехай дано орієнтований або неорієнтований граф без петель і кратних ребер. Потрібно перевірити, чи є він ациклічним, а якщо не є, то знайти будь-який цикл.
Вирішимо цю задачу за допомогою серії пошуків в глибину в графі. Тобто з кожної вершини, до якої ми ще жодного разу не приходили, запустимо пошук в глибину, який при вході в вершину буде позначати її відвіданою. І якщо пошук в глибину знайде ребро до вже відвіданої вершини, то це означає, що ми знайшли цикл.
Сам цикл можна відновити проходом по масиву предків.
Застосування Кожен алгоритм топологічного сортування виявляє цикли, бо їх присутність означає відсутність часткового порядку для вершин.
Знаходження циклів у дозволяє виявляти взаємні блокування.. Якщо Андрій чекає на Богдану, Богдана чекає на Василя, а Василь чекає на Андрія, то існує цикл і вони не дочекаються.
- це теж форма циклу на графі і їх наявність є небажаним індикатором.
Див. також Циклічний граф Циклічний граф (алгебра) Ланцюг (теорія графів) Шлях (теорія графів) Покриття вершин циклами Покриття ребер циклами Панциклічний граф Теорема Веблена Сильна теорема про досконалі графи
Література
Енциклопедія кібернетики, Зиков О. О., т. 2, с. 518.
Зноски