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

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

Шлях позначають символом μ(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.

Посилання

Шаблон:Math-stub