3. Найдите декартово произведение и декартову сумму следующих двух графов.
Решение:
Обозначим вершины графов
Запишем для них отношения
|
а1: {a2} a2: {a1,a3,a4} a3: {a2} a4: {a2} |
b1: {b2} b2: {b1,b3} b3: {b2,b4} b4: {b3} |
Декартово произведение графов:
Вершины: (а1,b1), (а1,b2), (а1,b3), (а1,b4), (а2,b1), (а2,b2), (а2,b3), (а2,b4),
(а3,b1), (а3,b2), (а3,b3), (а3,b4), (а4,b1), (а4,b2), (а4,b3), (а4,b4).
Дуги: (а1,b1)–(a2,b2), (а1,b2)-(a2,b1), (а1,b2)-(a2,b3), (а1,b3)-(a2,b2),
(a1,b3)- (a2,b4), (а1,b4) – (a2,b3), (а2,b1) –(a1,b2) (а2,b1) –(a3,b2),
(а2,b1) –(a4,b3), (а2,b2)-(a1,b1), (а2,b2)-(a1,b3), (а2,b2)-(a3,b1),
(а2,b2)-(a3,b3), (а2,b2)-(a4,b1), (а2,b2)-(a4,b3), (а2,b3)-(a1,b2), (а2,b3)-(a1,b4),
(а2,b3)-(a3,b2), (а2,b3)-(a3,b4), (а2,b3)-(a4,b2), (а2,b3)-(a4,b4), (а2,b4)-(a1,b3),
(а2,b4)-(a3,b3), (а2,b4)-(a4,b3), (а3,b1) –(a2,b2), (а3,b2)-(a2,b1), (а3,b2)-(a2,b3),
(а3,b3)-(a2,b2), (а3,b3)-(a2,b4), (а3,b4)-(a2,b3), (а4,b1)-(a2,b2), (а4,b2-(a2,b1),
(а4,b2-(a2,b3), (а4,b3)-(a2,b2), (а4,b3)-(a2,b4), (а4,b4)-(a2,b3).
На основании собранных данных строим граф декартова произведения данных графов:
Сумма графов:
Вершины: (а1,b1), (а1,b2), (а1,b3), (а1,b4), (а2,b1), (а2,b2), (а2,b3), (а2,b4),
(а3,b1), (а3,b2), (а3,b3), (а3,b4), (а4,b1), (а4,b2), (а4,b3), (а4,b4).
Дуги: (а1,b1) → (a2,b1), (a1,b2); (а1,b2) → (a2,b2); (а1,b3) → (a2,b3);
(а1,b4) → (a2,b4); (а2,b1) → (a1,b1), (a3,b1), (a4,b1);
(а2,b2) → (a1,b2), (a3,b2), (a4,b2); (а2,b3) → (a1,b3), (a3,b3), (a4,b3);
(а2,b4) → (a1,b4), (a3,b4), (a4,b4); (а3,b1) → (a2,b1), (a3,b2);
(а3,b2) → (a2,b2), (a3,b1), (a3,b3); (а3,b3) → (a2,b3), (a3,b2), (a3,b4);
(а3,b4) → (a2,b4), (a3,b3); (а4,b1) → (a2,b1), (a4,b2);
(а4,b2) → (a2,b2), (a4,b1), (a4,b3); (а4,b3) → (a2,b3), (a4,b2), (a4,b4);
(а4,b4) → (a2,b4), (a4,b3).
