Шлях (теорія графів) — Вікіпедія
Шля́х (в теорії графів) — ланцюг, всі ребра якого орієнтовані в напряму руху від початкової до кінцевої вершини ланцюга.
Шлях позначають символом μ(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−1(A).
Шлях, що містить всі дуги орієнтованого графу, називається ейлеровим.
- Ланцюг (теорія графів)
- Цикл (теорія графів)
- Граф (математика)
- Алгоритм Дейкстри знаходження найкоротшого шляху у графі.
- Граціозна розмітка
- Лінійний ліс
- Задача про найширший шлях
- Енциклопедія кібернетики, Донец Г. А., т. 2, с. 256.
![]() | Це незавершена стаття з математики. Ви можете допомогти проєкту, виправивши або дописавши її. |
![]() | Ця стаття потребує додаткових посилань на джерела для поліпшення її перевірності. (лютий 2016) |