Шля́х (в теорії графів) — ланцюг, всі ребра якого орієнтовані в напряму руху від початкової до кінцевої вершини ланцюга.
Шлях позначають символом μ(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) |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет