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

Произведение графов — это бинарная операция на графах. Конкретнее, это операция, которая двум графам G₁ и G₂ сопоставляет граф H со следующими свойствами:

• Множество вершин графа H — это прямое произведение V(G₁) × V(G₂), где V(G₁) и V(G₂) являются множествами вершин G₁ и G₂ соответственно.
• Две вершины (u₁, u₂) и (v₁, v₂) графа H соединены ребром тогда и только тогда, когда вершины u₁, u₂, v₁, v₂ удовлетворяют определённым условиям, соответствующим типу произведения (смотрите ниже).

Виды произведений

Следующая таблица показывает наиболее употребительные произведения графов. В таблице ${\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][1] ${\displaystyle G\ltimes H}$	${\displaystyle (u_{1}=v_{1})}$ или ${\displaystyle (u_{1}\sim v_{1}}$ и ${\displaystyle u_{2}\not \sim v_{2})}$

В общем случае произведение графов определяется любым условием для (u₁, u₂) ∼ (v₁, 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]}$ для лексикографического произведения напоминает, что произведение не коммутативно.

См. также

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

Примечания

1. David E. Roberson, Laura Mancinska. Graph Homomorphisms for Quantum Players. — 2012.
2. R. Bačík, S. Mahajan. Computing and Combinatorics. — 1995. — Т. 959. — С. 566, Semidefinite programming and its applications to NP problems. — (Lecture Notes in Computer Science). — ISBN 3-540-60216-X. — doi:10.1007/BFb0030878.

Литература

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