| dbo:abstract
|
- A matematika, azon belül a gráfelmélet területén a G és H gráfok Descartes-szorzata egy gráfszorzás, olyan gráfművelet, amely gráfok rendezett párjaihoz egy új gráfot rendel. A G H Descartes-szorzat olyan gráf, melyre a következők igazak:
* G H csúcshalmaza megegyezik a V(G) × V(H) Descartes-szorzattal;
* A G H két csúcsa, (u,u' ) és (v,v' ) pontosan akkor szomszédos egymással, ha az alábbi két feltétel bármelyike teljesül:
* u = v és u' szomszédos v' -vel H-ban vagy
* u' = v' és u szomszédos v-vel G-ben. A Descartes-szorzatként előálló gráfok hatékonyan, felismerhetők. A gráfok izomorfizmus ekvivalenciaosztályain értelmezett művelet kommutatív, ráadásul G H és H G , címkézett gráfokon végzett műveletként azonban nem kommutatív. A művelet asszociatív is, hiszen az (F G) H és F (G H) gráfok természetesen izomorfak. Néha a G × H jelölést is használják a gráfok Descartes-szorzatára, de ez a jelölés általában inkább a gráfok tenzorszorzatára utal. A négyzet szimbólum gyakoribb és egyértelműbb jelölése a Descartes-szorzatnak, mivel vizuálisan is jelzi a két él Descartes-szorzatául eredményül kapott négy élt. (hu)
- A matematika, azon belül a gráfelmélet területén a G és H gráfok Descartes-szorzata egy gráfszorzás, olyan gráfművelet, amely gráfok rendezett párjaihoz egy új gráfot rendel. A G H Descartes-szorzat olyan gráf, melyre a következők igazak:
* G H csúcshalmaza megegyezik a V(G) × V(H) Descartes-szorzattal;
* A G H két csúcsa, (u,u' ) és (v,v' ) pontosan akkor szomszédos egymással, ha az alábbi két feltétel bármelyike teljesül:
* u = v és u' szomszédos v' -vel H-ban vagy
* u' = v' és u szomszédos v-vel G-ben. A Descartes-szorzatként előálló gráfok hatékonyan, felismerhetők. A gráfok izomorfizmus ekvivalenciaosztályain értelmezett művelet kommutatív, ráadásul G H és H G , címkézett gráfokon végzett műveletként azonban nem kommutatív. A művelet asszociatív is, hiszen az (F G) H és F (G H) gráfok természetesen izomorfak. Néha a G × H jelölést is használják a gráfok Descartes-szorzatára, de ez a jelölés általában inkább a gráfok tenzorszorzatára utal. A négyzet szimbólum gyakoribb és egyértelműbb jelölése a Descartes-szorzatnak, mivel vizuálisan is jelzi a két él Descartes-szorzatául eredményül kapott négy élt. (hu)
|
