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

Добуток графів - це бінарна операція на графах. Конкретніше, це операція, яка двом графам G₁ і G₂ ставить у відповідність граф H з такими властивостями:

• Множина вершин графу H - це прямий добуток V(G₁) × V(G₂), де V(G₁) і V(G₂) є множинами вершин G₁ і G₂ відповідно.
• Дві вершини (u_1, u₂) і (v_1, v₂) графу H з'єднані ребром тоді і тільки тоді, коли вершини u_1, u_2, v_1, v₂ задовольняють певним умовам, що відповідають типу добутку (див. нижче).

Види добутків

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

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

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

Мнемоніка

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

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

Див. також

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

Література

• Imrich, Wilfried; Klavžar, Sandi. Product Graphs: Structure and Recognition. — Wiley, 2000. — ISBN 0-471-37039-8..