![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Нехай задані два орграфи 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. Об'єднання графів
Властивості операції об'єднання
" xiÎXÈY(S(xi) =Г(xi) È P(xi))
" xiÎXÈY(S-1(xi) =Г-1(xi) È P-1(xi))
Визначення. Перетинанням Q = GÇH називається граф Q = <A, S> такий, що
A = XÇY, а. S = ГÇР.
Приклад. A = {x1, x2}, S = {<x2, x2>}, Q – підграф графів G і Н із попереднього прикладу, QÌ G і QÌ H
Рис. 16.2. Перетинання графів
Властивості операції перетинання
" xiÎXÇY(S(xi) =Г(xi) Ç P(xi))
" xiÎXÇY(S-1(xi) =Г-1(xi) Ç P-1(xi))
Граф G = <X, Г> називається наповненим (повним), якщо Г = X2.
Визначення. Доповненням графу G = <X, Г> до наповненого називається граф
` G = <X, ` Г>, де ` Г = X2 \ Г.
Приклад. G = <X, Г>, X = {x1, x2, x3}, Г ={<x1, x2>, <x1, x3>, <x2, x2>, <x2, x3>, <x3, x1>}, X2 ={<x1, x1>, <x1, x2>, <x1, x3>, <x2, x1>, <x2, x2>, <x2, x3>, <x3, x1>, <x3, x2>, <x3, x3>},
` G = <X, ` Г >, ` Г = X2 \ Г = {<x1, x1>, <x2, x1>, <x3, x2>, <x3, x3>}.
Рис. 16.3. Доповнення графу ` G = <X, ` Г >
Властивості операції доповнення
" xiÎX(`Г(xi) = X \ Г(xi))
" xiÎX(`Г-1(xi) = X \ Г-1(xi))
Визначення. Різницею графів 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
Властивості операції різниці:
" xiÎXÇY(S(xi) = Г(xi) \ P(xi))
" xiÎXÇY(S-1(xi) = Г-1(xi) \ P-1(xi))
Нехай задані два графи G = <X, Г>, H = <Y, P>.
Дата публикования: 2014-11-18; Прочитано: 1285 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!