| dbo:abstract
|
- A matematika, azon belül a gráfelmélet területén egy gráf klikkszélessége (clique-width) a gráf szerkezetének bonyolultságát leíró paraméter; közeli rokona a faszélességnek, de attól eltérő módon, sűrű gráfokon is korlátos lehet az értéke.A definíció szerint értéke megegyezik a gráf konstruálásához szükséges címkék minimális számával, ha a következő négy művelet engedélyezett: 1.
* Felveszünk egy új csúcsot, v-t és i címkével látjuk el (jelölés: i(v) vagy ) 2.
* Két címkézett gráf, G és H diszjunkt unióját képezzük (jelölés: ) 3.
* Minden i-vel jelölt csúcsot összekötünk minden j-vel jelölt csúccsal (jelölés: η(i,j)), ahol 4.
* Átnevezzük az i címkét j-re (jelölés: ρ(i,j) ) A korlátos klikkszélességű gráfok közé tartoznak a kográfok és a távolság-örökletes gráfok is. Bár általános esetben a klikkszélesség meghatározása feladat, és nem tudjuk, vajon polinom időben kiszámítható-e abban az esetben, ha korlátos, ismert több hatékony a klikkszélesség kiszámítására.Ezekre az algoritmusokra és a alapozva számos, általános gráfokon NP-nehéz gráfoptimalizálási probléma gyorsan megoldható vagy közelíthető a korlátos klikkszélességű gráfokon. A klikkszélesség fogalmához szükséges konstrukciós lépéseket , Engelfriet és Rozenberg fogalmazta meg 1990-ben , majd . A „klikkszélesség” kifejezést először használta egy másik fogalom leírására, de 1993-ra már a jelenlegi értelemben használták. (hu)
- A matematika, azon belül a gráfelmélet területén egy gráf klikkszélessége (clique-width) a gráf szerkezetének bonyolultságát leíró paraméter; közeli rokona a faszélességnek, de attól eltérő módon, sűrű gráfokon is korlátos lehet az értéke.A definíció szerint értéke megegyezik a gráf konstruálásához szükséges címkék minimális számával, ha a következő négy művelet engedélyezett: 1.
* Felveszünk egy új csúcsot, v-t és i címkével látjuk el (jelölés: i(v) vagy ) 2.
* Két címkézett gráf, G és H diszjunkt unióját képezzük (jelölés: ) 3.
* Minden i-vel jelölt csúcsot összekötünk minden j-vel jelölt csúccsal (jelölés: η(i,j)), ahol 4.
* Átnevezzük az i címkét j-re (jelölés: ρ(i,j) ) A korlátos klikkszélességű gráfok közé tartoznak a kográfok és a távolság-örökletes gráfok is. Bár általános esetben a klikkszélesség meghatározása feladat, és nem tudjuk, vajon polinom időben kiszámítható-e abban az esetben, ha korlátos, ismert több hatékony a klikkszélesség kiszámítására.Ezekre az algoritmusokra és a alapozva számos, általános gráfokon NP-nehéz gráfoptimalizálási probléma gyorsan megoldható vagy közelíthető a korlátos klikkszélességű gráfokon. A klikkszélesség fogalmához szükséges konstrukciós lépéseket , Engelfriet és Rozenberg fogalmazta meg 1990-ben , majd . A „klikkszélesség” kifejezést először használta egy másik fogalom leírására, de 1993-ra már a jelenlegi értelemben használták. (hu)
|
