Produkt af grafer

Produktet af grafer er en binær operation på grafer . Mere specifikt er det en operation, der kortlægger to grafer G 1 og G 2 til en graf H med følgende egenskaber:

Toppunktet af grafen H er det direkte produkt V ( G 1 ) × V ( G 2 ), hvor V ( G 1 ) og V ( G 2 ) er toppunkterne af henholdsvis G 1 og G 2 .
To toppunkter ( u 1 , u 2 ) og ( v 1 , v 2 ) af grafen H er forbundet med en kant hvis og kun hvis toppunkterne u 1 , u 2 , v 1 , v 2 opfylder visse betingelser svarende til produktet type (se nedenfor).

Typer af værker

Følgende tabel viser de mest brugte grafprodukter. I tabellen betyder "forbundet af en kant" og betyder "ikke forbundet med en kant". Betjeningssymbolerne nedenfor betyder ikke altid standarden, især i tidligere værker. $\sim$ $\not \sim$

Navn	Betingelse for ( , ) ~ ( , ). $u_{1}$ ${\displaystyle u_{2))$ $v_{1}$ $v_{2}$	Dimensioner	Eksempel
Kartesisk produkt $G\square H$	( = og ) eller $u_{1}$ $v_{1}$ ${\displaystyle u_{2))$ $\sim$ $v_{2}$ ( og = ) $u_{1}$ $\sim$ $v_{1}$ ${\displaystyle u_{2))$ $v_{2}$	$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})}$
Tensor-produkt (kategorisk produkt) $G\ gange H$	$u_{1}$ $\sim$ $v_{1}$ og ${\displaystyle u_{2))$ $\sim$ $v_{2}$	$G_{V_{1},E_{1}}\ gange H_{V_{2},E_{2}}\højrepil J_{(V_{1}V_{2}),(2E_{1}E_ {2})}$
Leksikografisk arbejde el $G\cdot H$ $G[H]$	u 1 ∼ v 1 eller ( u 1 = v 1 og u 2 ∼ v 2 )	$G_{V_{1},E_{1}}\cdot H_{V_{2},E_{2}}\højrepil J_{(V_{1}V_{2}),(E_{2}V_ {1}+E_{1}V_{2}^{2})}$
Stærkt produkt (normalt produkt) $G\boxtimes H$	( u 1 = v 1 og u 2 ∼ v 2 ) eller ( u 1 ∼ v 1 og u 2 = v 2 ) eller ( u 1 ∼ v 1 og u 2 ∼ v 2 )	$G_{V_{1},E_{1}}\boxtimes H_{V_{2},E_{2}}\højrepil J_{(V_{1}V_{2}),(V_{1}E_ {2}+V_{2}E_{1}+2E_{1}E_{2})}$
Konormalt produkt af grafer (Disjunkt produkt) $G*H$	u 1 ∼ v 1 eller u 2 ∼ v 2
Modulært produkt	${\displaystyle (u_{1}\sim v_{1))$ og eller $u_{2}\sim v_{2})$ ${\displaystyle (u_{1}\ikke \sim v_{1))$ og $u_{2}\ikke \sim v_{2})$
rodprodukt	se artiklen	$G_{V_{1},E_{1}}\cdot H_{V_{2},E_{2}}\højrepil J_{(V_{1}V_{2}),(E_{2}V_ {1}+E_{1})}$
Kronecker produkt	se artiklen	se artiklen	se artiklen
Zigzag produkt	se artiklen	se artiklen	se artiklen
Udskiftningsarbejde
Homomorft produkt [1] [2] [1] $G\ltimes H$	$(u_{1}=v_{1})$ eller og ${\displaystyle (u_{1}\sim v_{1))$ $u_{2}\ikke \sim v_{2})$

Generelt er et grafprodukt defineret ved en hvilken som helst betingelse for ( u 1 , u 2 ) ∼ ( v 1 , v 2 ), der kan udtrykkes i form af udsagn u 1 ∼ v 1 , u 2 ∼ v 2 , u 1 = v 1 og u 2 = v 2 .

Mnemonic

Lad være en komplet graf med to spidser (det vil sige en enkelt kant). Produkterne af graferne , , og ligner nøjagtigt tegnet på multiplikationsoperationen. For eksempel er en cyklus med længde 4 (kvadratisk), og er en komplet graf med fire hjørner. Notationen for det leksikografiske produkt minder om, at produktet ikke er kommutativt. $K_{2}$ $K_{2}\square K_{2}$ ${\displaystyle K_{2}\ gange K_{2))$ ${\displaystyle K_{2}\boxtimes K_{2))$ $K_{2}\square K_{2}$ ${\displaystyle K_{2}\boxtimes K_{2))$ $G[H]$

Se også

Operationer på grafer

Noter

↑ 1 2 David E. Roberson, Laura Mancinska. Grafhomomorfismer for kvantespillere . – 2012.
↑ R. Bačík, S. Mahajan. Computing og kombinatorik. - 1995. - T. 959. - P. 566, Semidefinite programmering og dens anvendelser på NP-problemer. — (Forelæsningsnotater i datalogi). — ISBN 3-540-60216-X . - doi : 10.1007/BFb0030878 .

Litteratur

Imrich, Wilfried; Klavzar, Sandi. Produktgrafer: Struktur og anerkendelse . - Wiley, 2000. - ISBN 0-471-37039-8 . .