Цикл (теорія графів)

У Вікіпедії є статті про інші значення цього терміна: Цикл.

Ци́кл (в теорії графів) — ланцюг x₀u₁x₁u₂x₂…x_l−1u_lx₀, в якому перша та остання вершина збігаються.

Якщо відсутні інші збіжності вершин, то такий цикл називається простим. Цикл, який містить всі ребра графа називається ейлеровим, а простий цикл, який містить всі вершини графа — гамільтоновим. Якщо кожне ребро u_i — дуга від x_i−1 до x_i (i = 1, 2, …, l; x_l = x₀), то цикл називається орієнтованим, або орциклом. Дозволяючи повторення ребер, отримаємо визначення циклічного (замкненого) шляху.

Пошук циклів

Нехай дано орієнтований або неорієнтований граф без петель і кратних ребер. Потрібно перевірити, чи є він ациклічним, а якщо не є, то знайти будь-який цикл.

Вирішимо цю задачу за допомогою серії пошуків в глибину в графі. Тобто з кожної вершини, до якої ми ще жодного разу не приходили, запустимо пошук в глибину, який при вході в вершину буде позначати її відвіданою. І якщо пошук в глибину знайде ребро до вже відвіданої вершини, то це означає, що ми знайшли цикл.

Сам цикл можна відновити проходом по масиву предків.

Застосування

Кожен алгоритм топологічного сортування виявляє цикли, бо їх присутність означає відсутність часткового порядку для вершин.

Знаходження циклів у графі очікування дозволяє виявляти взаємні блокування.. Якщо Андрій чекає на Богдану, Богдана чекає на Василя, а Василь чекає на Андрія, то існує цикл і вони не дочекаються.

Циклічні залежності - це теж форма циклу на графі і їх наявність є небажаним індикатором.

Див. також

• Циклічний граф
• Циклічний граф (алгебра)
• Ланцюг (теорія графів)
• Шлях (теорія графів)
• Покриття вершин циклами
• Покриття ребер циклами
• Панциклічний граф
• Теорема Веблена
• Сильна теорема про досконалі графи

Література

• Sedgewick, Robert (1983). Algorithms. Reading, Mass: Addison-Wesley. ISBN 0-201-06672-6.
• Skiena, Steven S. (2008). The algorithm design manual (вид. 2nd). London: Springer. ISBN 978-1-84800-069-8.
• Енциклопедія кібернетики, Зиков О. О., т. 2, с. 518.
• Silberschatz, Abraham; Peter Galvin; Greg Gagne (2003). Operating System Concepts. John Wiley & Sons, INC. ISBN 0-471-25060-0.
• Джозеф Ротман. An Introduction to the Theory of Groups. — 4th. — Springer (Graduate Texts in Mathematics), 1994. — 532 с. — ISBN 978-0387942858.(англ.)