Маршруты и связность в ориентированных графах

Неориентированные графы

Основные определения

Пусть V – конечное множество некоторых элементов, и I_V – его тождественное отношение, такое, что:

Обозначим

Определим отношение эквивалентности следующим образом:

(v₁,v₂) ~ (w₁,w₂), если (v₁,v₂) = (w₁,w₂) или (v₁,v₂) = (w₂,w₁). Множество эквивалентных классов, определенное таким образом, обозначим

Каждый класс эквивалентности содержит два элемента, так как если

, то [(v₁,v₂)] = {(v₁,v₂), (v₂,v₁)}.

Графом называется упорядоченная пара G = (V, E), где V – непустое конечное множество вершин, а , то есть E - это множество неупорядоченных пар различных вершин.

Множество E - это множество ребер графа. Обычно в графе всегда можно определить количество вершин |V| и ребер |E|.

Граф G определяет нерефлексивное, симметричное отношение на множестве V. Обратное утверждение тоже верно: нерефлексивное, симметричное отношение на множестве V определяет граф.

Изображение графа G = (V, E) получается путем расположения различных точек на R² для каждой вершины v Î V . Причем, если [v, w] Î E, проводим линию, соединяющую вершины v и w.

Графы в значительной мере выражают отношения между вершинами, а не их расположение в пространстве. То есть один и тот же граф может быть изображен разными способами (рис. 1).

v1 v2 v3 v2

v1

v3

Рис. 1. Примеры изображения графа

Приведем пример построения графа (рис. 2).

Пусть V={1, 2, 3, 4, 5}.

Тогда I_V = {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5)}.

V² = V ´ V = {(1, 1), (1, 2), (1, 3), (1, 4), (1, 5),

(2, 1), (2, 2), (2, 3), (2, 4), (2, 5),

(3, 1), (3, 2), (3, 3), (3, 4), (3, 5),

(4, 1), (4, 2), (4, 3), (4, 4), (4, 5),

(5, 1), (5, 2), (5, 3), (5, 4), (5, 5)}

= {(1, 1), (1, 2), (1, 3), (1, 4), (1, 5),

(2, 1), (2, 2), (2, 3), (2, 4), (2, 5),

(3, 1), (3, 2), (3, 3), (3, 4), (3, 5),

(4, 1), (4, 2), (4, 3), (4, 4), (4, 5),

(5, 1), (5, 2), (5, 3), (5, 4), (5, 5)}

= {[(v₁, v₂)], [(v₁, v₃)], [(v₁, v₄)], [(v₁, v₅)],

[(v₂, v₁)], [(v₂, v₃)], [(v₂, v₄)], [(v₂, v₅)],

[(v₃, v₁)], [(v₃, v₂)], [(v₃, v₄)], [(v₃, v₅)],

[(v₄, v₁)], [(v₄, v₂)], [(v₄, v₃)], [(v₄, v₅)],

[(v₅, v₁)], [(v₅, v₂)], [(v₅, v₃)], [(v₅, v₄)]}.

Рис. 2 . Полный граф

Граф H = (V₁, E₁) является подграфом графа G = (V, E), если V₁ Í V и E₁ Í E.

Если V₁ = V, то граф H является остовным подграфом графа G. Если V₁ – непустое подмножество вершин графа (V, E), то подграф (V₁, E₁), порожденный V₁, определяется как

[v, w] Î E₁ Û v, w Î V₁ и [v, w] Î E.

Граф G = (V, E) называется полным, если для всех v₁, v₂ Î V имеем [v₁, v₂] Î E. Полный граф с n вершинами обозначается K_n.

Граф G = (V, E) называется двудольным, если существует разбиение множества его вершин V = {V₁, V₂} такое, что никакие две вершины из V₁ или из V₂ не являются смежными. Двудольный граф называется полным, если для любой пары v₁ Î V, v₂ Î V имеем [v₁, v₂] Î E. Если |V₁| = m и |V₂| = n, то полный двудольный граф G = (V, E) обозначается K_m,_n.

Маршруты, циклы и связность

Значительная часть теории графов и ее приложений занимается вопросами существования и изучения свойств маршрутов в графах.

Пусть G = (V, E) – граф. Маршрутом длины k в графе G из вершины v в вершину w называется последовательность <v₀, v₁, v₂, …, v_k> вершин (необязательно различных) v_i Î V, таких, что v₀ = v, v_k = w, а [v_i-1, v_i] Î E для i = 1, …, k.

Маршрут называется замкнутым, если v₀ = v_k.

Маршрут называется цепью, если все его вершины различны. Замкнутая цепь называется циклом. Цикл называется простым, если только v₀ = v_k, а остальные вершины v_i различны.

Если существует маршрут из v в w, v, w Î V, то говорят, что w достижима из v.

Граф без циклов называется ациклическим.

Граф G = (V, E) называется связным, если каждая пара различных вершин может быть соединена маршрутом.

Деревом называется связный ациклический граф. Корневым деревом называется дерево с выделенной вершиной, называемой корнем.

Остовным деревом для G = (V, E) называется остовный подграф, являющийся деревом.

Пусть {V_i : 1 £ i £ p} – разбиение графа G = (V, E), определяемое отношением R^*. (R^* - отношение рефлексивного замыкания). Тогда p – число связности графа G = (V, E). Подграфы (V_i, E_i), порожденные классами эквивалентности, называют компонентами связности графа G.

Лесом называется граф, в котором каждая связная компонента является деревом. Остовный лес для графа G = (V, E) – это совокупность вершин разъединенных деревьев T_i = (V_i, E_i):

Ориентированные графы

Основные определения

Во многих приложениях теории графов требуется, чтобы ребра графа имели направление. Например: поток данных, проходящий через программу.

Ориентированный граф G (или просто орграф) есть пара G = (V, E), где V – конечное множество вершин, а E – произвольное подмножество.

Ориентированный граф G = (V, E) определяет отношение на V. Этот факт можно доказать следующим образом. Пусть R – отношение, такое, что vRw тогда и только тогда, когда (v, w) Î E. Очевидно, что R является отношением.

Обратное утверждение также верно: пусть V – конечное множество вершин. Тогда отношение на V определяет ориентированный граф, у которого множество вершин V. Этот факт можно доказать так. Если R – отношение на V, то орграф G = (V, E), определяемый отношением R, имеет множество ребер E, где (v, w) Î E тогда и только тогда, когда vRw.

Направление ребра обозначают порядком в V ´ V. Например, если (v, w) Î E, то ребро выходит из v и входит в w.

Приведем пример построения ориентированного графа (рис. 3).

Пусть V = {v₁, v₂, v₃}, E₁ = {(v₁, v₂), (v₂, v₃), (v₃, v₁)}. Тогда получим граф G₁ = (V, E₁) (рис. 3, а).

Пусть V = {v₁, v₂, v₃}, E₂ = {(v₁, v₁), (v₁, v₂), (v₁, v₃), (v₂, v₃), (v₃, v₁)}. Тогда получим граф G₂ = (V, E₂) (рис. 3, б).

а) б)

Рис. 3. Примеры ориентированных графов:

а – граф G₁ = (V, E₁); б – граф G₂ = (V, E₂);

Для орграфа реберное отношение необязательно симметрично или рефлексивно. Поэтому допустимы ребра типа (v, v), называемые петлями. Степень вершины v ÎV обозначается s(v) = s ⁺ (v) + s ^- (v), где s ^- (v) – число ребер, входящих в v, s ⁺ (v) – число ребер, выходящих из v.

Множества {w: (w, v) Î E} и {w: (v, w) Î E} называют соответственно входящим узлом и выходящим узлом.

Маршруты и связность в ориентированных графах

Маршрутом длины k из v в w в орграфе G = (V, E) называется последовательность ребер вида: (v, w₁), (w₁, w₂), (w₂, w₃), …, (w_k-2, w_k-1), (w_k-1, w), то есть вторая вершина каждого ребра совпадает с первой вершиной следующего ребра.

Удобно представлять маршрут в орграфе последовательностью вершин: v, w₁, w₂, w₃, …, w_k-2, w_k-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. Типы связности орграфа: а – слабо связный, б – односторонне связный, в – сильно связный

Если {V_i: 1 £ i £ p} – разбиение V и {E_i: 1 £ i £ p, а E_i = (V_i ´ V_i) ìüE} являются соответствующими множествами ребер, то подграфы G_i = (V_i, E_i), 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. Предки и потомки в ациклическом орграфе:

вершины v₂ , v₄ ,v₅ являются листьями, так как из них ребра не выходят; вершина v₁ – является предком v₅, v₅ – прямой потомок v₃.

Существует тесная связь между ациклическими орграфами и частично упорядоченными отношениями:

· Пусть отношение < является частичным отношением порядка на конечном множестве V. Тогда, если E = {(v, w): v < w}, то пара G = (V, E) является ациклическим ориентированным графом.

· Пусть G = (V, E) – ациклический орграф и отношение < определяется следующим образом: v < w, если v является предком w. Тогда отношение < является частичным отношением порядка на V.

Ориентированное дерево T = (V, E) – это ациклических орграф, в котором одна вершина v_r Î V не имеет предков, а каждая другая вершина имеет только одного непосредственного предка. Вершина v_r называется корнем дерева. Бинарное дерево – это ориентированное дерево, в котором каждая вершина имеет не более двух непосредственных потомков, то есть s ⁺ (v) £ 2, " v Î V. Говорят, что бинарное дерево называется полным, если каждая вершина, не являющаяся листом, имеет ровно двух непосредственных потомков.

Не нашли, что искали? Воспользуйтесь поиском по сайту: