Faszélesség

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.

Definíció

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 X₁, ..., X_n csomópontokkal, ahol mindegyik X_i a V részhalmaza, mely a következő tulajdonságoknak megfelel (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 X_i halmazok uniója megegyezik V-vel. Tehát a gráf minden csúcsát tartalmazza legalább egy facsomópont.
2. Ha X_i és X_j is tartalmaz egy v csúcsot, akkor az X_i és X_j közötti (egyedi) úton lévő minden T-beli X_k 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 X_i 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 X_i 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 X_i-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. 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 K_n 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ű:

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

A 3 faszélesség négy tiltott minora: K₅ (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 = 1 esetben az egyedüli tiltott minor a 3 csúcsú körgráf, K₃.
• A k = 2 esetben az egyedüli tiltott minor a 4 csúcsú teljes gráf, K₄.
• A k = 3 esetben már négy tiltott minor van: a K₅ 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.

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.

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

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 (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, 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 X_i halmazára, és az X_i 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(k^{k   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 ($\wedge ,\vee ,\neg ,\Rightarrow$), tartalmazás ellenőrzése (pl. $e\in E,v\in V$), kvantorok csúcsokra és élekre, illetve csúcsok és élek halmazára (pl. $\forall$ $v\in V$, $\exists$ $e\in E$, $\exists$ $I\subseteq V$, $\forall$ $F\subseteq E$), 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 $G=(V,E)$ gráf esetén azt kérdezzük, lehetséges-e minden $v\in V$ 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:

$\exists W_{1}\subseteq V:\exists W_{2}\subseteq V:\exists W_{3}\subseteq V:\forall v\in V:(v\in W_{1}\vee v\in W_{2}\vee v\in W_{3})\wedge$

$\forall v\in V:\forall w\in V:(v,w)\in E\Rightarrow (\neg (v\in W_{1}\wedge w\in W_{1})\wedge \neg (v\in W_{2}\wedge w\in W_{2})\wedge \neg (v\in W_{3}\wedge w\in W_{3}))$,

ahol $W_{1},W_{2},W_{3}$ 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. Az f-re vonatkozó legjobb korlátok szerint f legalább Ω(r^d) valamely rögzített d>0 konstansra, de legfeljebb O(√r/log r ). 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(n^{1 (1/k)} – időben.

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.

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

(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, é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

• 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.

Források

• Arnborg, S.; Corneil, D. & Proskurowski, A. (1987), "Complexity of finding embeddings in a k-tree", SIAM Journal on Matrix Analysis and Applications 8 (2): 277–284, DOI 10.1137/0608024
• Arnborg, Stefan; Proskurowski, Andrzej & Corneil, Derek G. (1990), "Forbidden minors characterization of partial 3-trees", Discrete Mathematics 80 (1): 1–19, DOI 10.1016/0012-365X(90)90292-P
• Arnborg, S. & Proskurowski, A. (1989), "Linear time algorithms for NP-hard problems restricted to partial k-trees", Discrete Applied Mathematics 23 (1): 11–24, DOI 10.1016/0166-218X(89)90031-0
• Bern, M. W.; Lawler, E. L. & Wong, A. L. (1987), "Linear-time computation of optimal subgraphs of decomposable graphs", Journal of Algorithms 8 (2): 216–235, DOI 10.1016/0196-6774(87)90039-3
• Bertelé, Umberto & Brioschi, Francesco (1972), Nonserial Dynamic Programming, Academic Press, pp. 37–38, ISBN 0-12-093450-7, <https://books.google.ca/books?id=baw3LMwm-y8C&pg=PA37>
• Bodlaender, Hans L. (1988), "Dynamic programming on graphs with bounded treewidth", Proc. 15th International Colloquium on Automata, Languages and Programming, vol. 317, Lecture Notes in Computer Science, Springer-Verlag, pp. 105–118, DOI 10.1007/3-540-19488-6_110
• Bodlaender, Hans L. (1996), "A linear time algorithm for finding tree-decompositions of small treewidth", SIAM Journal on Computing 25 (6): 1305–1317, DOI 10.1137/S0097539793251219
• Bodlaender, Hans L. (1998), "A partial k-arboretum of graphs with bounded treewidth", Theoretical Computer Science 209 (1–2): 1–45, DOI 10.1016/S0304-3975(97)00228-4
• Chekuri, Chandra & Chuzhoy, Julia (2016), "Polynomial bounds for the grid-minor theorem", Journal of the ACM 63 (5): A40:1–65, DOI 10.1145/2820609
• Demaine, Erik D.; Fomin, Fedor V. & Hajiaghayi, MohammadTaghi et al. (2004), "Bidimensional parameters and local treewidth", SIAM Journal on Discrete Mathematics 18 (3): 501–511, DOI 10.1137/S0895480103433410
• Demaine, Erik D. & Hajiaghayi, MohammadTaghi (2004a), "Diameter and treewidth in minor-closed graph families, revisited", Algorithmica 40 (3): 211–215, DOI 10.1007/s00453-004-1106-1
• Demaine, Erik D. & Hajiaghayi, MohammadTaghi (2004b), "Equivalence of local treewidth and linear local treewidth and its algorithmic applications", Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, New York: ACM, pp. 840–849
• Demaine, Erik D. & Hajiaghayi, MohammadTaghi (2008), "Linearity of grid minors in treewidth with applications through bidimensionality", Combinatorica 28 (1): 19–36, doi:10.1007/s00493-008-2140-4, <http://erikdemaine.org/papers/GridMinors_Combinatorica/paper.pdf>
• Diestel, Reinhard (2004), "A short proof of Halin's grid theorem", Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 74: 237–242, DOI 10.1007/BF02941538
• Diestel, Reinhard (2005), Graph Theory (3rd ed.), Springer, ISBN 3-540-26182-6, <http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/>
• Eppstein, D. (2000), "Diameter and treewidth in minor-closed graph families", Algorithmica 27 (3-4): 275–291, DOI 10.1007/s004530010020
• Frick, Markus & Grohe, Martin (2001), "Deciding first-order properties of locally tree-decomposable structures", Journal of the ACM 48 (6): 1184–1206, DOI 10.1145/504794.504798
• Grigoriev, Alexander & Bodlaender, Hans L. (2007), "Algorithms for graphs embeddable with few crossings per edge", Algorithmica 49 (1): 1–11, DOI 10.1007/s00453-007-0010-x
• Halin, Rudolf (1976), "S-functions for graphs", Journal of Geometry 8: 171–186, DOI 10.1007/BF01917434
• Kao, Ming-Yang, ed. (2008), "Treewidth of graphs", Encyclopedia of Algorithms, Springer, p. 969, ISBN 9780387307701, <https://books.google.com/books?id=i3S9_GnHZwYC&pg=PA969>
• Lagergren, Jens (1993), "An upper bound on the size of an obstruction", Graph structure theory (Seattle, WA, 1991), vol. 147, Contemporary Mathematics, Providence, RI: American Mathematical Society, pp. 601–621, DOI 10.1090/conm/147/01202
• Ramachandramurthi, Siddharthan (1997), "The structure and number of obstructions to treewidth", SIAM Journal on Discrete Mathematics 10 (1): 146–157, DOI 10.1137/S0895480195280010
• Robertson, Neil & Seymour, Paul D. (1984), "Graph minors III: Planar tree-width", Journal of Combinatorial Theory, Series B 36 (1): 49–64, DOI 10.1016/0095-8956(84)90013-3
• Robertson, Neil & Seymour, Paul D. (1986), "Graph minors V: Excluding a planar graph", Journal of Combinatorial Theory, Series B 41 (1): 92–114, DOI 10.1016/0095-8956(86)90030-4
• Robertson, Neil; Seymour, Paul & Thomas, Robin (1994), "Quickly excluding a planar graph", Journal of Combinatorial Theory, Series B 62 (2): 323–348, DOI 10.1006/jctb.1994.1073
• Satyanarayana, A. & Tung, L. (1990), "A characterization of partial 3-trees", Networks 20 (3): 299–322, DOI 10.1002/net.3230200304
• Seymour, Paul D. & Thomas, Robin (1993), "Graph Searching and a Min-Max Theorem for Tree-Width.", Journal of Combinatorial Theory, Series B 58 (1): 22–33, DOI 10.1006/jctb.1993.1027
• Shoikhet, Kirill & Geiger, Dan (1997), "A practical algorithm for finding optimal triangulations", Proc. AAAI '97, pp. 185–190, <http://www.aaai.org/Papers/AAAI/1997/AAAI97-029.pdf>
• Thorup, Mikkel (1998), "All structured programs have small tree width and good register allocation", Information and Computation 142 (2): 159–181, DOI 10.1006/inco.1997.2697