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

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

Шлях позначають символом μ(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 вершин визначається досяжна множина

${\displaystyle D(A)=\cup _{x\in A}D(x)}$.

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

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