Властивості базових операцій над графами

1. GÈH = HÈG; GÇH = HÇG;
комутативність

2. GÈ(HÈF) = (GÈH)ÈF; GÇ(HÇF) = (GÇH)ÇF;
асоціативність

3. GÈ(HÇF) = (GÈH)Ç(GÈF); GÇ(HÈF) = (GÇH)È(GÇF);
дистрибутивність

4. GÈG_Æ = G; GÇG_Æ = G_Æ;
GÈG_U = G_U; GÇG_U = G;
властивості меж

5. GÈG = G; GÇG = G;
ідемпотентність

6. GÈ`G = G<sub>U</sub>; GÇ`G = G_Æ;
доповнення

7. GÈ(GÇH) = G; GÇ(GÈH) = G;
поглинання

8. (GÈH)Ç(GÈ`H) = GÈH<sub>Æ</sub>; (GÇH)È(GÇ`H) = GÇH_U;
склеювання

9. GÈ(`GÇF) = GÈ(G<sub>U</sub>ÇF); GÇ(`GÈF) = GÇ(G_ÆÈF);
Блейка-Порецького

10. ù(GÈH) = ` GÇ ` H ù(GÇH) = ` GÈ ` H
де-Моргана

Визначення. Декартовим добутком Q = G´H графів Q = <X, Г> і
Н = <Y, P> називається новий граф Q = <A, S>, де A =X´Y і для будь якого <x, y>ÎA виконується S(<x, y>) =Г(x)´P(y)).

Приклад: Для графів G =<X, Г>, H = <Y, P>, у яких X = {x1, x2},
Г ={<x1, x1>, <x2, x1>, <x2, x2>} і Y = {y1, y2}, P = {<y1, y1>, <y1, y2>, <y2, y1>}, а також Г(x1)= = {x1}, Г(x2) = {x1, x2}, P(y1) = {y2, y1}, P(y2) = {y1}, множина вершин графу Q =
= <A, S> і множина переходів рівні:

A = X´Y = {a1, a2, a3, a4} = {<x1, y1>, <x1, y2>, <x2, y1>, <x2, y2>}, S(<x1, y1>) = Г(x1)´P(y1) = {<x1, y1>, <x1, y2>}, S(<x1, y2>) = Г(x1)´P(y2) = {<x1, y1>}, S(<x2, y1>) = F(x2)´P(y1) = ={<x1, y1>, <x1, y2>, <x2, y1>, <x2, y2>}, S(<x2, y2>) = =Г(x2)´P(y2) = {<x1, y1>, <x2, y1>}

Рис. 16.5. Декартів добуток графів Q = G´H

Визначення. Композицією Q = G ° H графів G = <Х, Г> і H =<Y, P> називається граф Q = <A, S>, де A = X´Y і для <x, y>ÎA виконується S(<x, y>)) ={Г(x)´Y}È{X´P(y)}).

Приклад. Для графів G = <X, Г>, H = <Y, P>, у яких X = {x1, x2},
Г = {<x1, x1>, <x2, x1>, <x2, x2>} і Y = {y1, y2}, P = {<y1, y1>, <y1, y2>, <y2, y1>},

а також Г(x1)={x1}, Г(x2)={x1, x2}, P(y1)={y2, y1}, P(y2)={y1},

множина вершин графу Q = <A, S> і множина переходів рівні

A = X´Y = {a1, a2, a3, a4} = {<x1, y1>, <x1, y2>, <x2, y1>, <x2, y2>}, S(<x1, y1>) = {{x1}´{y1, y2}}È{{x1, x2}´{y1, y2}} = {a1, a2, a3, a4}, S(<x1, y2>) = {{x1}´{y1, y2}}È{{x1, x2}´{y1}} = {a1, a2, a3}, S(<x2, y1>) = {{x1, x2}´{y1, y2}}({{x1, x2}´{y1, y2}} = {a1, a2, a3, a4}, S(<x2, y2>) = {{x1, x2}´{y1, y2}}È{{x1, x2}´{y1}} = {a1, a2, a3, a4}.

Рис. 16.6. Композиція графів Q = G ° H

Контрольні запитання

1. Що є об'єднанням графів, яка різниця цієї операції зі звичайним множинним об’єднанням?

2. Які властивості має об'єднання?

3. Що є перетинанням графів, яка різниця цієї операції зі звичайним множинним перетинанням?

4. Які властивості у перетинання?

5. Що є доповненням графів, яка різниця цієї операції зі звичайним множинним доповненням?

6. Які властивості у доповнення?

7. Що є різницею графів, яка різниця цієї операції зі звичайною множинною різницею?

8. Які властивості має різниця?

9. Які десять властивостей мають базові операції над графуми?

10. Яка різниця між звичайними властивостями операцій для множин та операціями для графів?

11. Що є декартовим добутком графів?

12. Що є композицією графів?