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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Ци́кл (в теорії графів) — ланцюг x0u1x1u2x2xl−1ulx0, в якому l > 1 та остання вершина збігається з початковою.

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

Джерела інформації[ред.ред. код]

Див. також[ред.ред. код]