Gráfszorzás

A matematika, azon belül a gráfelmélet területén a gráfszorzás olyan kétváltozós gráfművelet, amely gráfok rendezett párjaihoz egy új gráfot rendel. Specifikusan: a két bemeneti gráf, G₁ és G₂ alapján kimenetként a következő tulajdonságokkal rendelkező H-t adja:

H csúcshalmaza a V(G₁) × V(G₂) Descartes-szorzat, ahol V(G₁) és V(G₂) a G₁, illetve a G₂ csúcshalmazai.
Két H-beli csúcs (u₁, u₂) és (v₁, v₂) pontosan akkor szomszédosak, ha az u₁, u₂, v₁, v₂ csúcsokra teljesül valamely G₁ és G₂ éleire vonatkozó feltétel. A gráfszorzatok különböző fajtái éppen ebben a feltételben térnek el.

A különböző gráfszorzatok leírása és jelölése az irodalomban erősen változó lehet; bár az alább alkalmazott jelölések elég elterjedtek, érdemes egy-egy cikk olvasásakor ellenőrizni, hogy az adott szerző egy gráfszorzat mely definícióját használja, főleg régebbi szövegekben.

Áttekintő táblázat

A következő táblázat felsorolja az elterjedtebb gráfszorzatokat. A $\sim$ ; jelentése „a két csúcs össze van kötve”, míg a $\sim̸$ az össze nem kötöttséget jelöli. A táblázatban alkalmazott szimbólumok nem tekinthetők univerzálisan elfogadottnak, különösen a régi cikkekben találhatók egyedi jelölések.

Név	$(u_{1}, u_{2}) \sim (v_{1}, v_{2})$ feltétele	Méret (élek száma) $\begin{matrix} n_{1} = \| V (G) \| & n_{2} = \| V (H) \| \\ m_{1} = \| E (G) \| & m_{2} = \| E (H) \| \end{matrix}$	Példa
Descartes-szorzat $G ◻ H$	( $u_{1}$ = $v_{1}$ és $u_{2}$ $\sim$ $v_{2}$ ) vagy ( $u_{1}$ $\sim$ $v_{1}$ és $u_{2}$ = $v_{2}$ )	$m_{2} n_{1} + m_{1} n_{2}$
Tenzorszorzat (kategóriaszorzat) $G \times H$	$u_{1}$ $\sim$ $v_{1}$ és $u_{2}$ $\sim$ $v_{2}$	$2 m_{1} m_{2}$
Lexikografikus szorzat $G \cdot H$ vagy $G [H]$	u₁ ∼ v₁ vagy ( u₁ = v₁ és u₂ ∼ v₂ )	$m_{2} n_{1} + m_{1} n_{2}^{2}$
Erős szorzat (Normál szorzat, ÉS szorzat) $G ⊠ H$	( u₁ = v₁ és u₂ ∼ v₂ ) vagy ( u₁ ∼ v₁ és u₂ = v₂ ) vagy ( u₁ ∼ v₁ és u₂ ∼ v₂ )	$n_{1} m_{2} + n_{2} m_{1} + 2 m_{1} m_{2}$
Ko-normális szorzat (diszjunktív szorzat, VAGY szorzat) $G * H$	u₁ ∼ v₁ vagy u₂ ∼ v₂
Moduláris szorzat	$(u_{1} \sim v_{1}$ és $u_{2} \sim v_{2})$ vagy $(u_{1} \sim̸ v_{1}$ és $u_{2} \sim̸ v_{2})$
Gyökeres szorzat	Lásd a szócikket	$m_{2} n_{1} + m_{1}$
Cikkcakkszorzat	Lásd a szócikket	Lásd a szócikket	Lásd a szócikket
Replacement szorzat
Homomorf szorzat^[1]Sablon:Refn $G ⋉ H$	$(u_{1} = v_{1})$ vagy $(u_{1} \sim v_{1}$ és $u_{2} \sim̸ v_{2})$

Általában egy gráfszorzat értékét az (u₁, u₂) ∼ (v₁, v₂)-re vonatkozó olyan feltétel határozza meg, ami a következő kifejezések segítségével megadható: u₁ ∼ v₁, u₂ ∼ v₂, u₁ = v₁ vagy u₂ = v₂.

Mnemonik

Néhány egyszerű trükk segít megkülönböztetni a sokféle gráfszorzatot.

Jelöljük a két csúcsú teljes gráfot (ami egyetlen élből áll) $K_{2}$ -vel. Ekkor a $K_{2} ◻ K_{2}$ , $K_{2} \times K_{2}$ és $K_{2} ⊠ K_{2}$ szorzatgráfok éppen úgy néznek ki, mint az őket előállító műveleti jel. Például a $K_{2} ◻ K_{2}$ a négy csúcsból álló kör (négyzet) és $K_{2} ⊠ K_{2}$ a négy csúcsú teljes gráf. A lexikografikus szorzás jelölése – $G [H]$ – arra emlékeztet, hogy ez a szorzástípus nem kommutatív.