Faszélesség

A Wikipédiából, a szabad enciklopédiából

A matematika, azon belül a gráfelmélet területén egy irányítatlan gráf faszélessége vagy favastagsága (treewidth) egy a gráf szerkezetétől függő, a gráfhoz rendelt szám, azaz gráftulajdonság. A faszélesség több, egymással egyenértékű módon definiálható: a gráf fafelbontása legnagyobb csúcshalmazával, a gráf merev körű kiegészítésében található legnagyobb klikkel, a gráfon játszott üldözős-menekülős játék elkerülési stratégiáját leíró menedékkel vagy az egymást kölcsönösen érintő összefüggő részgráfok, azaz bramble-ök maximális rendjével.

A faszélesség gyakran előkerül gráfalgoritmusok parametrikus bonyolultságának vizsgálatakor. A legfeljebb k faszélességű gráfokat részleges k-fáknak is nevezik; számos, részletekbe menően tanulmányozott gráfcsalád rendelkezik korlátozott faszélességgel.

A faszélesség koncepciója először Umberto Bertelé and Francesco Brioschi (1972)-nél jelent meg „dimenzió” név alatt. Később Rudolf Halin (1976) fedezte fel újra, a Hadwiger-számmal közös tulajdonságai alapján. Majd Neil Robertson and Paul Seymour (1984) ismét felfedezték, és azóta számos más szerző is tanulmányozta.[1]

Definíció[szerkesztés]

Nyolc csúcsú gráf (fent), fafelbontása hat csomópontú fába (lent). A gráf minden éle olyan két csúcsot köt össze, melyek valamely fa-csomóponton együtt szerepelnek, továbbá minden egyes csúcs olyan fa-csomópontokon szerepel, melyek a fa folytonos részfáját alkotják. Minden fa-csomóponton legalább három csúcs szerepel, ezért ennek a felbontásnak a szélessége kettő.

Egy G = (V, E) gráf fafelbontása alatt olyan T fát értünk, az X1, ..., Xn csomópontokkal, ahol mindegyik Xi a V részhalmaza, mely a következő tulajdonságoknak megfelel[2] (a csomópont alatt T egy-egy csúcsát értjük, hogy elkerüljük a G csúcsaival való összekeverésüket):

  1. Az Xi halmazok uniója megegyezik V-vel. Tehát a gráf minden csúcsát tartalmazza legalább egy facsomópont.
  2. Ha Xi és Xj is tartalmaz egy v csúcsot, akkor az Xi és Xj közötti (egyedi) úton lévő minden T-beli Xk csomópontnak is tartalmaznia kell v-t. Ezzel ekvivalens megfogalmazás szerint, a v-t tartalmazó facsomópontok a T összefüggő részfáját alkotják.
  3. A gráf minden (v, w) éléhez tartozik egy Xi részhalmaz, ami v-t és w-t is tartalmazza. Tehát a gráf csúcsai akkor lehetnek szomszédosak, ha a nekik megfelelő részfáknak van egy közös csomópontja.

A fafelbontás szélessége a legnagyobb Xi halmaz mérete mínusz egy. A G gráf tw(G) faszélessége a G összes lehetséges fafelbontásai közül a minimális szélesség. Ebben a definícióban azért csökkentjük eggyel a legnagyobb halmaz méretét, hogy egy fa szélessége éppen eggyel legyen egyenlő.

Ezzel ekvivalens definíció szerint a G faszélessége eggyel kisebb, mint a legkisebb klikkszámú, G-t tartalmazó merev körű gráf legnagyobb klikkje. Ilyen klikkméretű merev körű gráfot elő lehet állítani úgy, hogy G-nek minden olyan két csúcsa közé behúzunk egy élt, melyek közül mindkettő legalább egy halmazba beletartozik az Xi-t közül.

A faszélesség jellemezhető az üldözős-menekülős játék elkerülési stratégiáját leíró menedékek segítségével is. Egy G gráf faszélessége pontosan akkor k, ha létezik benne k + 1 rendű menedék, de magasabb rendű már nem. Egy k + 1 rendű menedék olyan β függvény, ami G minden, legfeljebb k csúcsot tartalmazó X csúcshalmazához hozzárendeli G \ X valamely összefüggő komponensét, és amire igaz az a monotonitási feltétel, miszerint ha X ⊆ Y, akkor β(Y) ⊆ β(X).

A 3×3-as rácsgráfhoz tartozó 4 rendű bramble, melynek létezése igazolja, hogy a gráf faszélessége legalább 3

Hasonló jellemzés adható az egymást kölcsönösen érintő (vagy közös csúccsal rendelkező, vagy éllel összekötött) összefüggő részgráfok, a bramble-ök segítségével.[3] A bramble rendje a részgráfok családjának legkisebb „hitting set”-je (olyan halmaz, ami minden halmaz elemei közül legalább egyet tartalmaz), a gráf faszélessége pedig eggyel kisebb a bramble maximális rendjénél.

Példák[szerkesztés]

Minden Kn teljes gráf faszélessége n − 1. Ez a legkönnyebben a merev körű gráfos definícióból látható be: a teljes gráf eleve merev körű, és újabb él hozzáadásával nem lehet csökkenteni a legnagyobb klikkjének a méretét.

Egy összefüggő, legalább két csúcsból álló gráf faszélessége pontosan akkor 1, ha a gráf fa. A fa szélessége a teljes gráfokhoz hasonlóan látható be (merev körű, és maximális elemszámú klikkje 2). Megfordítva, ha egy gráfnak van köre, akkor a gráf minden merev körű kiegészítésében legalább egy háromszög egymást követő csúcsa szerepel, amiből következik, hogy a faszélesség legalább kettő.

Korlátos faszélesség[szerkesztés]

Korlátos faszélességű gráfcsaládok[szerkesztés]

Rögzített k értékekre, a legfeljebb k faszélességű gráfokat részleges k-fáknak nevezik. A korlátos faszélességű gráfcsaládok közé tartoznak a kaktuszgráfok, pszeudoerdők, soros-párhuzamos gráfok, külsíkgráfok, Halin-gráfok és Apollóniusz-hálózatok.[4] A strukturált programok lefordításakor létrejövő vezérlésfolyam-gráf faszélessége szintén korlátos, ami lehetővé teszi bizonyos feladatok, például a regiszterallokáció hatékony végrehajtását.[5]

A síkbarajzolható gráfok faszélessége nem korlátos, hiszen az n × n-es rácsgráf olyan síkbarajzolható gráf, melynek faszélessége pontosan n. Ezért ha F egy korlátos faszélességű, minorzárt gráfcsalád, akkor nem tartalmazhatja az összes síkbarajzolható gráfot. Megfordítva, ha valamely síkbarajzolható gráf nem jelenik meg egy F gráfcsalád minoraként, akkor létezik olyan k konstans, melyre az összes F-beli gráf faszélessége legfeljebb k. Más szavakkal, a következő három feltétel egymással egyenértékű:[6]

  1. F korlátozott faszélességű gráfok minorzárt családja;
  2. Az F-et jellemző véges sor tiltott minor közül valamelyik síkba rajzolható;
  3. F minorzárt gráfcsalád, ami nem tartalmazza az összes síkbarajzolható gráfot.

Tiltott minorok[szerkesztés]

A 3 faszélesség négy tiltott minora: K5 (fent balra), az oktaédergráf (lent balra), a Wagner-gráf (fent jobbra) és az ötszögű hasábgráf (lent jobbra)

Minden véges k értékre a legfeljebb k faszélességű gráfok jellemezhetők tiltott minorok egy véges halmazával. (Tehát bármely k-nál nagyobb faszélességű gráf tartalmazza ezen obstrukciós halmaz tiltott gráfjainak valamelyikét minorként.) Minden ilyen véges obstrukciós halmaz tartalmaz legalább egy síkbarajzolható gráfot.

A k = 4 esetben már legalább 75 tiltott minort találtak, és a k növekedésével a tiltott minorok száma legalább a k négyzetgyöke szerint exponenciálisan nő.[9] Az ismert felső korlátok a tiltott minorok méretére és számára azonban sokkal nagyobbak ennél az alsó korlátnál.[10]

Algoritmusok[szerkesztés]

A faszélesség meghatározása[szerkesztés]

Annak meghatározása, hogy adott G gráf faszélessége adott k értékét meghaladja-e, NP-teljes probléma.[11] Ennek ellenére k rögzített értékére a pontosan k faszélességű gráfok felismerhetők, és k szélességű fafelbontásuk is előállítható lineáris időben.[12] Ezen algoritmus időfüggése k szerint exponenciális.

A matematika megoldatlan problémája:
Meghatározható-e a síkbarajzolható gráfok faszélessége polinom időben?
(A matematika további megoldatlan problémái)

Nem ismert, hogy a síkbarajzolható gráfok faszélességének meghatározása NP-teljes, vagy polinom időben meghatározható-e.[13]

A gyakorlatban (Shoikhet & Geiger 1997) algoritmusa képes a legfeljebb 100 csúcsból álló gráfok faszélességének meghatározására legfeljebb 11 értékig, optimális faszélességű merev körű kiegészítés keresésével.

Egyéb problémák megoldása alacsony faszélességű gráfokon[szerkesztés]

Az 1970-es évek elején megfigyelték, hogy a gráfokon definiált kombinatorikai optimalizációs problémák nagy osztálya hatékonyan megoldható nem soros, dinamikus programozási módszerekkel, amennyiben a gráf korlátos „dimenzióval” rendelkezik,[14] mely paraméterről (Bodlaender 1998) megmutatta, hogy a faszélességgel ekvivalens. Később egymástól függetlenül több szerző is megfigyelte az 1980-as évek végén,[15] hogy számos, tetszőleges gráfokon NP-teljes probléma a korlátos faszélességű gráfokon dinamikus programozással hatékonyan megoldható, a gráfok fafelbontásának felhasználásával.

Példa erre a k faszélességű gráf színezése. A fafelbontás minden Xi halmazára, és az Xi csúcsainak minden színosztályba sorolására az algoritmus meghatározza, hogy a színezés érvényes-e, illetve kiterjeszthető-e a a fefelbontás leszármazó csomópontjaira, a csomópontokon tárolt hasonló információk felhasználásával. A végső algoritmus egy n csúcsú gráf optimális színezését O(kk + O(1)n) időben oldja meg, ami ezt a problémát rögzített paraméter mellett kezelhetővé teszi.

Courcelle-tétel[szerkesztés]

Bővebben: Courcelle-tétel

Egy nagy problémaosztályra létezik lineáris idejű megoldó algoritmus, ha bemenetként egy konstans, korlátos faszélességű fafelbontást adunk meg. A Courcelle-tétel[16][17] állítása szerint ha egy gráfprobléma kifejezhető monadikus másodrendű logika szerinti gráflogika segítségével, akkor korlátos faszélességű gráfokon lineáris időben megoldható. A monadikus másodrendű logika a gráftulajdonságokat a következő konstrukciók segítségével írja le: logikai műveletek (), tartalmazás ellenőrzése (pl. ), kvantorok csúcsokra és élekre, illetve csúcsok és élek halmazára (pl. , , , ), illeszkedés ellenőrzése (u az e végpontja), valamint egy optimalizáló kiterjesztés.

Tekintsük például a gráfok 3-színezési problémáját. Egy gráf esetén azt kérdezzük, lehetséges-e minden csúcshoz a 3 szín egyikét hozzárendelni úgy, hogy semelyik két szomszédos csúcs ne legyen egymással megegyező színű. A probléma így fejezhető ki monadikus másodrendű logikával:

,

ahol az egyes színosztályba tartozó csúcs-részhalmazoknak felelnek meg. Tehát Courcelle tétele szerint a 3-színezési probléma lineáris időben megoldható egy konstans faszélességű gráfon, ha annak fafelbontása adott.

Kapcsolódó paraméterek[szerkesztés]

Útszélesség[szerkesztés]

Egy gráf útszélessége a faszélességhez nagyon hasonlóan definiálható, de olyan fafelbontásokra korlátozódik, melyben kizárólag útgráfok szerepelnek. Alternatív megoldásként az útszélesség definiálható intervallumgráfok segítségével, hasonlóan a faszélesség merev körű gráfokkal való definiálásához. A gráfok útszélessége az eddigiekből következően legalább akkora, mint a faszélességük, de legfeljebb logaritmikus faktorral lehet nagyobb.[4] Egy másik paramétert, a sávszélességet egység-intervallumgráffal definiálják, és legalább akkora, mint az útszélesség. További kapcsolódó paraméter a famélység, ami egy minorzárt gráfcsaládnál akkor korlátos, ha a család tiltott gráfja egy út, valamint a degeneráltság, a gráfok ritkaságának egy mértéke, ami legfeljebb a faszélességgel egyezik meg.

Rácsminor-méret[szerkesztés]

Mivel egy n × n méretű négyzetes rácsgráf faszélessége n, egy G gráf faszélessége mindig nagyobb vagy egyenlő, mint G legnagyobb rácsgráf-minorának mérete. Megfordítva, a Robertson és Seymour által kimondott rácsminor-tétel (grid minor theorem) szerint létezik olyan f függvény, melyre a faszélesség legfeljebb f(r), ahol r a legnagyobb négyzetrács-minor mérete.[18] Az f-re vonatkozó legjobb korlátok szerint f legalább Ω(rd) valamely rögzített d>0 konstansra, de legfeljebb O(√r/log r).[19] Egyes korlátozott gráfcsaládokra szorosabb korlátok ismertek, melyekre vonatkozó gráfoptimalizálási problémákra hatékony algoritmusokat ad a bidimenzionalitás-elmélet.[20] A Halin-rácstétel a faszélesség és rácsminor-méret között állít fel összefüggést végtelen gráfokra.[21]

Átmérő és lokális faszélesség[szerkesztés]

Egy F gráfcsaládnak akkor van korlátos helyi faszélessége (bounded local treewidth), illetve rendelkezik az átmérő-faszélesség tulajdonsággal (diameter-treewidth property), ha a család gráfjainak faszélességét felülről korlátozza átmérőjük egy függvénye. Ha F minden minora szintén F-ben található, akkor F pontosan akkor rendelkezik korlátos helyi faszélességgel, ha F valamelyik tiltott minora egy csúcsgráf.[22] Ennek az eredménynek az eredeti bizonyításában szerepelt annak bizonyítása is, hogy egy csúcsminor-mentes gráfcsalád faszélessége legfeljebb az átmérő dupla-exponenciális függvényében nő;[23] ezt később sikerült sima exponenciálisra[20], majd lineáris korlátra javítani.[24] Az átmérő-faszélesség tulajdonság közeli kapcsolatban áll a bidimenzionalitás algoritmikus elméletével,[25] és minden elsőrendű logikával definiálható gráftulajdonság létezése egy csúcsminor-mentes gráfcsalád esetében eldönthető a lineárisnál csak kissé rosszabb – O(n1+(1/k) – időben.[26]

Lehet korlátos helyi faszélessége nem minorzárt gráfosztálynak is. Ilyenek például az élenként legfeljebb egy metszéssel síkba rajzolható ún. 1-síkbarajzolható gráfok, vagy általánosabban azok a gráfok, melyek egy korlátos génuszú felületre élenként korlátozott számú metszéssel lerajzolhatók. Ahogy a minorzárt gráfcsaládoknál, a korlátos helyi faszélesség itt is hatékony approximációs algoritmusoknak enged utat.[27]

Hadwiger-szám és S-függvények[szerkesztés]

(Halin 1976) egy általa S-függvényeknek (S-functions) nevezett gráfparaméter-osztályt definiál, melybe a faszélesség is beletartozik. Ezeknek a gráfokhoz egész számokat rendelő függvényeknek a következő tulajdonságokkal kell rendelkezniük: az üres gráfon legyen nulla az értékük, legyenek minor-monotonok,[28] értékük eggyel nőjön, ha az összes korábbi csúccsal szomszédos új csúcs kerül a gráfba, végül hogy egy klikk-szeparátor két oldalán lévő részgráfok értékei közül a nagyobbikat vegye fel. Az összes ilyen függvény halmaza az elemenkénti minimalizáció és maximalizáció műveleteire nézve teljes hálót alkot. A háló legkisebb eleme a Hadwiger-szám, azaz a legnagyobb teljesgráf-minor mérete, a legnagyobb pedig a faszélesség.

Fordítás[szerkesztés]

  • Ez a szócikk részben vagy egészben a Treewidth című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek[szerkesztés]

  1. ↑ (Diestel 2005) pp.354–355
  2. ↑ (Diestel 2005) section 12.3
  3. ↑ (Seymour & Thomas 1993).
  4. ↑ a b (Bodlaender 1998).
  5. ↑ (Thorup 1998).
  6. ↑ (Robertson & Seymour 1986).
  7. ↑ a b (Bodlaender 1988).
  8. ↑ (Arnborg, Proskurowski & Corneil 1990); (Satyanarayana & Tung 1990).
  9. ↑ Ramachandramurthi (1997).
  10. ↑ Lagergren (1993).
  11. ↑ Arnborg, Corneil & Proskurowski (1987).
  12. ↑ (Bodlaender 1996).
  13. ↑ Kao (2008).
  14. ↑ Bertelé & Brioschi (1972).
  15. ↑ (Arnborg & Proskurowski 1989); (Bern, Lawler & Wong 1987); (Bodlaender 1988).
  16. ↑ Courcelle, B. (1990. április 1.). „The monadic second-order logic of graphs I: Recognizable sets of finite graphs”. Information and Computation 85, 12–75. o. DOI:10.1016/0890-5401(90)90043-h.  
  17. ↑ Courcelle, B. (1992. április 1.). „The monadic second-order logic of graphs III: Treewidth, forbidden minors and complexity issues.”. Informatique Théorique (26), 257–286. o.  
  18. ↑ Robertson, Seymour. Graph minors. V. Excluding a planar graph. [1] „open access” publikáció – ingyenesen elolvasható
  19. ↑ (Chekuri & Chuzhoy 2016). Az alsó korlátban látható Ω jelöléshez lásd O jelölés.
  20. ↑ a b Demaine & Hajiaghayi (2008).
  21. ↑ Diestel (2004).
  22. ↑ Eppstein (2000).
  23. ↑ (Eppstein 2000); (Demaine & Hajiaghayi 2004a).
  24. ↑ Demaine & Hajiaghayi (2004b).
  25. ↑ (Demaine et al. 2004); (Demaine & Hajiaghayi 2008).
  26. ↑ Frick & Grohe (2001).
  27. ↑ Grigoriev & Bodlaender (2007).
  28. ↑ Az f függvény akkor minor-monoton, ha fennáll, hogy ha H a G minora, akkor f(H) ≤ f(G).

Források[szerkesztés]

A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Faszélesség&oldid=26713708”