Gráfok lexikografikus szorzata
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 Sablon:Math vagy lexikografikus szorzat olyan gráf, melyre a következők igazak:
- Sablon:Math csúcshalmaza megegyezik a Sablon:Math Descartes-szorzattal;
- két Sablon:Math-beli csúcs, Sablon:Math és Sablon:Math pontosan akkor szomszédosak, ha Sablon:Mvar szomszédos Sablon:Mvar-szel Sablon:Mvar-ben vagy Sablon:Math é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.
A lexikografikus szorzatot elsőként Sablon:Harvs tanulmányozta. Ahogy Sablon:Harvtxt megmutatta, annak eldöntése, hogy egy gráf lexikografikus szorzatként előáll-e, a gráfizomorfizmus-problémával ekvivalens.
Tulajdonságok
A lexikografikus szorzat általában nemkommutatív: Sablon:Math. A diszjunkt unió művelettel együtt azonban disztributívak: Sablon:Math. Ezen kívül teljesít egy a komplementerképzéssel kapcsolatos azonosságot: Sablon:Math.
A lexikografikus szorzat függetlenségi száma könnyen adódik tényezőinek függetlenségi számaiból Sablon:Harv:
A lexikografikus szorzat klikkszáma is multiplikatív:
A lexikografikus szorzat kromatikus száma megegyezik G frakcionális színezés szerinti b-szeres kromatikus számával, ahol b megegyezik H kromatikus számával:
- Sablon:Math, ahol b = χ(H).
Két gráf lexikografikus szorzata pontosan akkor perfekt gráf, ha mindkét tényező perfekt Sablon:Harv.