Trädets bredd (grafteori)

I grafteorin är trädbredden för en oriktad graf numret som hör ihop med grafen. Trädbredd kan definieras på flera likvärdiga sätt: som storleken på den största uppsättningen av hörn i en trädnedbrytning , som storleken på den största klicken i ackordskomplementet av en graf, som den maximala flyktordningen när man beskriver en jaktspelsstrategi på en graf, eller som den maximala ordningen för en torn , en uppsättning anslutna subgrafer som berör varandra. Trädbredd används ofta som en parameter i analysen av den parametriska komplexiteten hos på grafer. Grafer med trädets bredd högst k kallas partiella k-träd . Många andra väl studerade graffamiljer har också en begränsad trädbredd.

Begreppet trädbredd introducerades av Halin ( 1976 ) utifrån en annan parameter, Hadwiger-talet , som trädbredden delar ett antal egenskaper med. Treewidth återupptäcktes senare av Robertson och Seymour [1] och har sedan dess studerats av många författare. [2]

Definition

En trädupplösning av en graf G = ( V , E ) är ett träd T vars hörn X 1 , ..., X n är delmängder av V som uppfyller följande egenskaper [3] :

  1. Unionen av alla mängder X i är lika med V . Sålunda finns alla hörn på grafen i minst en uppsättning.
  2. Om X i och X j båda innehåller vertex v , så innehåller alla andra hörn i trädet X k på den (unika) banan från X i till Xj också v . Detta motsvarar att säga att hörnen på trädet som innehåller v bildar ett förbundet underträd av T .
  3. För varje kant ( v , w ) av G , finns det en delmängd Xi som innehåller både v och w . Det vill säga, hörn är intill varandra i en graf om endast motsvarande underträd har en gemensam vertex i trädet T .

Bredden på ett trädsönderfall är storleken på dess största uppsättning X i minus ett (således har träd en trädnedbrytningsbredd på 1).

Trädbredden tw( G ) av G är den minsta bredden av alla möjliga nedbrytningar av G . I denna definition subtraheras man från mängden storlek så att trädets bredd är lika med en.

På samma sätt är trädbredden för G en mindre än storleken på den största klicken i ackordsgrafen med det lägsta klicktalet som innehåller G. En ackordsgraf med detta klicknummer kan erhållas genom att lägga till kanter till G mellan två valfria hörn, om båda tillhör samma (minst en) uppsättning X i .

Trädbredd kan också beskrivas i termer av skyddsrum , funktioner som beskriver undvikandestrategier för vissa grafjaktspel . En graf G har trädbredden k om och endast om den har ett skydd av ordningen k + 1 men inget skydd av högre ordning. Här är skyddet av ordningen k + 1 funktionen β som avbildar varje mängd X med högst k hörn i G till en av de sammankopplade komponenterna i grafen G \ X och som uppfyller monotoniegenskapen

kl .

En liknande beskrivning kan också göras med hjälp av björnbär , en familj av sammankopplade grafer som är tangent (vilket betyder att de antingen delar en gemensam vertex eller är förbundna med en kant). [4] En delmängd av G kommer att sägas täcka (eller täcka) ett björnbär om det skär varje element i björnbäret. Ordningen på björnbäret är det minsta täcket , och trädbredden på grafen är en mindre än den maximala ordningen för björnbären.

Exempel

Vilken komplett graf K n som helst har trädbredd n  − 1. Detta är enklast att se med definitionen av trädbredd i termer av ackordsgrafer – en komplett graf är redan ackordal, och att lägga till kanter kan inte minska storleken på den största klicken.

Sammankopplade grafer med minst två hörn har trädbredd 1 om och endast om det är ett träd. Ett träd har trädbredd ett av samma anledning som kompletta grafer har (de är nämligen korda och har en maximal klick av storlek två). Omvänt, om en graf har en cykel, innehåller alla kordakomplement av grafen minst en triangel, vilket innebär att trädbredden på grafen är minst två.

Begränsad vedbredd

Familjer av trädgrafer med begränsad bredd

För varje fast konstant k kallas grafer med trädbredd som mest k partiella k-träd . Andra familjer av grafer med begränsad trädbredd inkluderar kaktusar , pseudoskogar , parallell-serie-grafer , ytterplanära grafer , Halin -grafer och Apollonius-grafer [5] . Styrflödesdiagrammen som visas i översättningen av strukturerade program har också en begränsad trädbredd, vilket gör att vissa uppgifter som registerallokering kan utföras effektivt . [6]

Plana grafer har inte en begränsad trädbredd eftersom ett n × n gitter är en plan graf som har trädbredd exakt n . Således, om F är en familj av mindre slutna grafer med begränsad trädbredd, kan den inte inkludera alla plana grafer. Omvänt, om någon plan graf inte kan vara en minor av grafer i familjen F , så finns det en konstant k så att alla grafer i F har trädbredd som mest k . Följande tre villkor är således likvärdiga med varandra: [7]

  1. F är en familj av mindre slutna grafer med avgränsad trädbredd;
  2. En av det ändliga antalet förbjudna minderåriga för F är plan;
  3. F är en familj av mindre slutna grafer, inklusive icke-planära grafer.

Illegala minderåriga

För vilket ändligt värde på k som helst kan grafer med högst k trädbredd beskrivas med ett ändligt antal förbjudna minorer , som var och en inkluderar minst en plan graf.

För stora värden på k växer antalet förbjudna minderåriga åtminstone som en exponent för k . [10] Emellertid är de kända övre gränserna för storleken och antalet förbjudna minderåriga mycket högre än denna nedre gräns. [elva]

Algoritmer

Beräkning av trädbredd

Att avgöra om en given graf G har trädbredd som mest k är ett NP-komplett problem. [12] Men om k är fast, kan grafer med trädbredd k hittas och motsvarande träduppdelning konstrueras i linjär tid. [13] Exekveringstiden för algoritmen beror exponentiellt på k .

I praktiken kan Shoikhet och Geigers algoritm ( Shoikhet, Geiger 1997 ) hitta trädbredden för grafer upp till 100 hörn i storlek och trädbredd upp till 11 genom att hitta ackordkomplementet för dessa grafer med optimal trädbredd.

Lösa andra problem på grafer med en liten trädbredd

I början av sjuttiotalet av 1900-talet märktes det att en stor klass av kombinatoriska optimeringsproblem på grafer kan lösas effektivt med hjälp av icke-seriell dynamisk programmering om grafen har en avgränsad dimension , [14] en parameter relaterad till trädbredden. Senare, i slutet av 1980-talet [15] upptäckte ett antal matematiker oberoende av varandra att många algoritmiska problem som är NP-kompletta för godtyckliga grafer effektivt kan lösas genom dynamisk programmering för grafer med avgränsad trädbredd med hjälp av en träduppdelning av dessa grafer.

Som ett exempel kan problemet med att färglägga en graf med trädbredden k lösas med hjälp av dynamisk programmering på träduppdelningen av grafen. För varje uppsättning X i av trädnedbrytning och varje uppdelning av hörn X i i färger, bestämmer algoritmen om den resulterande färgningen är tillåten och om den kan utökas till alla härledda hörn av sönderdelningen genom att kombinera information av samma typ och lagra i dessa hörn. Den resulterande algoritmen hittar den optimala färgningen av en graf med n hörn i O( k k  + O(1) n ) tid, vilket gör detta problem parametriskt svårt med en fast parameter .

Relaterade parametrar

Spårbredd

Vägbredden för en graf har en mycket liknande definition som trädbredd via trädsönderdelning, men är begränsad till endast de nedbrytningar där det resulterande trädet är en väg . Ett annat sätt är att definiera vägbredden från intervallgrafen, liknande definitionen av trädbredden från ackordsgraferna. Som en konsekvens är vägbredden för en graf minst lika stor som dess trädbredd, men kan bara vara större med en logaritmisk faktor. [5] En annan parameter, graph bandwidth , har en liknande definition, baserad på grafer med vanliga intervall , och parameterns värde är inte mindre än vägbredden. Dessutom finns det träddjup , ett tal som är bundet för mindre stängda grafer om och endast om familjen inte inkluderar alla vägdiagram, och degeneration , ett mått på grafens gleshet som inte överstiger trädets bredd.

Galler liten dimension

Eftersom trädbredden för ett n  ×  n gitter är n , är trädbredden för G alltid större än eller lika med storleken på det största kvadratiska mindre gittret av G . Omvänt finns det en funktion f så att trädets bredd inte överstiger f ( r ), där r är storleken på det största kvadratiska mindre gittret. De kända gränserna för f är dock inte små: f måste vara minst Ω( r 2  log  r ) och högst 20 2 r 5 . [16] Strängare gränser är kända för avgränsade familjer av grafer, vilket ger effektiva algoritmer för många optimeringsproblem på dessa graffamiljer enligt den tvådimensionella teorin . [17] Halins Lattice Theorem ger en analog av förhållandet mellan trädets bredd och gittrets mindre storlek för obegränsade grafer. [arton]

Diameter och lokal trädbredd

En familj F av grafer sägs ha en begränsad lokal trädbredd om trädbredden för graferna i familjen begränsas ovanför av en funktion av diametern . Om någon minderårig av en familjemedlem F också är i F , så har F begränsat lokal trädbredd om och endast om en av de förbjudna minderåriga i F är en apexgraf . [19] Det ursprungliga beviset för detta resultat visade att trädbredden i en familj av grafer utan minor som är vertexgrafer inte växer snabbare än två gånger exponenten för diametern. [20] Detta reducerades senare till bara en exponentiell [17] och slutligen till en linjär gräns. [21] Begränsad lokal trädbredd är nära relaterad till den algoritmiska teorin om tvådimensionalitet [22] , och alla grafegenskaper som kan definieras i termer av första ordningens logik kan beräknas för grafer från en familj som gör det inte innehålla grafer med mindre vertex, på endast något superlinjär tid. [23]

Vissa klasser av grafer som inte är stängda under minderåriga har fortfarande en begränsad lokal trädbredd. I synnerhet är dessa 1-planära grafer , det vill säga grafer som kan ritas på planet med högst en skärning av en kant, och mer generella grafer som kan ritas på en yta av begränsat släkte med ett begränsat antal kanter korsningar. Liksom i fallet med familjer med mindre slutna grafer med begränsad lokal trädbredd, banar den här egenskapen vägen för effektiva approximationsalgoritmer för sådana grafer. [24]

Hadwiger nummer och S -funktioner

Halin ( 1976 ) definierar en klass av grafparametrar som han kallar S -funktioner, och denna klass inkluderar bredden på ett träd. Dessa funktioner har grafer som sin domän och heltal som sin domän, och de måste ta värdet noll på grafer utan kanter och måste vara monotona med avseende på minor , det vill säga öka med ett när en ny vertex läggs till som ligger intill alla tidigare hörn. Det krävs också att värdet på graffunktionen är lika med det större av värdena på två delmängder vars skärningspunkt är både en vertexseparator och en klick samtidigt. Uppsättningen av alla sådana funktioner bildar ett komplett gitter med avseende på elementvisa minimerings- och maximeringsoperationer. Det översta elementet i detta gitter är trädbredden, och det nedre elementet är Hadwiger-talet , storleken på den maximala kompletta moll i den givna grafen.

Anteckningar

  1. ↑ Robertson, Seymour, 1984
  2. ↑ Diestel, 2005 s. 354–355
  3. ↑ Diestel, 2005 , avsnitt 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 . För Ω i den nedre gränsen, se "O" stor och "o" liten .
  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. ↑ Grigoriev, Bodlaender, 2007 .

Länkar