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

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

Шлях позначають символом μ(x₀, x_l) = (u₁, u₂, …, u_l), де дуга u_i інциндентна вершинам x_i-1 та x_i. Шлях, в якому будь яка вершина не зустрічається двічі, називається елементарним.

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

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

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

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

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

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

Див. також

• Ланцюг (теорія графів)
• Цикл (теорія графів)
• Граф (математика)
• Алгоритм Дійкстра знаходження найкоротшого шляху у графі.
• Алгоритм перевірки наявності шляху між вершинами