Пересечение графов

Пусть даны два графа G₁(X) и G₂(X) на одном и том же множестве вершин. Тогда пересечением графов G₁(X) и G₂(X) называется граф G(X), состоящий из ребер, принадлежащих и G₁(X) и G₂(X), то есть если

(x_i, x_j)  G₁(X) и (x_i, x_j)  G₂(X), то (x_i, x_j)  G(X).

Обозначение пересечения двух графов: G(X) = G₁(X)  G₂(X).

Аналогично пересечение n графов G_i(X) (i = 1, …, n) обозначается как

_n

G_i(X) =  G_i(X) и определяет граф G(X), состоящий из ребер, принадле-

ⁱ⁼¹

жащих одновременно всем графам G_i(X).

Для графов, используемых в примере 1 (рис. 2.24), имеем:

а) G₁(X)  G₂(X) =  (ноль - граф);

б) пересечение графов G₁(X) и G₂(X) изображено на рис. 2.26.

Для графов, определенных на различных множествах вершин опера­ция пересечения определяется следующим образом:

_n

G(X) = G₁(X₁)G₂(X₂)…G_n(X_n) =G_i(X_i),

_n ⁱ⁼¹

где Х = Х₁  Х₂  …  Х_n =  X_i

ⁱ⁼¹ _n

иG(x_j) = G₁(x_j)G₂(x_j)…G_n(x_j) =G_i(x_j),

x_j X._i=1

Пересечение графов G₁(X₁) и G₂(X₂) примера 2 изображено на рис. 2.27.

Композиция графов

Композицией (произведением) двух графов G₁(X) и G₂(X) с одним и тем же множеством вершин Х является граф, у которого множество вер­шин, смежных с вершиной x_i, состоит из всех вершин, достижимых из x_i цепью длины два, первое ребро которой принадлежит G₂(X), а второе – G₁(X) (рис. 2.28). Здесь (x_i, x_j)  G₂(X), (x_j, x_k)  G₁(X), (x_i, x_k)  G₁(G₂(X)).

Композиция графов обозначается как G(X) = G₁(G₂(X)) (на рис. 2.29 изображен пример композиции).

Пример 3.

Композицию графов, изображенных на рис. 2.29, иллюстрирует табл.2.1.

Таблица 2.1 – Соответствие между вершинами графов (рис. 2.29)

Соответст- вие Вер- шина	(xi, xj)  G1(X)	(xi, xj)  G2(X)	(xi, xj)  G1(G2(X))	(xi, xj)  G2(G1(X))
x1	(x1, x4)	(x1, x5)		
x2	(x2, x5)			(x2,x3)
x3	(x3, x2)	(x3, x4)	(x3, x3)	
x4	(x4, x3)			(x4,x4)
x5		(x5, x3)	(x5, x2)	

На основе таблицы можно по­строить G₁(G₂(X)) и G₂(G₁(X))

(рис. 2.30).

Транзитивное замыкание графов

Пусть имеется нетранзитивный ориентированный граф G(X). Его можно сделать транзитивным, добав­ляя дуги с целью получения замыкаю­щей дуги (x_i, x_k) для каждой пары его последовательных дуг (x_i, x_j) и (x_j, x_k). В этом случае говорят, что транзитивный граф G_тр(X) получен из нетран­зитивного G(X) при помощи транзитивного замыкания графа (аналогично транзитивному замыканию отображений)

G_тр(X) = {x}  G(x)  G²(x)  G³(x), …, xX.

Пример 4.

Декартово произведение

Декартовым произведением двух графов G₁(X₁) и G₂(X₂) называ­ется граф G(X) = G₁(X₁)  G₂(X₂), определенный следующим образом:

а) множество вершин Х является декартовым произведением мно­жеств Х₁ и Х₂: Х = Х₁  Х₂ = {(x_i1, x_j2) / x_i1  X₁, x_j2X₂};

б) множество вершин, смежных с вершиной (х_i1, х_j2) декартова про­изведения двух графов, определяется как G(x_i1, x_j2) = G₁(x_i1) G₂(x_j2), т.е. как декартово произведение множеств вершин графа G₁(X₁), смежных с х_i1 и графа G₂(X₂), смежных с x_j2. Пример приведен на рис. 2.32.

Пример 5.

Для примера 5 G(x₀₁,x₀₂)={(x₁₁,x₁₂), (x₂₁,x₁₂)},

G₁(x₀₁)={x₁₁, x₂₁}, G(x₀₁, x₁₂)={(x₁₁, x₀₂), (x₂₁, x₀₂)},

G₁(x₁₁)= x₀₁, G₂(x₀₂)=x₁₂, G(x₁₁, x₀₂)=(x₀₁, x₁₂),

G₁(x₂₁)= x₀₁, G₂(x₁₂)=x₀₂, G(x₁₁, x₁₂)=(x₀₁, x₀₂),

G(x₂₁, x₀₂)=(x₀₁, x₁₂),

G(x₂₁, x₁₂)=(x₀₁, x₀₂).

Пусть даны n графов G₁(x₁), G₂ (x₂), ..., G_n (x_n). Тогда граф

G(x)= G₁(x₁)  G₂(x₂)  ...  G_n(x_n) называется декартовым произве-

­­­­де­­нием указанных графов, если

а) x = x₁  x₂  ...  x_n = {( x₁ , x₂ , ..., x_n) / x₁  X₁, x₂  X₂, ... , x_n  X_n};

б) G(x₁ , x₂ , ... , x_n) = G₁(x₁)G₂(x₂)...G_n(x_n) – декартово произве­дение подмножеств вершин графов G_i(x_i) (i = 1, ..., n), смежных с верши­нами x₁, x₂, ... , x_n.