Produkt av grafer

Produkten av grafer är en binär operation på grafer . Mer specifikt är det en operation som mappar två grafer G 1 och G 2 till en graf H med följande egenskaper:

Hönsmängden för grafen H är den direkta produkten V ( G 1 ) × V ( G 2 ), där V ( G 1 ) och V ( G 2 ) är vertexuppsättningarna av G 1 respektive G 2 .
Två hörn ( u 1 , u 2 ) och ( v 1 , v 2 ) i grafen H är förbundna med en kant om och endast om hörnen u 1 , u 2 , v 1 , v 2 uppfyller vissa villkor som motsvarar produkten typ (se nedan).

Typer av verk

Följande tabell visar de mest använda grafprodukterna. I tabellen betyder "ansluten av en kant" och betyder "ej förbunden med en kant". Funktionssymbolerna nedan betyder inte alltid standarden, särskilt i tidigare verk. $\sim$ $\not \sim$

namn	Villkor för ( , ) ~ ( , ). $u_{1}$ ${\displaystyle u_{2))$ $v_{1}$ $v_{2}$	Mått	Exempel
kartesisk produkt $G\square H$	( = och ) eller $u_{1}$ $v_{1}$ ${\displaystyle u_{2))$ $\sim$ $v_{2}$ ( och = ) $u_{1}$ $\sim$ $v_{1}$ ${\displaystyle u_{2))$ $v_{2}$	$G_{V_{1},E_{1}}\square H_{V_{2},E_{2}}\högerpil J_{(V_{1}V_{2}),(E_{2}V_ {1}+E_{1}V_{2})}$
Tensorprodukt (kategorisk produkt) $G\ gånger H$	$u_{1}$ $\sim$ $v_{1}$ och ${\displaystyle u_{2))$ $\sim$ $v_{2}$	$G_{V_{1},E_{1}}\times H_{V_{2},E_{2}}\rightarrow J_{(V_{1}V_{2}),(2E_{1}E_ {2})}$
Lexikografiskt arbete eller $G\cdot H$ $G[H]$	u 1 ∼ v 1 eller ( u 1 = v 1 och u 2 ∼ v 2 )	$G_{V_{1},E_{1}}\cdot H_{V_{2},E_{2}}\högerpil J_{(V_{1}V_{2}),(E_{2}V_ {1}+E_{1}V_{2}^{2})}$
Stark produkt (normal produkt) $G\boxtimes H$	( u 1 = v 1 och u 2 ∼ v 2 ) eller ( u 1 ∼ v 1 och u 2 = v 2 ) eller ( u 1 ∼ v 1 och u 2 ∼ v 2 )	$G_{V_{1},E_{1}}\boxtimes H_{V_{2},E_{2}}\högerpil J_{(V_{1}V_{2}),(V_{1}E_ {2}+V_{2}E_{1}+2E_{1}E_{2})}$
Konormal produkt av grafer (Disjunkt produkt) $G*H$	u 1 ∼ v 1 eller u 2 ∼ v 2
Modulär produkt	${\displaystyle (u_{1}\sim v_{1))$ och eller $u_{2}\sim v_{2})$ ${\displaystyle (u_{1}\not \sim v_{1))$ och $u_{2}\not \sim v_{2})$
rotprodukt	se artikeln	$G_{V_{1},E_{1}}\cdot H_{V_{2},E_{2}}\högerpil J_{(V_{1}V_{2}),(E_{2}V_ {1}+E_{1})}$
Kronecker produkt	se artikeln	se artikeln	se artikeln
Sicksack produkt	se artikeln	se artikeln	se artikeln
Ersättningsarbete
Homomorf produkt [1] [2] [1] $G\ltimes H$	$(u_{1}=v_{1})$ eller och ${\displaystyle (u_{1}\sim v_{1))$ $u_{2}\not \sim v_{2})$

I allmänhet definieras en grafprodukt av vilket villkor som helst för ( u 1 , u 2 ) ∼ ( v 1 , v 2 ) som kan uttryckas i termer av påståendena u 1 ∼ v 1 , u 2 ∼ v 2 , u 1 = v 1 och u 2 = v 2 .

Mnemonic

Låta vara en komplett graf med två hörn (det vill säga en enda kant). Produkterna av graferna , , och ser exakt ut som tecknet på multiplikationsoperationen. Till exempel är en cykel med längden 4 (kvadrat) och är en komplett graf med fyra hörn. Notationen för den lexikografiska produkten påminner om att produkten inte är kommutativ. $K_{2}$ $K_{2}\square K_{2}$ ${\displaystyle K_{2}\ gånger K_{2))$ ${\displaystyle K_{2}\boxtimes K_{2))$ $K_{2}\square K_{2}$ ${\displaystyle K_{2}\boxtimes K_{2))$ $G[H]$

Se även

Operationer på grafer

Anteckningar

↑ 1 2 David E. Roberson, Laura Mancinska. Grafhomomorfismer för kvantspelare . — 2012.
↑ R. Bačík, S. Mahajan. Beräkning och kombinatorik. - 1995. - T. 959. - P. 566, Semidefinite programmering och dess tillämpningar på NP-problem. — (Föreläsningsanteckningar i datavetenskap). — ISBN 3-540-60216-X . - doi : 10.1007/BFb0030878 .

Litteratur

Imrich, Wilfried; Klavzar, Sandi. Produktdiagram: struktur och igenkänning . - Wiley, 2000. - ISBN 0-471-37039-8 . .