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 -nél jelent meg „dimenzió” név alatt. Később fedezte fel újra, a Hadwiger-számmal közös tulajdonságai alapján. Majd ismét felfedezték, és azóta számos más szerző is tanulmányozta. pp.354–355
Definíció
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 section 12.3 (a csomópont alatt T egy-egy csúcsát értjük, hogy elkerüljük a G csúcsaival való összekeverésüket): Az Xi halmazok uniója megegyezik V-vel. Tehát a gráf minden csúcsát tartalmazza legalább egy facsomópont. 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. 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 rendű menedék, de magasabb rendű már nem. Egy rendű menedék olyan β függvény, ami G minden, legfeljebb k csúcsot tartalmazó X csúcshalmazához hozzárendeli valamely összefüggő komponensét, és amire igaz az a monotonitási feltétel, miszerint ha , akkor .
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.. 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 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
Korlátos faszélességű gráfcsaládok 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.. 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..
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ű:. F korlátozott faszélességű gráfok minorzárt családja; Az F-et jellemző véges sor tiltott minor közül valamelyik síkba rajzolható; F minorzárt gráfcsalád, ami nem tartalmazza az összes síkbarajzolható gráfot.
Tiltott minorok
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 = 1 esetben az egyedüli tiltott minor a 3 csúcsú körgráf, K3.. A k = 2 esetben az egyedüli tiltott minor a 4 csúcsú teljes gráf, K4. A k = 3 esetben már négy tiltott minor van: a K5 teljes gráf, az oktaéder gráfja, a GP(5,1) ötszög alapú hasábgráf és a Wagner-gráf. Ezek közül a két poliédergráf síkba rajzolható.; . 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ő. 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.
Algoritmusok
A faszélesség meghatározása Annak meghatározása, hogy adott G gráf faszélessége adott k értékét meghaladja-e, NP-teljes probléma. 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.. Ezen algoritmus időfüggése k szerint exponenciális.
Nem ismert, hogy a síkbarajzolható gráfok faszélességének meghatározása NP-teljes, vagy polinom időben meghatározható-e.
A gyakorlatban 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 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, mely paraméterről 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,; ; . 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 felbontá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
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 á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
Útszélesség 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. 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 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.Robertson, Seymour. Graph minors. V. Excluding a planar graph. Az f-re vonatkozó legjobb korlátok szerint f legalább Ω(rd) valamely rögzített d>0 konstansra, de legfeljebb O().. Az alsó korlátban látható Ω jelöléshez lásd O jelölés. 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. 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.
Átmérő és lokális faszélesség 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. 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ő;; . ezt később sikerült sima exponenciálisra, majd lineáris korlátra javítani. Az átmérő-faszélesség tulajdonság közeli kapcsolatban áll a bidimenzionalitás algoritmikus elméletével,; . é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.