Ланцюг (теорія графів)
Матеріал з Вікіпедії — вільної енциклопедії.
Ланцю́г (в теорії графів) — це послідовність виду Q = x0u1x1u2x2...xl−1ul, де ребра 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.