dbo:abstract
|
- 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 gráfművelet, amely gráfok rendezett párjaihoz egy új gráfot rendel. A G ∙ H vagy 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 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ő . A lexikografikus szorzatot elsőként Felix Hausdorff tanulmányozta. Ahogy megmutatta, annak eldöntése, hogy egy gráf lexikografikus szorzatként előáll-e, a ekvivalens. (hu)
- 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 gráfművelet, amely gráfok rendezett párjaihoz egy új gráfot rendel. A G ∙ H vagy 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 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ő . A lexikografikus szorzatot elsőként Felix Hausdorff tanulmányozta. Ahogy megmutatta, annak eldöntése, hogy egy gráf lexikografikus szorzatként előáll-e, a ekvivalens. (hu)
|