Gráfok lexikografikus szorzata

1. Sablon:Humatek A matematika, azon belül a gráfelmélet területén a G és H gráfok lexikografikus szorzata vagy gráfkompozíció 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 vagy $G[H]$ lexikografikus szorzat olyan gráf, melyre a következők igazak:
   • G ∙ H csúcshalmaza megegyezik a V(G) × V(H) Descartes-szorzattal;
   • két G ∙ H -beli csúcs, (u,v) és (x,y) pontosan akkor szomszédosak, ha Sablon:Mvar szomszédos Sablon:Mvar-szel Sablon:Mvar-ben vagy 1=u = x és Sablon:Mvar szomszédos Sablon:Mvar-nal Sablon:Mvar-ban.

Ha a két gráf élrelációi rendezési relációk, akkor lexikografikus szorzatuk élrelációja éppen a megfelelő lexikografikus rendezés.

• Sablon:En: Sablon:T