Пересечение (произведение) графов

Пересечением графов G1(x₁,г₁x₁) и G2(x₂,г₂x₂) называется такой граф G(x,гx), у которого множество вершин есть пересечение множеств вершин графов X=X₁ÇX₂, а отображение есть пересечение отображений перемножаемых графов ГX=Г₁X₁ÇГ₂X₂.

Пример.

Пересечение графов G₁ и G₂ предыдущего примера есть граф G(x,гx) (геометрическая реализация на рис 3.1.15):

Рис. 3.1.15

Граф-пересечение содержит вершины и дуги, являющиеся общими у перемножаемых графов.