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

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

Пример.

Пересечение графов G1 и G2 предыдущего примера есть граф G(x, гx):

Рис. 15.

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

Прямое произведение графов.

Прямым (декартовым) произведением графов G1(x₁, г₁x₁) и G2(x₂, г₂x₂) называется граф G(x, гx), для которого X=X₁*X₂ и гx=г₁x₁*г₂x₂.

Пример.

Найти декартово произведение графов G1 и G2:

Рис. 16.

Обозначим каждую получившуюся вершину через , тогда

Геометрическая реализация графа G имеет вид (рис.17):

Рис. 17.