Операції над графами

Нехай задані два орграфи G =<X, Г>, H = <Y, P>.

Визначення. Об'єднанням Q = GÈH називається граф Q = <A, S> такий, що

A = XÈY, а S = ГÈР.

Приклад: Граф G, для якого X = {x1, x2, x3}, Г = {<x1, x2>, <x1, x3>, <x2, x2>, <x3, x2>}; граф H, для якого Y ={x1, x2},
P = {<x1, x1>, <x2, x1>, <x2, x2>}. У результати є граф Q, для якого A = {x1, x2, x3}, S = {<x1, x1>, <x1, x2>, <x1, x3>, <x2, x1>, <x2, x2>, <x3, x2>}. G і H – підграф графу Q, GÌQ і HÌ Q

Рис. 16.1. Об'єднання графів

Властивості операції об'єднання

" x_iÎXÈY(S(x_i) =Г(x_i) È P(x_i))

" xiÎXÈY(S^-1(x_i) =Г^-1(x_i) È P^-1(x_i))

Визначення. Перетинанням Q = GÇH називається граф Q = <A, S> такий, що

A = XÇY, а. S = ГÇР.

Приклад. A = {x1, x2}, S = {<x2, x2>}, Q – підграф графів G і Н із попереднього прикладу, QÌ G і QÌ H

Рис. 16.2. Перетинання графів

Властивості операції перетинання

" x_iÎXÇY(S(x_i) =Г(x_i) Ç P(x_i))

" x_iÎXÇY(S^-1(x_i) =Г^-1(x_i) Ç P^-1(x_i))

Граф G = <X, Г> називається наповненим (повним), якщо Г = X².

Визначення. Доповненням графу G = <X, Г> до наповненого називається граф

` G = <X, ` Г>, де ` Г = X² \ Г.

Приклад. G = <X, Г>, X = {x1, x2, x3}, Г ={<x1, x2>, <x1, x3>, <x2, x2>, <x2, x3>, <x3, x1>}, X² ={<x1, x1>, <x1, x2>, <x1, x3>, <x2, x1>, <x2, x2>, <x2, x3>, <x3, x1>, <x3, x2>, <x3, x3>},

` G = <X, ` Г >, ` Г = X² \ Г = {<x1, x1>, <x2, x1>, <x3, x2>, <x3, x3>}.

Рис. 16.3. Доповнення графу ` G = <X, ` Г >

Властивості операції доповнення

" x_iÎX(`Г(x_i) = X \ Г(x_i))

" x_iÎX(`Г^-1(x_i) = X \ Г^-1(x_i))

Визначення. Різницею графів Q = G \ H називається граф Q=
= <A, S> такий, що

A = XÇY, S = Г \ P = ГÇ `P, тобто Q = G \ H = GÇ `H

Приклад. Для двох вхідних графів G = <X, Г>, H = <Y, P> для графу різниці Q = G \ H множини вершин і дуг визначаються як
A = XÇ Y = { x1, x2}, `P = {<x1, x2>}, S = {<x1, x2>}.

Рис. 16.4. Різниця графів Q = G \ H = GÇ`H

Властивості операції різниці:

" x_iÎXÇY(S(x_i) = Г(x_i) \ P(x_i))

" x_iÎXÇY(S^-1(x_i) = Г^-1(x_i) \ P^-1(x_i))

Нехай задані два графи G = <X, Г>, H = <Y, P>.