Произведение графов

В произведении графов вершины обозначаются парами ab, где символы a и b – обозначения вершин в G ₁ и G ₂ соответственно.

Ребро (1 x,1 y) E, так как первые символы совпадают (рис. 2.16), а в G ₂ есть ребро (x, y). Аналогично и для других ребер.

Рисунок 2.16

Неформально: Произведение G ₁ G ₂ означает, что каждая вершина G ₁ заменяется на копию Ga = G ₂, а каждая вершина G ₂ заменяется на копию Gb = G ₁.