Gráfszorzás

A Wikipédiából, a szabad enciklopédiából
Jump to navigation Jump to search

A matematika, azon belül a gráfelmélet területén a gráfszorzás olyan kétváltozós gráfművelet, amely gráfok rendezett párjaihoz egy új gráfot rendel. Specifikusan: a két bemeneti gráf, G1 és G2 alapján kimenetként a következő tulajdonságokkal rendelkező H-t adja:

  • H csúcshalmaza a V(G1) × V(G2) Descartes-szorzat, ahol V(G1) és V(G2) a G1, illetve a G2 csúcshalmazai.
  • Két H-beli csúcs (u1u2) és (v1v2) pontosan akkor szomszédosak, ha az u1, u2, v1, v2 csúcsokra teljesül valamely G1 és G2 éleire vonatkozó feltétel. A gráfszorzatok különböző fajtái éppen ebben a feltételben térnek el.

A különböző gráfszorzatok leírása és jelölése az irodalomban erősen változó lehet; bár az alább alkalmazott jelölések elég elterjedtek, érdemes egy-egy cikk olvasásakor ellenőrizni, hogy az adott szerző egy gráfszorzat mely definícióját használja, főleg régebbi szövegekben.

Áttekintő táblázat[szerkesztés]

A következő táblázat felsorolja az elterjedtebb gráfszorzatokat. A ; jelentése „a két csúcs össze van kötve”, míg a az össze nem kötöttséget jelöli. A táblázatban alkalmazott szimbólumok nem tekinthetők univerzálisan elfogadottnak, különösen a régi cikkekben találhatók egyedi jelölések.

Név feltétele Méret (élek száma)
Példa
Descartes-szorzat
 =  és    )
vagy

   és  =  )

Graph-Cartesian-product.svg
Tenzorszorzat
(kategóriaszorzat)
   és     Graph-tensor-product.svg
Lexikografikus szorzat
vagy
u1 ∼ v1
vagy
u1 = v1 és u2 ∼ v2 )
Graph-lexicographic-product.svg
Erős szorzat
(Normál szorzat, ÉS szorzat)
u1 = v1 és u2 ∼ v2 )
vagy
u1 ∼ v1 és u2 = v2 )
vagy
u1 ∼ v1 és u2 ∼ v2 )
Ko-normális szorzat
(diszjunktív szorzat, VAGY szorzat)
u1 ∼ v1
vagy
u2 ∼ v2
Moduláris szorzat és
vagy

és

Modular product.png
Gyökeres szorzat Lásd a szócikket Graph-rooted-product.svg
Cikkcakkszorzat Lásd a szócikket Lásd a szócikket Lásd a szócikket
Replacement szorzat
Homomorf szorzat[1][3]

vagy
és

Általában egy gráfszorzat értékét az (u1u2) ∼ (v1v2)-re vonatkozó olyan feltétel határozza meg, ami a következő kifejezések segítségével megadható: u1 ∼ v1, u2 ∼ v2, u1 = v1 vagy u2 = v2.

Mnemonik[szerkesztés]

Néhány egyszerű trükk segít megkülönböztetni a sokféle gráfszorzatot.

Jelöljük a két csúcsú teljes gráfot (ami egyetlen élből áll) -vel. Ekkor a , és szorzatgráfok éppen úgy néznek ki, mint az őket előállító műveleti jel. Például a a négy csúcsból álló kör (négyzet) és a négy csúcsú teljes gráf. A lexikografikus szorzás jelölése – – arra emlékeztet, hogy ez a szorzástípus nem kommutatív.

Kapcsolódó szócikkek[szerkesztés]

Jegyzetek[szerkesztés]

  1. ^ a b (2012) „Graph Homomorphisms for Quantum Players”. Journal of Combinatorial Theory, Series B 118, 228–267. o. DOI:10.1016/j.jctb.2015.12.009.  
  2. Semidefinite programming and its applications to NP problems, Computing and Combinatorics, Lecture Notes in Computer Science, 566. o.. DOI: 10.1007/BFb0030878 (1995). ISBN 3-540-60216-X 
  3. The hom-product of [2] is the graph complement of the homomorphic product of.[1]