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

Добуток графів - це бінарна операція на графах. Конкретніше, це операція, яка двом графам 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$ означає «з'єднані ребром» і $\sim ̸$ означає «не з'єднані ребром». Символи операцій, наведені нижче, не завжди стандартизовані, особливо в ранніх роботах.

Назва	Умова для ($u_1$, $u_2$) ∼ ($v_1$, $v_2$)	Розміри	Приклад
Декартів добуток $G◻H$	( $u_1$ = $v_1$ і $u_2$ $\sim$ $v_2$ ) або ( $u_1$ $\sim$ $v_1$ і $u_2$ = $v_2$ )	$G_{V_1,E_1}◻H_{V_2,E_2}\to 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}\to 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}\to J_{(V_1{V}_2),(E_2{V}_1+E_1{V}_2^2)}$
Сильний добуток (нормальний добуток) $G⊠H$	( u1 = v1 і u2 ∼ v2 ) або ( u1 ∼ v1 і u2 = v2 ) або ( u1 ∼ v1 і u2 ∼ v2 )	$G_{V_1,E_1}⊠H_{V_2,E_2}\to 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\sim ̸v_1$ і $u_2\sim ̸v_2)$
Кореневий добуток	див. статтю	$G_{V_1,E_1}\cdot H_{V_2,E_2}\to J_{(V_1{V}_2),(E_2{V}_1+E_1)}$
Добуток Кронекера	див. статтю	див. статтю	див. статтю
Зигзаг-добуток	див. статтю	див. статтю	див. статтю
Шаблон:Не перекладено
Гомоморфний добуток $G⋉H$	$(u_1=v_1)$ або $(u_1\sim v_1$ і $u_2\sim ̸v_2)$

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

Мнемоніка

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

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

Див. також

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

Література

• Шаблон:Книга.