Ланцю́г (в теорії графів; , ) — це послідовність виду Q = x0u1x1u2x2...xlul, де ребра u0, u1, ..., ul різні і ребро ui з'єднує (в будь-якому напрямі) вершини xi−1 та xi (i = 1, 2, ..., l) графу L = (X, U, P). Вершина x0 називається початковою, вершина xl — кінцевою, а число l ≥ 0 — довжиною ланцюга.
Ланцюг називається простим, якщо всі його вершини відмінні. Ланцюг, який містить всі ребра графу, називається ейлеровим, а простий ланцюг, який містить всі вершини графу, називається гамільтоновим. Якщо в Q кожне ребро ui — дуга, яка виходить із xi−1 в xi (i = 1, 2, ..., l), то ланцюг називається орієнтованим (дозволяючи і дуги і петлі, отримаємо шлях). Якщо в Q дозволити повторення ребер, то отримаємо маршрут.
Джерела інформації
Енциклопедія кібернетики, Донец Г. А., Зиков О. О., т. 2, с. 518.
Див. також
Цикл (теорія графів) Шлях (теорія графів) Граф (математика)