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

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

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

Див. також

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

Джерела

• Енциклопедія кібернетики, Зиков О. О., т. 2, с. 518.
• Джозеф Ротман. An Introduction to the Theory of Groups. — 4th. — Springer (Graduate Texts in Mathematics), 1994. — 532 с. — ISBN 978-0387942858.(англ.)