Теоретико-множинні операції над графами

Задачі

Графи G і H задані множинами фактор-безлічей F_G = ({x₂}, {x₂, x₃}, {Æ}) і F_H = ({x₂}, {x₁}), необхідно визначити:

GÈH, GÇH;

`G, `H;

G\H, H\G;

GÅH, GÅ`H.

Графи G, H і P задані множинами фактор-безлічей F_G = ({x₂, x₃}, {x₃}, {Æ}), F_H = ({x₁}, {x₁, x₂}) і P = ({x₁}, {x₂}, {x₃}), необхідно визначити:

G\H, H\G;

G\PÇH;

(PÈH)\(GÇH);

(PÅH)Ç(G\H).

Для графів G і H, заданих множинами фактор-безлічей F_G = ({x₁, x₂}, {x₂}) і F_H = ({y₁}, {y₁, y₂}), побудувати граф, рівний:

декартовому добутку;

композиції.

Для графів G, H і P, заданих матрицями суміжності (відповідно табл. 4.4., 4.5. і 4.6.), побудувати матрицю суміжності графа, рівного:

GÈH, GÇH;

`G, `H;

G\H, H\G, G\P, P\H;

(G\P)Ç(GÈ`H);

(GÅ`H)Ç(`PÈG).

Таблиця 4.4

	x1	x2	x3
x1
x2
x3

Таблиця 4.5

	x1	x2	x3	X4
x1
x2
x3
x4

Таблиця 4.6

	X1	x2	x3	x4
x1
x2
x3
x4

Для графів G і H, заданих матрицями інцидентності (відповідно табл. 4.7. і 4.8., дуги, що з'єднують однойменні вершини в різних графах, мають однакове позначення), побудувати матрицю інцидентності результуючого графа, рівного:

GÈH, GÇH;

`G, `H;

G\H, H\G;

(GÅH), (`GÅ`H).

Таблиця 4.7

	v1	v2	v3	v4	v5	V6
X1		-1			-1
X2	-1
X3			-1	-1		-1

Таблиця 4.8

	v1	v2	V3
x1
x2	-1	-1
x3			-1

Для графів G і H, заданих матрицями суміжності (відповідно табл. 4.9. і 4.10.), побудувати матрицю суміжності результуючого графа, який дорівнює:

декартовому добутку;

композиції.

Таблиця 4.9

	x1	x2	X3
x1
x2
x3

Таблиця 4.10

	x1	x2	X3
x1
x2
x3

Для графів G і H задачі 6, заданих матрицями суміжності і (відповідно табл. 4.9. і 4.10.), розробити блок-схеми і написати програми виконання операцій:

GÈH, GÇH;

`G, `H;

G\H, H\G;

(GÅH);

(GÅ`H)Ç(`GÈH).

Для графів G і H, заданих множинами фактор-безлічей F_G = ({x₁, x₂}, {x₂}) і F_H = ({y₁}, {y₁, y₂}), розробити блок-схеми і написати програми виконання операцій:

декартового добутку;

композиції.