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

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

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

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

Див. також

[ред. | ред. код]

Джерела

[ред. | ред. код]