Ланцюг (теорія графів)

Ланцю́г (в теорії графів; нім. Kreis, рос. цепь) — це послідовність виду Q = x₀u₁x₁u₂x₂...x_lu_l, де ребра u₀, u₁, ..., u_l різні і ребро u_i з'єднує (в будь-якому напрямі) вершини x_i−1 та x_i (i = 1, 2, ..., l) графу L = (X, U, P). Вершина x₀ називається початковою, вершина x_l — кінцевою, а число l ≥ 0 — довжиною ланцюга.

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

Джерела інформації

• Енциклопедія кібернетики, Донец Г. А., Зиков О. О., т. 2, с. 518.

Див. також

• Цикл (теорія графів)
• Шлях (теорія графів)
• Граф (математика)