Gráfok erős szorzata
A matematika, azon belül a gráfelmélet területén a G és H gráfok erős szorzata egy gráfszorzás, olyan kétváltozós gráfművelet, amely gráfok rendezett párjaihoz egy új gráfot rendel. A G ⊠ H erős szorzat olyan gráf, melyre a következők igazak:[1]
- G × H csúcshalmaza megegyezik a V(G) × V(H) Descartes-szorzattal;
- két G × H-beli csúcs, (u,u') és (v,v') pontosan akkor szomszédosak, ha
- u = v és u' szomszédos v' -vel vagy
- u' = v' és u szomszédos v-vel vagy
- u szomszédos v-vel és u' szomszédos v' -vel
Az erős szorzatot Sabidussi vezette be 1960-ban.[2] Cikkében a szorzat „erőssége” egy gyenge szorzattípussal volt szembeállítva, de a kétfajta szorzat különbsége csak végtelen sok szorzótényező esetén jelentkezett. A művelet jelének kereszt szimbóluma vizuálisan a két él erős szorzatából adódó élekre emlékeztet.
Például a sakktáblán a király lehetséges lépéseit megjelenítő királygráf két útgráf erős szorzataként áll elő.[3]
Az irodalomban óvatosan kezelendők az „erős szorzatra” (strong product) való hivatkozások, mivel időnként[4] a gráfok tenzorszorzatát értik alatta.
Fordítás
[szerkesztés]- Ez a szócikk részben vagy egészben a Strong product of graphs című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
Jegyzetek
[szerkesztés]- ↑ Imrich, Wilfried; Klavžar, Sandi & Rall, Douglas F. (2008), Graphs and their Cartesian Product, A. K. Peters, ISBN 1-56881-429-1.
- ↑ Sabidussi, G. (1960). „Graph multiplication”. Math. Z. 72, 446–457. o. DOI:10.1007/BF01162967.
- ↑ Berend, Daniel; Korach, Ephraim & Zucker, Shira (2005), "Two-anticoloring of planar and related graphs", 2005 International Conference on Analysis of Algorithms, Discrete Mathematics & Theoretical Computer Science Proceedings, Nancy: Association for Discrete Mathematics & Theoretical Computer Science, pp. 335–341.
- ↑ See page 2 of Lovász, László (1979), "On the Shannon Capacity of a Graph", IEEE Transactions on Information Theory IT-25 (1), DOI 10.1109/TIT.1979.1055985.