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 (u1, u2) és (v1, v2) 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
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.
Általában egy gráfszorzat értékét az (u1, u2) ∼ (v1, v2)-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
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
Jegyzetek
- ↑ 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.
- ↑ 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
- ↑ The hom-product of[2] is the graph complement of the homomorphic product of.[1]