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

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

Пример.

Найти декартово произведение графов G₁ и G₂ (рис. 3.1.16):

Рис. 3.1.16.

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

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

Рис. 3.1.17