Шлях (теорія графів)

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

Шля́х (в теорії графів) — ланцюг, всі ребра якого орієнтовані в напряму руху від початкової до кінцевої вершини ланцюга.

Шлях позначають символом μ(x0, xl) = (u1, u2, …, ul), де дуга ui інциндентна вершинам xi-1 та xi. Шлях, в якому будь яка вершина не зустрічається двічі, називається елементарним.

Якщо xi та xj — деякі вершини графу, для яких існує шлях μ(xi, xj) то вершина xj досяжна із вершини xi, а вершина xi — зворотно досяжна із вершини xj. Множина всіх досяжних із xi вершин позначається символом D(xi), а зворотно досяжних — D−1(xi). Для будь якої множини A вершин визначається досяжна множина

D(A) = \cup_{x\in A} D(x).

Аналогічно визначається зворотно досяжна множина D−1(A).

Шлях, що містить всі дуги орієнтованого графу, називається ейлеровим.

Джерела інформації[ред.ред. код]

Див. також[ред.ред. код]