Добуток графів

У таблиці наведено найуживаніші добутки графів. Позначення: ${\displaystyle \sim }$ означає «з'єднані ребром» і ${\displaystyle \not \sim }$ означає «не з'єднані ребром». Символи операцій, наведені нижче, не завжди стандартизовані, особливо в ранніх роботах.

Назва	Умова для (${\displaystyle u_{1}}$, ${\displaystyle u_{2}}$) ∼ (${\displaystyle v_{1}}$, ${\displaystyle v_{2}}$)	Розміри	Приклад
Декартів добуток ${\displaystyle G\square H}$	( ${\displaystyle u_{1}}$ = ${\displaystyle v_{1}}$ і ${\displaystyle u_{2}}$ ${\displaystyle \sim }$ ${\displaystyle v_{2}}$ ) або ( ${\displaystyle u_{1}}$ ${\displaystyle \sim }$ ${\displaystyle v_{1}}$ і ${\displaystyle u_{2}}$ = ${\displaystyle v_{2}}$ )	${\displaystyle G_{V_{1},E_{1}}\square H_{V_{2},E_{2}}\rightarrow J_{(V_{1}V_{2}),(E_{2}V_{1}+E_{1}V_{2})}}$
Тензорний добуток (категорійний добуток) ${\displaystyle G\times H}$	${\displaystyle u_{1}}$ ${\displaystyle \sim }$ ${\displaystyle v_{1}}$ і ${\displaystyle u_{2}}$ ${\displaystyle \sim }$ ${\displaystyle v_{2}}$	${\displaystyle G_{V_{1},E_{1}}\times H_{V_{2},E_{2}}\rightarrow J_{(V_{1}V_{2}),(2E_{1}E_{2})}}$
Лексикографічний добуток ${\displaystyle G\cdot H}$ або ${\displaystyle G[H]}$	u1 ∼ v1 або ( u1 = v1 і u2 ∼ v2 )	${\displaystyle G_{V_{1},E_{1}}\cdot H_{V_{2},E_{2}}\rightarrow J_{(V_{1}V_{2}),(E_{2}V_{1}+E_{1}V_{2}^{2})}}$
Сильний добуток (нормальний добуток) ${\displaystyle G\boxtimes H}$	( u1 = v1 і u2 ∼ v2 ) або ( u1 ∼ v1 і u2 = v2 ) або ( u1 ∼ v1 і u2 ∼ v2 )	${\displaystyle G_{V_{1},E_{1}}\boxtimes H_{V_{2},E_{2}}\rightarrow J_{(V_{1}V_{2}),(V_{1}E_{2}+V_{2}E_{1}+2E_{1}E_{2})}}$
Конормальний добуток (диз'юнктний добуток) ${\displaystyle G*H}$	u1 ∼ v1 або u2 ∼ v2
Модулярний добуток	${\displaystyle (u_{1}\sim v_{1}}$ і ${\displaystyle u_{2}\sim v_{2})}$ або ${\displaystyle (u_{1}\not \sim v_{1}}$ і ${\displaystyle u_{2}\not \sim v_{2})}$
Кореневий добуток	див. статтю	${\displaystyle G_{V_{1},E_{1}}\cdot H_{V_{2},E_{2}}\rightarrow J_{(V_{1}V_{2}),(E_{2}V_{1}+E_{1})}}$
Добуток Кронекера	див. статтю	див. статтю	див. статтю
Зигзаг-добуток	див. статтю	див. статтю	див. статтю
Замінювальний добуток
Гомоморфний добуток[1][2] ${\displaystyle G\ltimes H}$	${\displaystyle (u_{1}=v_{1})}$ або ${\displaystyle (u_{1}\sim v_{1}}$ і ${\displaystyle u_{2}\not \sim v_{2})}$

У загальному випадку добуток графів визначається будь-якою умовою для (u_1, u₂) ∼ (v_1, v₂), яку можна виразити в термінах тверджень u₁ ∼ v₁, u₂ ∼ v₂, u₁ = v₁ і u₂ = v₂.

Нехай ${\displaystyle K_{2}}$ - повний граф з двома вершинами (тобто одне ребро). Добутки графів ${\displaystyle K_{2}\square K_{2}}$, ${\displaystyle K_{2}\times K_{2}}$, і ${\displaystyle K_{2}\boxtimes K_{2}}$ виглядають так, як знак операції множення. Наприклад, ${\displaystyle K_{2}\square K_{2}}$ є циклом довжини 4 (квадрат), а ${\displaystyle K_{2}\boxtimes K_{2}}$ є повним графом з чотирма вершинами.

Нотація ${\displaystyle G[H]}$ для лексикографічного добутку нагадує, що добуток не комутативний.

• Операції над графами