Маршруты и связность в ориентированных графах
Маршруты и связность в ориентированных графах
Маршрутом длины k из v в w в орграфе G = (V, E) называется последовательность ребер вида: (v, w1), (w1, w2), (w2, w3), …, (wk-2, wk-1), (wk-1, w), то есть вторая вершина каждого ребра совпадает с первой вершиной следующего ребра.
Удобно представлять маршрут в орграфе последовательностью вершин: v, w1, w2, w3, …, wk-2, wk-1, w.
Если v = w, то маршрут называют замкнутым маршрутом, или циклом. Орграф без циклов называется ациклическим.
Пусть D – множество всех орграфов, а P – множество всех графов вообще. Можно определить отображение F: D ® P следующим образом:
Пусть G = (V, E) Î D. Тогда множество вершин F(G) совпадает с V, а множество ребер F(G) определяется применением следующих операций на Е:
· удаляются все петли из Е;
· (v, w) заменяются на [v, w] для всех (v, w) Î E.
Тогда F(G) является графом, связанным с орграфом G.
Рекомендуемые материалы
Для орграфов понятие связности является более содержательным, чем для графов, и имеет отношение к проблеме обхода. Определим три важных типа связности орграфа:
· G слабо связный, если граф F(G) - связный;
· G односторонне связный, если для каждой пары различных вершин v, w, принадлежащей множеству E, существует маршрут из v в w или обратно;
· G односторонне связный, если для каждой пары различных вершин v, w, принадлежащей множеству E, существует маршрут из v в w и обратно.
Очевидно, что если G – сильно связный орграф, то G - односторонне связный. Если G - односторонне связный орграф, то G слабо связный (рис. 4).
Рис. 4. Типы связности орграфа: а – слабо связный, б – односторонне связный, в – сильно связный
Если {Vi: 1 £ i £ p} – разбиение V и {Ei: 1 £ i £ p, а Ei = (Vi ´ Vi) ìüE} являются соответствующими множествами ребер, то подграфы Gi = (Vi, Ei), 1 £ i £ p называются сильно связными компонентами G.
Пусть G = (V, E) – ациклический орграф. Вершину v ÎV называют листом, если s + (v) = 0, то есть отсутствуют исходящие из нее дуги.
Если (v, w) Î E, то w является непосредственным потомком v, а v является непосредственным предком w. Если существует маршрут из вершины v в вершину w, то v является предком w, а w – потомком v (рис.5).
Эти понятия не имеют смысла для ориентированных графов, имеющих циклы, так как для таких графов вершины могут исходить сами из себя.
Ещё посмотрите лекцию "Доказать свойства свертки оригиналов" по этой теме.
Рис. 5. Предки и потомки в ациклическом орграфе:
вершины v2 , v4 ,v5 являются листьями, так как из них ребра не выходят; вершина v1 – является предком v5, v5 – прямой потомок v3.
Существует тесная связь между ациклическими орграфами и частично упорядоченными отношениями:
· Пусть отношение < является частичным отношением порядка на конечном множестве V. Тогда, если E = {(v, w): v < w}, то пара G = (V, E) является ациклическим ориентированным графом.
· Пусть G = (V, E) – ациклический орграф и отношение < определяется следующим образом: v < w, если v является предком w. Тогда отношение < является частичным отношением порядка на V.
Ориентированное дерево T = (V, E) – это ациклических орграф, в котором одна вершина vr Î V не имеет предков, а каждая другая вершина имеет только одного непосредственного предка. Вершина vr называется корнем дерева. Бинарное дерево – это ориентированное дерево, в котором каждая вершина имеет не более двух непосредственных потомков, то есть s + (v) £ 2, " v Î V. Говорят, что бинарное дерево называется полным, если каждая вершина, не являющаяся листом, имеет ровно двух непосредственных потомков.
