Grafikonok szorzata

A gráfok szorzata egy bináris művelet gráfokon . Pontosabban, ez egy olyan művelet, amely két G 1 és G 2 gráfot képez le egy H gráfra a következő tulajdonságokkal:

A H gráf csúcskészlete a V ( G 1 ) × V ( G 2 ) közvetlen szorzata , ahol V ( G 1 ) és V ( G 2 ) a G 1 és G 2 csúcshalmaza .
A H gráf két csúcsát ( u 1 , u 2 ) és ( v 1 , v 2 ) akkor és csak akkor kapcsoljuk össze éllel , ha az u 1 , u 2 , v 1 , v 2 csúcsok bizonyos, a szorzatnak megfelelő feltételeket teljesítenek. típus (lásd lent) .

Művek típusai

Az alábbi táblázat a leggyakrabban használt grafikontermékeket mutatja be. A táblázatban azt jelenti, hogy "éllel összekötve", és azt jelenti, hogy "nem éllel összekötve". Az alább megadott műveleti szimbólumok nem mindig jelentik a szabványt, különösen a korábbi munkákban. $\sim$ ${\megjelenítési stílus \nem \sim }$

Név	( , ) ∼ ( , ) feltétele. $u_{1}$ ${\displaystyle u_{2))$ $v_{1}$ $v_{2}$	Méretek	Példa
Descartes termék $G\square H$	( = és ) vagy $u_{1}$ $v_{1}$ ${\displaystyle u_{2))$ $\sim$ $v_{2}$ ( és = ) $u_{1}$ $\sim$ $v_{1}$ ${\displaystyle u_{2))$ $v_{2}$	$G_{V_{1},E_{1}}\square H_{V_{2},E_{2}}\jobbra nyíl J_{(V_{1}V_{2}),(E_{2}V_ {1}+E_{1}V_{2})}$
Tensor termék (kategóriatermék) $G\time H$	$u_{1}$ $\sim$ $v_{1}$ és ${\displaystyle u_{2))$ $\sim$ $v_{2}$	$G_{V_{1},E_{1}}\times H_{V_{2},E_{2}}\jobbra nyíl J_{(V_{1}V_{2}),(2E_{1}E_ {2})}$
Lexikográfiai munka ill $G\cdot H$ $G[H]$	u 1 ∼ v 1 vagy ( u 1 = v 1 és u 2 ∼ 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}V_{2}^{2})}$
Erős termék (normál termék) $G\boxtimes H$	( u 1 = v 1 és u 2 ∼ v 2 ) vagy ( u 1 ~ v 1 és u 2 = v 2 ) vagy ( u 1 ~ v 1 és u 2 ~ v 2 )	$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})}$
Grafikonok konnormális szorzata (Disjunkt szorzat) $G*H$	u 1 ∼ v 1 vagy u 2 ∼ v 2
Moduláris termék	${\displaystyle (u_{1}\sim v_{1))$ és vagy $u_{2}\sim v_{2})$ ${\displaystyle (u_{1}\not \sim v_{1))$ és $u_{2}\not \sim v_{2})$
gyökértermék	lásd a cikket	$G_{V_{1},E_{1}}\cdot H_{V_{2},E_{2}}\rightarrow J_{(V_{1}V_{2}),(E_{2}V_ {1}+E_{1})}$
Kronecker termék	lásd a cikket	lásd a cikket	lásd a cikket
Cikcakkos termék	lásd a cikket	lásd a cikket	lásd a cikket
Csere munka
Homomorf termék [1] [2] [1] $G\ltimes H$	$(u_{1}=v_{1})$ vagy és ${\displaystyle (u_{1}\sim v_{1))$ $u_{2}\not \sim v_{2})$

Általában egy gráfszorzatot az ( u 1 , u 2 ) ∼ ( v 1 , v 2 ) tetszőleges feltétele határoz meg, amely az u 1 ∼ v 1 , u 2 ∼ v 2 , u 1 állításokkal fejezhető ki. = v 1 és u 2 = v 2 .

Mnemonikus

Legyen egy teljes gráf két csúcsgal (azaz egyetlen éllel). A , és a grafikonok szorzatai pontosan úgy néznek ki, mint a szorzási művelet előjele. Például egy 4 (négyzet) hosszúságú ciklus, és egy teljes gráf négy csúcstal. A lexikográfiai termék jelölése arra emlékeztet, hogy a termék nem kommutatív. $K_{2}$ $K_{2}\square K_{2}$ ${\displaystyle K_{2}\times K_{2))$ ${\displaystyle K_{2}\boxtimes K_{2))$ $K_{2}\square K_{2}$ ${\displaystyle K_{2}\boxtimes K_{2))$ $G[H]$

Lásd még

Műveletek grafikonokon

Jegyzetek

↑ 1 2 David E. Roberson, Laura Mancinska. Homomorfizmusok grafikonja kvantumlejátszókhoz . — 2012.
↑ R. Bačík, S. Mahajan. Számítástechnika és kombinatorika. - 1995. - T. 959. - P. 566, Félig meghatározott programozás és alkalmazásai NP problémákra. — (Számítástechnikai előadásjegyzetek). — ISBN 3-540-60216-X . - doi : 10.1007/BFb0030878 .

Irodalom

Imrich, Wilfried; Klavzar, Szandi. Termékgrafikonok: Struktúra és felismerés . - Wiley, 2000. - ISBN 0-471-37039-8 . .