Пересечением графов G1(x1,г1x1) и G2(x2,г2x2) называется такой граф G(x,гx), у которого множество вершин есть пересечение множеств вершин графов X=X1ÇX2, а отображение есть пересечение отображений перемножаемых графов ГX=Г1X1ÇГ2X2.
Пример.
Пересечение графов G1 и G2 предыдущего примера есть граф G(x,гx) (геометрическая реализация на рис 3.1.15):
Рис. 3.1.15 |
Граф-пересечение содержит вершины и дуги, являющиеся общими у перемножаемых графов.