gráfok lexikografikus szorzata

Magyar

(matematika) 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) \times V(H)$ Descartes-szorzattal;
- két $G ∙ H$ -beli csúcs, $(u, v)$ és $(x, y)$ pontosan akkor szomszédosak, ha $u$ szomszédos $x$ -szel $G$ -ben vagy $u = x$ és $v$ szomszédos $y$ -nal $H$ -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.