Fa szélessége (gráfelmélet)

A gráfelméletben egy irányítatlan gráf faszélessége a gráfhoz társított szám. A faszélesség több egyenértékű módon is definiálható: a legnagyobb csúcshalmaz méreteként egy fa dekompozícióban , a legnagyobb klikk méreteként a gráf akkordösszegében, mint a maximális menekülési sorrend, amikor egy üldözési játék stratégiáját írjuk le. egy gráfot, vagy a bramble maximális sorrendjeként egymáshoz kapcsolódó részgráfok halmaza. A faszélességet gyakran használják paraméterként az algoritmusok parametrikus összetettségének grafikonokon. A legfeljebb k faszélességű grafikonokat részleges k-fáknak nevezzük . Sok más jól tanulmányozott gráfcsalád is korlátozott faszélességgel rendelkezik.

A faszélesség fogalmát Halin ( 1976 ) vezette be egy másik paraméter, a Hadwiger-szám alapján, amellyel a faszélesség számos tulajdonságon osztozik. A Treewidth-et később Robertson és Seymour [1] fedezte fel újra, és azóta számos szerző tanulmányozta. [2]

Definíció

A G = ( V , E ) gráf fafelbontása egy olyan T fa , amelynek X 1 , ..., X n csúcsai V részhalmazai, amelyek kielégítik a következő tulajdonságokat [3] :

  1. Az összes X i halmaz uniója egyenlő V -vel . Így a gráf bármely csúcsa legalább egy halmazban szerepel.
  2. Ha X i és X j egyaránt tartalmazza a v csúcsot, akkor az X k fa összes többi csúcsa az X i -től X j -ig tartó (egyedi) úton szintén v -t tartalmaz . Ez egyenértékű azzal, mintha azt mondanánk, hogy a v -t tartalmazó fa csúcsai T összefüggő részfáját alkotják .
  3. G bármely ( v , w ) éléhez létezik egy X i részhalmaz, amely v -t és w -t is tartalmazza . Vagyis a csúcsok szomszédosak egy gráfban, ha csak a megfelelő részfáknak van közös csúcsa a T fában .

Egy fa dekompozíció szélessége a legnagyobb X i halmazának a mérete mínusz egy (tehát a fák fabontási szélessége 1).

G faszélessége tw( G ) a G összes lehetséges dekompozíciójának minimális szélessége . Ebben a definícióban az egyet levonják a halmaz méretéből, így a fa faszélessége eggyel egyenlő.

Ugyanígy a G faszélessége eggyel kisebb, mint a G -t tartalmazó minimális klikkszámmal rendelkező akkordgráf legnagyobb klikkjének mérete. Ezzel a klikkszámmal akkordgráfot kaphatunk, ha bármely két csúcs között éleket adunk G -hez , ha mindkettő ugyanahhoz (legalább egy) X i halmazhoz tartozik .

A Treewidth leírható menedékekkel is , olyan függvényekkel, amelyek bizonyos gráf - üldözési játékok kijátszási stratégiáit írják le. Egy G gráfnak akkor és csak akkor van k faszélessége , ha van k + 1 rendű menedéke, de nincs magasabb rendű menedéke. Itt a k + 1 rendű menedék az a β függvény , amely minden G -beli legfeljebb k csúcsú X halmazt leképez a G \ X gráf egyik összefüggő komponensére, és amely kielégíti a monotonitási tulajdonságot .

at .

Hasonló leírást készíthetünk a blackberries használatával is , amely egy olyan összefüggő gráfcsalád, amely érintők (ami azt jelenti, hogy vagy közös csúcsuk van, vagy éllel vannak összekötve). [4] A G egy részhalmazáról azt mondjuk, hogy fed (vagy takar) egy szederet, ha a szeder minden elemét metszi. A szeder sorrendje a legkisebb borítás , és a grafikon faszélessége eggyel kisebb, mint a szeder maximális sorrendje.

Példák

Bármely K n teljes gráf faszélessége n  − 1. Ez a legkönnyebben a faszélesség definícióját használva látható akkordgráfoknál – a teljes gráf már akkordális, és élek hozzáadásával nem lehet csökkenteni a legnagyobb klikk méretét.

A legalább két csúcsot tartalmazó összekapcsolt gráfok faszélessége 1 akkor és csak akkor, ha fa. Egy fának ugyanaz a szélessége, mint a teljes grafikonoknak (tehát akkordálisak, és a maximális kattintásuk kettes méretű). Ezzel szemben, ha egy gráfnak van ciklusa, akkor a gráf bármely húrkomplementere legalább egy háromszöget tartalmaz, ami azt jelenti, hogy a gráf faszélessége legalább kettő.

Korlátozott faszélesség

Korlátozott szélességű fagrafikonok családjai

Bármely rögzített k állandó esetén a legfeljebb k faszélességű gráfokat részleges k-fának nevezzük . A korlátozott faszélességű gráfok további családjai közé tartoznak a kaktuszok , álerdők , párhuzamos soros gráfok , külső síkbeli gráfok , Halin -gráfok és Apollonius-gráfok [5] . A strukturált programok fordításában megjelenő vezérlőfolyamat-grafikonok szintén korlátozott faszélességűek, lehetővé téve egyes feladatok, például a regiszterkiosztás hatékony végrehajtását . [6]

A sík gráfok nem rendelkeznek korlátos faszélességgel, mert az n × n rács olyan sík gráf, amelynek faszélessége pontosan n . Így, ha F kisebb zárt gráfok családja korlátos faszélességgel, akkor nem tartalmazhat minden síkgráfot. Megfordítva, ha egy síkgráf nem lehet az F család gráfjainak kisebb része , akkor van olyan k állandó, hogy az F -beli összes gráf faszélessége legfeljebb k . Így a következő három feltétel egyenértékű egymással: [7]

  1. F korlátos faszélességű kisebb-nagyobb zárt gráfok családja;
  2. A véges számú tiltott kiskorú közül az egyik a síkbeli ;
  3. Az F kisebb zárt gráfok családja, beleértve a nem síkbeli gráfokat is.

Illegális kiskorúak

K bármely véges értékéhez a legfeljebb k faszélességű gráfok véges számú tiltott mellékel írhatók le , amelyek mindegyike tartalmaz legalább egy síkgráfot.

Nagy k értéke esetén a tiltott kiskorúak száma legalább k kitevőjével nő . [10] A tiltott kiskorúak méretének és számának ismert felső határa azonban jóval magasabb, mint ez az alsó korlát. [tizenegy]

Algoritmusok

Fa szélesség számítása

Annak meghatározása, hogy egy adott G gráfnak legfeljebb k faszélessége van-e, NP-teljes probléma. [12] Ha azonban k fix, akkor k faszélességű gráfokat találhatunk, és a megfelelő fafelbontást lineáris időben megszerkeszthetjük. [13] Az algoritmus végrehajtási ideje exponenciálisan függ k -tól .

A gyakorlatban Shoikhet és Geiger algoritmusa ( Shoikhet, Geiger 1997 ) meg tudja találni a 100 csúcs méretű gráfok faszélességét, és a faszélességet 11-ig úgy, hogy megtalálja ezeknek a gráfoknak az optimális faszélességű húrkomplementerét.

Egyéb feladatok megoldása kis faszélességű grafikonokon

A huszadik század hetvenes éveinek elején észrevették, hogy a gráfokon a kombinatorikus optimalizálási problémák nagy csoportja hatékonyan megoldható nem soros dinamikus programozással , ha a gráf korlátos dimenzióval rendelkezik , [14] a faszélességhez kapcsolódó paraméter. Később, az 1980-as évek végén [15] számos matematikus fedezte fel egymástól függetlenül, hogy sok olyan algoritmikus probléma, amely tetszőleges gráfok esetén NP-teljes , hatékonyan megoldható a korlátos faszélességű gráfok dinamikus programozásával , ezeknek a gráfoknak a fabontásával.

Például a k faszélességű gráf színezésének problémája megoldható dinamikus programozással a gráf fabontásán. A fabontás minden X i halmazára és az X i csúcsok színekre való felosztására az algoritmus meghatározza, hogy az eredményül kapott színezés elfogadható-e, és kiterjeszthető-e a dekompozíció összes származtatott csúcsára az azonos típusú információk kombinálásával és tárolásával. ezeket a csúcsokat. Az így kapott algoritmus megtalálja az n csúcsú gráf optimális színezését O( k k  + O(1) n ) idő alatt, ami ezt a problémát paraméteresen megnehezíti egy fix paraméterrel .

Kapcsolódó paraméterek

Nyomtáv

A gráf útvonalszélességének meghatározása nagyon hasonló a fa dekompozíción keresztüli faszélességéhez, de csak azokra a dekompozíciókra korlátozódik, ahol az eredményül kapott fa egy útvonal . Egy másik módszer az, hogy az intervallumgráfból határozzuk meg az útvonalszélességet, hasonlóan a húr gráfok faszélességének meghatározásához. Ennek következtében egy gráf útszélessége legalább akkora, mint a faszélessége, de csak logaritmikus tényezővel lehet nagyobb. [5] Egy másik paraméter, a graph bandwidth definíciója hasonló, szabályos intervallum grafikonokon alapul , és a paraméter értéke nem kisebb, mint az útvonal szélessége. Ezen kívül létezik a fa mélysége , a kisebb zárt gráfokhoz kötött szám, ha és csak akkor, ha a család nem tartalmazza az összes útvonalgráfot, valamint a degeneráció , a gráf ritkaságának mértéke, amely nem haladja meg a fa szélességét.

Rács kisebb méret

Mivel egy n  ×  n rács faszélessége n , G fa szélessége mindig nagyobb vagy egyenlő G legnagyobb négyzetes kisebb rácsának méretével . Megfordítva, van egy f függvény , amelyre a fa szélessége nem haladja meg az f ( r )-t, ahol r a legnagyobb négyzet kisrács mérete. Az f ismert határai azonban nem kicsik: f -nek legalább Ω( r 2  log  r ) és legfeljebb 20 2 r 5 értékűnek kell lennie . [16] A korlátos gráfcsaládoknál ismertek a szigorúbb határok, amelyek a kétdimenziós elmélet szerint hatékony algoritmusokat adnak ezeken a gráfcsaládokon számos optimalizálási problémára . [17] A Halin-féle rácstétel analógiát ad a fa szélessége és a rács kisebb mérete közötti kapcsolatra korlátlan gráfok esetén. [tizennyolc]

Átmérő és helyi fa szélesség

Egy F gráfcsaládról azt mondjuk, hogy korlátozott lokális faszélessége van , ha a családban lévő gráfok faszélessége felett van az átmérő függvényében . Ha egy F családtag bármely kiskorú tagja is F - ben van , akkor F akkor és csak akkor korlátozza a helyi faszélességet , ha F egyik tiltott kiskora csúcsgráf . [19] Ennek az eredménynek az eredeti bizonyítéka azt mutatta, hogy a fák szélessége a mellék gráfok családjában, amelyek csúcsgráfok, nem növekszik gyorsabban az átmérő kitevőjének kétszeresénél. [20] Ezt később csak egy exponenciális [17] és végül egy lineáris határra redukálták. [21] A korlátos lokális faszélesség szorosan összefügg a kétdimenziós algoritmus elméletével [22] , és minden olyan gráftulajdonság, amely elsőrendű logikával definiálható, kiszámítható egy olyan családból származó gráfokra, amelyek nem tartalmaznak kisebb csúcsú gráfokat, csak kissé szuperlineáris időben. [23]

Egyes gráfosztályok, amelyek nincsenek bezárva a minor alá, továbbra is korlátozott helyi faszélességgel rendelkeznek. Konkrétan ezek az 1-síkú gráfok , azaz olyan gráfok, amelyek egy élnek legfeljebb egy metszéspontjával rajzolhatók meg a síkon, és általánosabb gráfok, amelyek korlátozott számú éllel rendelkező, korlátozott nemzetség felületére rajzolhatók. kereszteződések. Csakúgy, mint a korlátozott lokális faszélességű kisebb zárt gráfok családjai esetében, ez a tulajdonság megnyitja az utat az ilyen gráfok hatékony közelítő algoritmusai előtt. [24]

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

Halin ( 1976 ) definiálja a gráfparaméterek egy osztályát, amelyet S -függvényeknek nevez, és ez az osztály tartalmazza a fa szélességét. Ezeknek a függvényeknek a tartományuk a gráfok, a tartományuk pedig az egész számok, és az él nélküli gráfokon nulla értéket kell felvenniük, és monotonnak kell lenniük a kisebbekhez képest , azaz eggyel nőnek, ha egy új csúcsot adunk hozzá, amely szomszédos minden előző csúcsok. Az is szükséges, hogy a gráffüggvény értéke egyenlő legyen a nagyobbik értékkel azon két részhalmazon, amelyek metszéspontja egyszerre csúcselválasztó és klikk . Az összes ilyen függvény halmaza egy teljes rácsot alkot az elemenkénti minimalizálási és maximalizálási műveletek tekintetében. Ennek a rácsnak a felső eleme a faszélesség, az alsó eleme pedig a Hadwiger-szám , amely az adott gráfban a maximális teljes moll mérete.

Jegyzetek

  1. ↑ Robertson, Seymour, 1984
  2. ↑ Diestel, 2005 354–355
  3. ↑ Diestel, 2005 , 12.3
  4. ↑ Seymour, Thomas, 1993 .
  5. ↑ 1 2 Bodlaender, 1998
  6. ↑ Thorup, 1998 .
  7. ↑ Robertson, Seymour, 1986 .
  8. ↑ 1 2 Bodlaender, 1988 .
  9. ↑ Arnborg, Proskurowski, Corneil, 1990 ; Satyanarayana, Tung, 1990 .
  10. ↑ Ramachandramurthi, 1997 .
  11. ↑ Lagergren, 1993 .
  12. ↑ Arnborg, Corneil, Proskurowski, 1987 .
  13. ↑ Bodlaender, 1996 .
  14. ↑ Bertelé, Brioschi, 1972 .
  15. ↑ Arnborg, Proskurowski, 1989 ; Bern, Lawler, Wong, 1987 ; Bodlaender, 1988 .
  16. ↑ Robertson, Seymour, Thomas, 1994 . Az alsó korlát Ω értékét lásd: "O" nagy és "o" kicsi .
  17. ↑ 1 2 Demaine, Hajiaghayi, 2008 .
  18. ↑ Diestel, 2004 .
  19. ↑ Eppstein, 2000 .
  20. ↑ Eppstein, 2000 ; Demaine, Hajiaghayi, 2004a .
  21. ↑ Demaine, Hajiaghayi, 2004b .
  22. ↑ Demaine, Fomin, Hajiaghayi, Thilikos, 2004 ; Demaine, Hajiaghayi, 2008 .
  23. ↑ Frick, Grohe, 2001 .
  24. ↑ Grigorjev, Bodlaender, 2007 .

Linkek