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 $\not \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{array}{cc}n_{1}=\vert \mathrm {V} (G)\vert &n_{2}=\vert \mathrm {V} (H)\vert \\m_{1}=\vert \mathrm {E} (G)\vert &m_{2}=\vert \mathrm {E} (H)\vert \end{array}}$	Példa
Descartes-szorzat $G\square 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}$	$2m_{1}m_{2}$
Lexikografikus szorzat $G\cdot H$ vagy $G[H]$	u1 ∼ v1 vagy ( u1 = v1 és u2 ∼ v2 )	$m_{2}n_{1}+m_{1}n_{2}^{2}$
Erős szorzat (Normál szorzat, ÉS szorzat) $G\boxtimes H$	( u1 = v1 és u2 ∼ v2 ) vagy ( u1 ∼ v1 és u2 = v2 ) vagy ( u1 ∼ v1 és u2 ∼ v2 )	$n_{1}m_{2}+n_{2}m_{1}+2m_{1}m_{2}$
Ko-normális szorzat (diszjunktív szorzat, VAGY szorzat) $G*H$	u1 ∼ v1 vagy u2 ∼ v2
Moduláris szorzat	$(u_{1}\sim v_{1}$ és $u_{2}\sim v_{2})$ vagy $(u_{1}\not \sim v_{1}$ és $u_{2}\not \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 $G\ltimes H$	$(u_{1}=v_{1})$ vagy $(u_{1}\sim v_{1}$ és $u_{2}\not \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}\square K_{2}$, $K_{2}\times K_{2}$ és $K_{2}\boxtimes K_{2}$ szorzatgráfok éppen úgy néznek ki, mint az őket előállító műveleti jel. Például a $K_{2}\square K_{2}$ a négy csúcsból álló kör (négyzet) és $K_{2}\boxtimes 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.

Kapcsolódó szócikkek

• Gráfművelet

Jegyzetek

• Product Graphs: Structure and Recognition. Wiley (2000). ISBN 0-471-37039-8 .