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

Ланцю́г (в теорії графів; нім. Kreis, рос. цепь) — це послідовність виду 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 дозволити повторення ребер, то отримаємо маршрут.

Джерела інформаціїРедагувати

Див. такожРедагувати