Součin grafů

Součinem grafů je binární operace s grafy . Konkrétně se jedná o operaci, která mapuje dva grafy G 1 a G 2 na graf H s následujícími vlastnostmi:

Vrcholová množina grafu H je přímým součinem V ( G 1 ) × V ( G 2 ), kde V ( G 1 ) a V ( G 2 ) jsou vertexové množiny G 1 a G 2 , v tomto pořadí.
Dva vrcholy ( u 1 , u 2 ) a ( v 1 , v 2 ) grafu H jsou spojeny hranou právě tehdy , když vrcholy u 1 , u 2 , v 1 , v 2 splňují určité podmínky odpovídající součinu typu (viz níže).

Druhy děl

V následující tabulce jsou uvedeny nejběžněji používané grafické produkty. V tabulce znamená „spojeno hranou“ a znamená „nepřipojeno hranou“. Níže uvedené provozní symboly ne vždy znamenají standard, zejména v dřívějších dílech. $\sim$ $\not \sim$

název	Podmínka pro ( , ) ∼ ( , ). $u_{1}$ ${\displaystyle u_{2))$ $v_{1}$ $v_{2}$	Rozměry	Příklad
kartézský součin $G\square H$	( = a ) nebo $u_{1}$ $v_{1}$ ${\displaystyle u_{2))$ $\sim$ $v_{2}$ ( a = ) $u_{1}$ $\sim$ $v_{1}$ ${\displaystyle u_{2))$ $v_{2}$	$G_{V_{1},E_{1}}\čtverec H_{V_{2},E_{2}}\rightarrow J_{(V_{1}V_{2}),(E_{2}V_ {1}+E_{1}V_{2})}$
Produkt Tensor (kategorický produkt) $G\krát H$	$u_{1}$ $\sim$ $v_{1}$ a ${\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})}$
Lexikografické dílo popř $G\cdot H$ $G[H]$	u 1 ~ v 1 nebo ( u 1 = v 1 a 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})}$
Silný produkt (normální produkt) $G\boxtimes H$	( u 1 = v 1 a u 2 ~ v 2 ) nebo ( u 1 ~ v 1 a u 2 = v 2 ) nebo ( u 1 ~ v 1 a 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})}$
Konnormální součin grafů (Disjunktní součin) $G*H$	u 1 ∼ v 1 nebo u 2 ∼ v 2
Modulární produkt	${\displaystyle (u_{1}\sim v_{1))$ a nebo $u_{2}\sim v_{2})$ ${\displaystyle (u_{1}\ne \sim v_{1))$ a $u_{2}\ne \sim v_{2})$
kořenový produkt	viz článek	$G_{V_{1},E_{1}}\cdot H_{V_{2},E_{2}}\rightarrow J_{(V_{1}V_{2}),(E_{2}V_ {1}+E_{1})}$
Produkt Kronecker	viz článek	viz článek	viz článek
Cikcak produkt	viz článek	viz článek	viz článek
Náhradní práce
Homomorfní produkt [1] [2] [1] $G\ltimes H$	$(u_{1}=v_{1})$ nebo a ${\displaystyle (u_{1}\sim v_{1))$ $u_{2}\ne \sim v_{2})$

Obecně platí, že grafový součin je definován jakoukoli podmínkou pro ( u 1 , u 2 ) ∼ ( v 1 , v 2 ), kterou lze vyjádřit pomocí výroků u 1 ∼ v 1 , u 2 ∼ v 2 , u 1 = vi au2 = v2 . _ _ _ _

Mnemotechnická pomůcka

Nechť je úplný graf se dvěma vrcholy (tj. jednou hranou). Součin grafů , , a vypadá přesně jako znaménko operace násobení. Například je to cyklus délky 4 (čtverec) a je to úplný graf se čtyřmi vrcholy. Zápis pro lexikografický produkt připomíná skutečnost, že produkt není komutativní. $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]$

Viz také

Operace s grafy

Poznámky

↑ 1 2 David E. Roberson, Laura Mancinska. Graf homomorfismů pro kvantové hráče . — 2012.
↑ R. Bačík, S. Mahajan. Výpočetní technika a kombinatorika. - 1995. - T. 959. - S. 566, Semidefinitní programování a jeho aplikace na NP problémy. — (Poznámky z informatiky). — ISBN 3-540-60216-X . - doi : 10.1007/BFb0030878 .

Literatura

Imrich, Wilfried; Klavzar, Sandi. Produktové grafy: Struktura a rozpoznávání . - Wiley, 2000. - ISBN 0-471-37039-8 . .