6.3.2. ‑ Орієнтований граф
Визначення 6.27. Послідовність ребер, у якому кінець кожного попереднього ребра збігається з початком наступного , називається шляхом або орієнтованим маршрутом. У шляху те саме ребро може зустрічатися кілька разів.
Визначення 6.28. Початком шляху є вершина ребра , а кінцем шляху є вершина ребра .
Визначення 6.29. Довжиною орієнтованого маршруту називається кількість орієнтованих ребер, що входять у цей шлях.
Приклад 6.17.
Для графа, зображеного на рис. 6.21,
приведемо приклади орієнтованих
маршрутів з вершини
до вершини
:
;
;
‑ довжини 3;
‑ довжини 5.
Рис. 6.21.
Визначення 6.30. Орієнтованим ланцюгом називається шлях, кожне ребро якого зустрічається не більше одного разу, і простим ланцюгом, якщо будь-яка вершина орграфа інцидентна не більш ніж двом його ребрам.
Визначення 6.31. Контуром називається шлях, початок і кінець якого збігаються. Контур називається циклом, якщо він є ланцюгом, і простим циклом – якщо це простий ланцюг.
Приклад
6.18. Для
графа, зображеного на рис. 6.22,а,
приклади: орієнтованого ланцюга ‑
;
контуру ‑
;
циклу ‑
.
Для графа, зображеного на рис. 6.22,б,
приклади: простого орієнтованого ланцюга
‑
;
простого циклу ‑
.
При цьому зауважимо, що при записі циклу
як для орієнтованого, так і для
неорієнтованого графа, як початком, так
і кінцем може бути обрана будь-яка
вершина. Наприклад:
;
і т.п.
(а) (б)
Рис. 6.22.
Визначення
6.32. Для
кожного орієнтованого графа
може бути побудований неорієнтований
граф
,
такий, що всі вершини цих графів
збігаються, а кожне ребро
(крім петель), стане неорієнтованим
ребром графа
.
У такому випадку граф
називається співвіднесеним
графом
орієнтованого графа
.
Приклад 6.19. Для графа , зображеного на рис. 6.23,а, співвіднесений граф буде мати вигляд (рис. 6.23,б):
(а) (б)
Рис. 6.23.
Визначення
6.33.
Вершина
називається досяжною
з вершини
,
якщо існує шлях з початком у
і кінцем у
.
Визначення 6.34. Орієнтований граф називається зв'язним, якщо його співвіднесений граф є зв'язним. Орієнтований граф називається сильно зв'язним, якщо для будь-якої пари вершин існує орієнтований шлях з , у .
Так, наприклад, граф, зображений на рис. 6.23,а, є зв'язним, але не є сильно зв'язним.
Вправи:
1. Для неорієнтованих графів, зображених на рис. 6.24(а,б), привести приклади: маршруту; ланцюга; простого ланцюга; циклічного маршруту; циклу; простого циклу.
(а) (б)
Рис. 6.24.
2. Для орієнтованих графів, зображених на рис. 6.25(а,б), привести приклади: шляху; орієнтованого ланцюга; простого ланцюга; контуру; циклу; простого циклу.
(а) (б)
Рис. 6.25.
3. Визначити число компонент зв’язності у графах , зображених на рис. 6.26(а,б,в,г).
(а) (б)
(в) (г)
Рис. 6.26.
4. Знайти на графах , зображених на рис. 6.27 (а-г), всі точки зчленування і мости:
(а) (б)
(в) (г)
Рис. 6.27.