| dbo:abstract
|
- A matematika, azon belül a gráfelmélet területén a G és H gráfok moduláris szorzata egy gráfszorzás, olyan gráfművelet, amely gráfok rendezett párjaihoz egy új gráfot rendel. G és H moduláris szorzata olyan gráf, melyre a következők igazak:
* G és H moduláris szorzatának csúcshalmaza megegyezik a V(G) × V(H) Descartes-szorzattal;
* két, a moduláris szorzatban található csúcs, (u, v) és (u' , v' ) pontosan akkor szomszédosak, ha
* u szomszédos u' -vel és v is szomszédos v' -vel, vagy
* u nem szomszédos u' -vel és v sem szomszédos v' -vel. A moduláris szorzatgráf klikkjei megfelelnek G és H feszített részgráfjai izomorfizmusainak. Ezért a moduláris szorzatgráf felhasználható egyes feszített részgráf-izomorfizmus problémáknak a gráfokban való klikkek keresésére redukálására.Konkrétabban, G és H megfelel moduláris szorzatuk maximális elemszámú klikkjének. Bár mindkét probléma , ez a redukció lehetővé teszi a alkalmazását a közös részgráf-problémára. (hu)
- A matematika, azon belül a gráfelmélet területén a G és H gráfok moduláris szorzata egy gráfszorzás, olyan gráfművelet, amely gráfok rendezett párjaihoz egy új gráfot rendel. G és H moduláris szorzata olyan gráf, melyre a következők igazak:
* G és H moduláris szorzatának csúcshalmaza megegyezik a V(G) × V(H) Descartes-szorzattal;
* két, a moduláris szorzatban található csúcs, (u, v) és (u' , v' ) pontosan akkor szomszédosak, ha
* u szomszédos u' -vel és v is szomszédos v' -vel, vagy
* u nem szomszédos u' -vel és v sem szomszédos v' -vel. A moduláris szorzatgráf klikkjei megfelelnek G és H feszített részgráfjai izomorfizmusainak. Ezért a moduláris szorzatgráf felhasználható egyes feszített részgráf-izomorfizmus problémáknak a gráfokban való klikkek keresésére redukálására.Konkrétabban, G és H megfelel moduláris szorzatuk maximális elemszámú klikkjének. Bár mindkét probléma , ez a redukció lehetővé teszi a alkalmazását a közös részgráf-problémára. (hu)
|
