Композиция p1p2 p1q2+p2p2q1

Произведение p1p2 p1q2+p2q1

Соединение p1+p2 q1+q2+p1p2

Объединение p1+p2 q1 + q2

 

Полный n-дольный граф K(p1, p2, ...,pn) определяется как последовательное соединение Kp1+Kp2+...+KPn - Ясно, что в этом графе åpi ; вершин и åpipj ребер.

Важный класс графов, называемых кубами, наиболее естественно описывается с помощью произведений. Рекурсивно определяется п-мерный куб Qn: Q1=K2 и Qn=K2xQn-1. Таким образом, Qn имеет 2ⁿ вершин, которые можно представлять наборами а1...аn, где an равно 0 или 1. Две вершины (или точки) куба Qn смежны, если их двоичные представления отличаются только в одной позиции (в одном разряде). Q2 и Q3 показаны на рисунке.

Если графы G и H таковы, что отождествление любой вершины графа G с произвольной вершиной графа Н приводит к одному и тому же графу (с точностью до изоморфизма), то граф, получаемый с помощью описанного отождествления вершин, обозначим через G°Н.