Пример 3. Композицию графов, изображенных на рис

Композицию графов, изображенных на рис. 2.29, иллюстрирует табл.2.1.

Таблица 2.1 – Соответствие между вершинами графов (рис. 2.29)

Соответст- вие Вер- шина	(xi, xj) Î G1(X)	(xi, xj) Î G2(X)	(xi, xj) Î G1(G2(X))	(xi, xj) Î G2(G1(X))
x1	(x1, x4)	(x1, x5)	Æ	Æ
x2	(x2, x5)	Æ	Æ	(x2,x3)
x3	(x3, x2)	(x3, x4)	(x3, x3)	Æ
x4	(x4, x3)	Æ	Æ	(x4,x4)
x5	Æ	(x5, x3)	(x5, x2)	Æ

На основе таблицы можно по­строить G₁(G₂(X)) и G₂(G₁(X))

(рис. 2.30).

Транзитивное замыкание

Графов

Пусть имеется нетранзитивный ориентированный граф G(X). Его можно сделать транзитивным, добав­ляя дуги с целью получения замыкаю­щей дуги (x_i, x_k) для каждой пары его последовательных дуг (x_i, x_j) и (x_j, x_k). В этом случае говорят, что транзитивный граф G_тр(X) получен из нетран­зитивного G(X) при помощи транзитивного замыкания графа (аналогично транзитивному замыканию отображений)

G_тр(X) = {x} È G(x) È G²(x) È G³(x), …, xÎX.

Пример 4.