Композиция графов

Композицией (произведением) двух графов G₁(X) и G₂(X) с одним и тем же множеством вершин Х является граф, у которого множество вер­шин, смежных с вершиной x_i, состоит из всех вершин, достижимых из x_i цепью длины два, первое ребро которой принадлежит G₂(X), а второе – G₁(X) (рис. 2.28). Здесь (x_i, x_j) Î G₂(X), (x_j, x_k) Î G₁(X), (x_i, x_k) Î G₁(G₂(X)).

Композиция графов обозначается как G(X) = G₁(G₂(X)) (на рис. 2.29 изображен пример композиции).