Grafový produkt - Graph product

v matematika, a grafový produkt je binární operace na grafy. Konkrétně se jedná o operaci, která trvá dva grafy G₁ a G₂ a vytvoří graf H s následujícími vlastnostmi:

The sada vrcholů z H je kartézský součin PROTI(G₁) × PROTI(G₂), kde PROTI(G₁) a PROTI(G₂) jsou vrcholové množiny G₁ a G₂, resp.
Dva vrcholy (A₁, A₂) a (b₁, b₂) z H jsou spojeny pomocí okraj, iff podmínka o A₁, b₁ v G₁ a A₂, b₂ v G₂ je splněn.

Grafové produkty se liší v tom, co přesně je tato podmínka. Vždy jde o to, zda vrcholy či nikoli A_n, b_n v G_n jsou stejné nebo spojené hranou.

Terminologie a notace pro konkrétní grafové produkty v literatuře se velmi liší; i když lze následující považovat za poněkud standardní, čtenářům se doporučuje zkontrolovat, jakou definici konkrétní autor používá pro grafický produkt, zejména ve starších textech.

Přehledová tabulka

Následující tabulka ukazuje nejběžnější produkty grafů s ${displaystyle sim}$ označení „je spojeno hranou s“ a ${displaystyle ot sim}$ označující nepřipojení. Zde uvedené symboly operátorů nejsou v žádném případě standardní, zejména ve starších dokumentech.

název	Podmínka pro ${displaystyle (a_ {1}, a_ {2}) sim (b_ {1}, b_ {2})}$		Počet hran ${displaystyle {egin {array} {cc} v_ {1} = vert mathrm {V} (G_ {1}) vert & v_ {2} = vert mathrm {V} (G_ {2}) vert e_ {1} = vert mathrm {E} (G_ {1}) vert & e_ {2} = vert mathrm {E} (G_ {2}) vert end {pole}}}$	Příklad
název		s ${displaystyle a_ {n} ~ {ext {rel}} ~ b_ {n}}$ zkráceně jako ${displaystyle {ext {rel}} _ {n}}$		Příklad
kartézský součin ${displaystyle G_ {1} čtverec G_ {2}}$	${displaystyle a_ {1} = b_ {1} ~ země ~ a_ {2} sim b_ {2}}$ ${displaystyle lor}$ ${displaystyle a_ {1} sim b_ {1} ~ land ~ a_ {2} = b_ {2}}$	${displaystyle = _ {1} ~ sim _ {2}}$ ${displaystyle lor}$ ${displaystyle sim _ {1} ~ = _ {2}}$	${displaystyle v_ {1} ~ e_ {2} ~ + ~ e_ {1} ~ v_ {2}}$
Tenzorový produkt (Produkt Kronecker, kategorický produkt) ${displaystyle G_ {1} je G_ {2}}$	${displaystyle a_ {1} sim b_ {1} ~ land ~ a_ {2} sim b_ {2}}$	${displaystyle sim _ {1} ~ sim _ {2}}$	${displaystyle 2 ~ e_ {1} ~ e_ {2}}$
Lexikografický produkt ${displaystyle G_ {1} cdot G_ {2}}$ nebo ${displaystyle G_ {1} [G_ {2}]}$	${displaystyle a_ {1} sim b_ {1}}$ ${displaystyle lor}$ ${displaystyle a_ {1} = b_ {1} ~ země ~ a_ {2} sim b_ {2}}$	${displaystyle sim _ {1}}$ ${displaystyle lor}$ ${displaystyle = _ {1} ~ sim _ {2}}$	${displaystyle v_ {1} ~ e_ {2} ~ + ~ e_ {1} ~ v_ {2} ^ {2}}$
Silný produkt (Normální produkt, Produkt AND) ${displaystyle G_ {1} vícekrát G_ {2}}$	${displaystyle a_ {1} = b_ {1} ~ země ~ a_ {2} sim b_ {2}}$ ${displaystyle lor}$ ${displaystyle a_ {1} sim b_ {1} ~ land ~ a_ {2} = b_ {2}}$ ${displaystyle lor}$ ${displaystyle a_ {1} sim b_ {1} ~ land ~ a_ {2} sim b_ {2}}$	${displaystyle = _ {1} ~ sim _ {2}}$ ${displaystyle lor}$ ${displaystyle sim _ {1} ~ = _ {2}}$ ${displaystyle lor}$ ${displaystyle sim _ {1} ~ sim _ {2}}$	${displaystyle v_ {1} ~ e_ {2} ~ + ~ e_ {1} ~ v_ {2} ~ + ~ 2 ~ e_ {1} ~ e_ {2}}$
Společný produkt (disjunktivní produkt NEBO produkt) ${displaystyle G_ {1} * G_ {2}}$	${displaystyle a_ {1} sim b_ {1}}$ ${displaystyle lor}$ ${displaystyle a_ {2} sim b_ {2}}$	${displaystyle sim _ {1}}$ ${displaystyle lor}$ ${displaystyle sim _ {2}}$	${displaystyle v_ {1} ^ {2} ~ e_ {2} ~ + ~ e_ {1} ~ v_ {2} ^ {2} ~ - ~ 2 ~ e_ {1} ~ e_ {2}}$
Modulární produkt	${displaystyle a_ {1} sim b_ {1} ~ land ~ a_ {2} sim b_ {2}}$ ${displaystyle lor}$ ${displaystyle a_ {1} ot sim b_ {1} ~ land ~ a_ {2} ot sim b_ {2}}$	${displaystyle sim _ {1} ~ sim _ {2}}$ ${displaystyle lor}$ ${displaystyle ot sim _ {1} ~ ot sim _ {2}}$
Kořenový produkt	viz článek		${displaystyle v_ {1} ~ e_ {2} ~ + ~ e_ {1}}$
Cik-cak produkt	viz článek		viz článek	viz článek
Náhradní produkt
Homomorfní produkt^[1]^[3] ${displaystyle G_ {1} ltimes G_ {2}}$	${displaystyle a_ {1} = b_ {1}}$ ${displaystyle lor}$ ${displaystyle a_ {1} sim b_ {1} ~ land ~ a_ {2} ot sim b_ {2}}$	${displaystyle = _ {1}}$ ${displaystyle lor}$ ${displaystyle sim _ {1} ~ ot sim _ {2}}$

Obecně platí, že grafový produkt je určen jakoukoli podmínkou pro ${displaystyle (a_ {1}, a_ {2}) sim (b_ {1}, b_ {2})}$ které lze vyjádřit pomocí ${displaystyle a_ {n} = b_ {n}}$ a ${displaystyle a_ {n} sim b_ {n}}$ .

Mnemotechnická pomůcka

Nechat ${displaystyle K_ {2}}$ být úplným grafem na dvou vrcholech (tj. na jedné hraně). Produktové grafy ${displaystyle K_ {2} čtverec K_ {2}}$ , ${displaystyle K_ {2} je K_ {2}}$ , a ${displaystyle K_ {2} vícekrát K_ {2}}$ vypadat přesně jako graf představující operátora. Například, ${displaystyle K_ {2} čtverec K_ {2}}$ je čtyři cyklus (čtverec) a ${displaystyle K_ {2} vícekrát K_ {2}}$ je kompletní graf na čtyřech vrcholech. The ${displaystyle G_ {1} [G_ {2}]}$ notace pro lexikografický produkt slouží jako připomínka, že tento produkt není komutativní.

Viz také

Grafické operace

Poznámky

^ ^A ^b Roberson, David E .; Mancinska, Laura (2012). "Graf homomorfismů pro kvantové hráče". Journal of Combinatorial Theory, Series B. 118: 228–267. arXiv:1212.1724. doi:10.1016 / j.jctb.2015.12.009.
^ Bačík, R .; Mahajan, S. (1995). "Semidefinitní programování a jeho aplikace na problémy NP". Výpočetní technika a kombinatorika. Přednášky z informatiky. 959. p. 566. doi:10.1007 / BFb0030878. ISBN 978-3-540-60216-3.
^ Hom-produkt z ^[2] je grafickým doplňkem homomorfního součinu.^[1]

Reference

Imrich, Wilfried; Klavžar, Sandi (2000). Grafy produktů: Struktura a rozpoznávání. Wiley. ISBN 978-0-471-37039-0 {{nekonzistentní citace}}CS1 maint: ref = harv (odkaz).

[rm12-1] A ^b Roberson, David E .; Mancinska, Laura (2012). "Graf homomorfismů pro kvantové hráče". Journal of Combinatorial Theory, Series B. 118: 228–267. arXiv:1212.1724. doi:10.1016 / j.jctb.2015.12.009.

[2] Bačík, R .; Mahajan, S. (1995). "Semidefinitní programování a jeho aplikace na problémy NP". Výpočetní technika a kombinatorika. Přednášky z informatiky. 959. p. 566. doi:10.1007 / BFb0030878. ISBN 978-3-540-60216-3.

[3] Hom-produkt z ^[2] je grafickým doplňkem homomorfního součinu.^[1]

[1]

[3]

[2]