A grafikonok erős szorzata

A G és H gráfok erős szorzata egy olyan gráf, amelyre [1] :

• a csúcsok halmaza közvetlen szorzat
• különálló csúcsok ( u,u' ) és ( v,v' ) akkor és csak akkor kapcsolódnak éllel
  • u = v és u' szomszédos v' -vel , vagy
  • u' = v' és u szomszédos v -vel , vagy
  • u szomszédos v -vel , u' pedig v'- vel .

Az erős szorzat a közvetlen szorzat és a tenzorszorzat egyesítése .

Az erős terméket normál terméknek vagy ÉS terméknek is nevezik . A terméket először Sabidussi vezette be 1960-ban [2] . Az erős szorzat ellentétben áll a gyenge szorzattal , de a két termék csak akkor tér el, ha végtelen gráfokra alkalmazzuk.

Például a király lépéseinek gráfja , egy olyan gráf, amelyben a csúcsok a sakktábla cellái, az élek pedig a király lehetséges lépéseit jelentik, két út erős szorzata [3] .

Óvatosan kell eljárni, amikor a kifejezés megjelenik a szakirodalomban, mivel az erős szorzatot a tenzorszorzatra is használják [4] .

Lásd még

• Grafikonok szorzata
• Grafikonok közvetlen szorzata
• Gráfok tenzorszorzata

Jegyzetek

1. ↑ Imrich, Klavžar, Rall, 2008 .
2. ↑ Sabidussi, 1960 , p. 446–457.
3. ↑ Berend, Korach, Zucker, 2005 , p. 335–341.
4. ↑ Lovász, 1979 , p. 2.

Irodalom

• Wilfried Imrich, Sandi Klavžar, Douglas F. Rall. Grafikonok és derékszögű szorzatuk. - A. K. Peters, 2008. - ISBN 1-56881-429-1 .
• Sabidussi, G. Grafikon szorzás // Math. Z .. - 1960. - T. 72 . – S. 446–457 . - doi : 10.1007/BF01162967 .
• Daniel Berend, Ephraim Korach, Shira Zucker. Síkbeli és kapcsolódó gráfok két-ellenszínezése // 2005 International Conference on Analysis of Algorithms. - Nancy: Association for Discrete Mathematics & Theoretical Computer Science, 2005. - P. 335–341. — (Diszkrét matematikai és elméleti számítástechnikai közlemények).
• Lovasz László. Egy gráf Shannon-kapacitásáról // IEEE Transactions on Information Theory. - 1979. - T. IT-25 , sz. 1 . - doi : 10.1109/TIT.1979.1055985 .