Лесом называется граф, в котором каждая связная компонента является деревом. Остовный лес для графа G=(V, Е) — это совокупность
вершин разъединенные деревьев Ті = (Vі, Еі) таких, что
V Vi и
i
Еі E для всех i. (Разъединенность вершин означает, что Vi ∩ Vj =
при i≠j).
Рисунок 5 иллюстрирует вышеупомянутые понятия для графа при р = 2.
Рис. 5.
Во многих приложениях теории графов требуется, чтобы ребра графа имели направление. Например, поток данных проходит через программу.
Определение. Ориентированный граф (орграф) G есть пара G = (V, Е), где V — конечное множество вершин, а Е — произвольное подмножество V × V.
Утверждение.
а) Ориентированный граф G = (V, E) определяет отношение на V.
б) Пусть V — конечное множество. Тогда отношение на V определяет ориентированный граф, у которого множество
вершин — У.
Доказательство.
а) Определим R(E) следующим образом: vR(E)w тогда и только тогда, когда (v, w) E. Очевидно, что R(E) — отношение.
б) Если R — отношение на V, то ориентированный граф G=(V, E), определяемый R, имеет множество ребер Е, где (v, w) E, тогда и только тогда, когда vRw.
Направление ребра обозначают порядком в V×V; например, если
(v, w) E, то говорят, что ребро выходит из v и входит в w. На диаграмме в этом случае для указания направления используют стрелки.
Пример 1. Пусть V — {v1, v2, v3}, a E1 = {(v1, v2), (v2, v3), (v3, v1)}. Тогда матрица смежности и изображение орграфа G1 =(V, E1) будут такими, как на рис. 6.
Рис. 6.
Аналогично на рис. 7 приведена матрица смежности и изображение графа G2= (V, E2), где
E2= {( v1, v1), (v1, v2), (v1, v3), (v2, v3), (v3 , v1)}.
Рис. 7.
Поскольку реберное отношение для орграфа не обязательно симметрично или нерефлексивно, то, вообще говоря, не обязательно, чтобы А = Ат или Аіі = 0. Ребра типа (v, v) называют петлей. Степень δ(v) вершины v V может быть записана в виде суммы δ(v) = δ-( v) + δ+( v), где δ- (v) — число ребер, входящих в v, а δ+(v) — число ребер, выходящих из v. Множества {w: (w, v) E} и
(w: (v, w) E} называют соответственно входящим узлом и выходящим узлом вершины v V. Понятия эквивалентности и пометки обобщаются на орграфы естественным образом.
Маршруты и связность в орграфах
Определение. Маршрутом длины k из v в w в орграфе G = (V, E)
называется последовательность ребер вида
т. е. вторая вершина каждого ребра совпадает с первой вершиной следующего ребра. Часто удобно представлять маршрут последовательностью вершин
которые его определяют. Если v = w, то маршрут называют замкнутым маршрутом или циклом. Орграф без циклов называется ацикличным.
Теоремы п.1.2 также справедливы с аналогичными доказательствами для орграфов. Определим связность или матрицу достижимости тем же самым способом. Заметим, однако, что для орграфов отношение R* не является отношением эквивалентности на V и, следовательно, не осуществляет разбиения V.
Пусть обозначает множество всех орграфов, а — множество всех графов. Мы можем определить отображение следующим образом.
Определение. Пусть Тогда множество вершин совпадает с V, а множество ребер F(G) определяется применением следующих операций на Е:
а) удаляются все петли из Е;
б) (v, w) заменяются на [v, w] для всех (v, w) E. Тогда F(G)
является графом, связанным с орграфом G.
Для орграфов понятие связности является более содержательным, чем для графов, и имеет отношение к проблеме обхода. Определим три важных типа связности орграфа.
Определение. Если G = (V, E)— орграф, то будем говорить, что: а) G слабо связный, если граф F(G) связный;
б) G односторонне связный, если для каждой пары различных вершин v, w V существует маршрут из v в w или обратно,
в) G сильно связный, если для каждой пары различных вершин v, w V
существует маршрут из v в w и обратно.
Очевидно, что G сильно связный G односторонне связный G
слабо связный.
Пример 3. Из рис. 8 мы видим, что орграф:
а) только слабо связный (рис. 8,а);
б) односторонне связный, но не сильно связный (рис. 8,b); в) сильно связный (рис. 8,с).
Рис. 8.
В терминах связности матрицы С = А (R*) орграф G сильно связный тогда и только тогда, когда Сij = 1 для всех 1≤i, j ≤п; G односторонне связный тогда и только тогда, когда Сij Сji = 1 для всех 1≤i, j ≤п.
Пример 4. Рассмотрим орграф, представленный диаграммой на рис. 9.
Для этого орграфа
поэтому для
имеем Сij = 1 для всех 1 ≤ i, j ≤ 5 и, следовательно, граф является сильно связным.
Рис. 9.
Для более эффективного вычисления С можно использовать алгоритм Уоршолла.
Если G = (V, E) — орграф, то можно разбить V путем определения отношения эквивалентности ρ следующим образом: vρw, если v = w или существуют маршруты из v в w и обратно. Если {Vi: 1≤i≤p} — разбиение V и {Ei: 1≤i≤p, a Ei = (Vi × Vi) ∩ Е} являются соответ- ствующими множествами ребер, то подграфы Gi = (Vi, Ei) (1≤i≤p) называются сильно связными компонентами G.
Очевидно, что ρ R* и А (ρ) может быть определено из A(R*) как A(ρ)ij= A(R*)ij A(R*)ji; граф G сильно связный тогда и только тогда, когда G имеет только одну сильно связную компоненту, т. е. если р=1.
Пример 6. Для орграфа на рис. 10 имеем
Рис. 10
Таким образом, Gi = ({vi}, ) (l≤i≤4) являются сильно связными компонентами графа.
Пусть G = (V, E) — ациклический орграф. Вершину v V называют листом, если δ+(v)=0. ЕСЛИ (v, w) E, то v является непосредственным предком w, a w — непосредственным потомком v. Если существует маршрут из v в w, то говорят, что v является предком w, а w — потомком v.
Эти понятия не имеют смысла для орграфов, имеющих циклы, так как для таких графов вершина может исходить сама из себя.
Пример 7. Для ациклического орграфа, изображенного на рис. 11, из вершин v2, v4 и v5 ребра не выходят, v1 является предком v5, v5 является прямым потомком v3 и т. д.
Рис. 11.
Существует тесная связь между ациклическими орграфами и частично упорядоченными отношениями. В частности, имеет место следующий результат, доказательство которого мы оставляем в качестве упражнения. Заметим, что для сокращения некоторых доказательств, приведенных ниже, частичные порядки будут основаны скорее на отношении <, чем на отношении ≤, и, следовательно, являются транзитивными и нерефлексивными.
Утверждение.
а) Пусть отношение < является частичным отношением порядка на конечном множестве V, Тогда, если
Достарыңызбен бөлісу: |
