Træbredde (grafteori)

I grafteori er træbredden af ​​en urettet graf det tal, der er forbundet med grafen. Træbredde kan defineres på flere ækvivalente måder: som størrelsen af ​​det største sæt af hjørner i en trænedbrydning , som størrelsen af ​​den største klike i akkordkomplementet af en graf, som den maksimale escape-rækkefølge, når man beskriver en forfølgelsesspilstrategi på en graf, eller som den maksimale rækkefølge af en bramfugl , et sæt forbundne undergrafer, der rører hinanden. Træbredde bruges ofte som parameter i analysen af ​​den parametriske kompleksitet af på grafer. Grafer med træbredde højst k kaldes partielle k-træer . Mange andre velundersøgte graffamilier har også en begrænset træbredde.

Begrebet træbredde blev introduceret af Halin ( 1976 ) ud fra en anden parameter, Hadwiger-tallet , som træbredden deler en række egenskaber med. Treewidth blev senere genopdaget af Robertson og Seymour [1] og er siden blevet undersøgt af mange forfattere. [2]

Definition

En trænedbrydning af en graf G = ( V , E ) er et træ T , hvis toppunkter X 1 , ..., X n er delmængder af V , der opfylder følgende egenskaber [3] :

  1. Unionen af ​​alle mængder X i er lig med V . Ethvert toppunkt på grafen er således indeholdt i mindst ét ​​sæt.
  2. Hvis X i og X j begge indeholder toppunkt v , så indeholder alle andre toppunkter i træet X k på den (unikke) sti fra X i til X j også v . Dette svarer til at sige, at hjørnerne af træet, der indeholder v , danner et forbundet undertræ af T .
  3. For enhver kant ( v , w ) af G eksisterer der en delmængde Xi , der indeholder både v og w . Det vil sige, at toppunkter er tilstødende i en graf, hvis kun de tilsvarende undertræer har et fælles toppunkt i træet T .

Bredden af ​​et trænedbrydning er størrelsen af ​​dets største sæt X i minus en (således har træer en trænedbrydningsbredde på 1).

Træbredden tw( G ) af G er minimumsbredden af ​​alle mulige nedbrydninger af G . I denne definition trækkes man fra størrelsen af ​​sættet, så træets træbredde er lig med én.

På samme måde er træbredden af ​​G en mindre end størrelsen af ​​den største klike i akkordgrafen med det mindste kliktal, der indeholder G. En akkordgraf med dette kliknummer kan opnås ved at tilføje kanter til G mellem to vilkårlige hjørner, hvis begge tilhører det samme (mindst et) sæt X i .

Træbredde kan også beskrives i form af shelters , funktioner, der beskriver unddragelsesstrategier for nogle grafforfølgelsesspil . En graf G har træbredde k , hvis og kun hvis den har et læ af størrelsesordenen k + 1, men ingen læ af højere orden. Her er ly af orden k + 1 funktionen β , der afbilder hvert sæt X med højst k toppunkter i G til en af ​​de forbundne komponenter i grafen G \ X og som opfylder monotoniegenskaben

kl .

En lignende beskrivelse kan også laves ved hjælp af brombær , en familie af forbundne grafer, der er tangenter (hvilket betyder, at de enten deler et fælles toppunkt eller er forbundet med en kant). [4] En delmængde af G vil siges at dække (eller dække) et brombær, hvis det skærer hvert element i brombæret. Rækkefølgen af ​​brombær er den mindste dækning , og træbredden af ​​grafen er en mindre end den maksimale rækkefølge for brombærene.

Eksempler

Enhver komplet graf K n har træbredde n  − 1. Dette ses nemmest ved at bruge definitionen af ​​træbredde i form af akkordgrafer - en komplet graf er allerede akkordal, og tilføjelse af kanter kan ikke reducere størrelsen af ​​den største klike.

Forbundne grafer med mindst to toppunkter har træbredde 1, hvis og kun hvis det er et træ. Et træ har træbredde en af ​​samme grund, som komplette grafer har (nemlig de er akkordale og har en maksimal klike på størrelse to). Omvendt, hvis en graf har en cyklus, så indeholder ethvert kordalkomplement af grafen mindst én trekant, hvilket indebærer, at træbredden af ​​grafen er mindst to.

Begrænset træbredde

Familier af trægrafer med afgrænset bredde

For enhver fast konstant k kaldes grafer med højst træbredde k partielle k-træer . Andre familier af grafer med begrænset træbredde omfatter kaktusser , pseudoskove , parallel-serielle grafer , ydre planære grafer , Halin -grafer og Apollonius-grafer [5] . Kontrolflowgraferne , der vises i oversættelsen af ​​strukturerede programmer , har også en begrænset træbredde, hvilket gør det muligt at udføre nogle opgaver, såsom registerallokering , effektivt . [6]

Plane grafer har ikke en afgrænset træbredde, fordi et n × n gitter er en plan graf, der har træbredde nøjagtigt n . Så hvis F er en familie af mindre lukkede grafer med afgrænset træbredde, kan den ikke inkludere alle plane grafer. Omvendt, hvis en plan graf ikke kan være en minor af grafer i familien F , så er der en konstant k sådan, at alle grafer i F højst har træbredde k . Følgende tre forhold svarer således til hinanden: [7]

  1. F er en familie af mindre lukkede grafer med afgrænset træbredde;
  2. En af det endelige antal forbudte mindreårige for F er plan;
  3. F er en familie af mindre lukkede grafer, herunder ikke-planære grafer.

Ulovlige mindreårige

For enhver endelig værdi af k kan grafer med højst træbredde k beskrives med et endeligt antal forbudte minorer , som hver indeholder mindst én plan graf.

For store værdier af k vokser antallet af forbudte mindreårige mindst som en eksponent for k . [10] Imidlertid er de kendte øvre grænser for størrelsen og antallet af forbudte mindreårige meget højere end denne nedre grænse. [elleve]

Algoritmer

Træbreddeberegning

At bestemme om en given graf G har træbredde højst k er et NP-komplet problem. [12] Men hvis k er fast, kan grafer med træbredde k findes og den tilsvarende trænedbrydning konstrueres i lineær tid. [13] Algoritmens udførelsestid afhænger eksponentielt af k .

I praksis kan Shoikhet og Geigers algoritme ( Shoikhet, Geiger 1997 ) finde træbredden af ​​grafer op til 100 toppunkter i størrelse og træbredde op til 11 ved at finde akkordkomplementet af disse grafer med optimal træbredde.

Løsning af andre problemer på grafer med en lille træbredde

I begyndelsen af ​​halvfjerdserne af det tyvende århundrede blev det bemærket, at en stor klasse af kombinatoriske optimeringsproblemer på grafer kan løses effektivt ved hjælp af ikke-seriel dynamisk programmering, hvis grafen har en afgrænset dimension , [14] en parameter relateret til træbredden. Senere, i slutningen af ​​1980'erne [15] opdagede en række matematikere uafhængigt af hinanden, at mange algoritmiske problemer, der er NP-komplette for vilkårlige grafer, effektivt kan løses ved dynamisk programmering for grafer med afgrænset træbredde ved hjælp af en trænedbrydning af disse grafer.

Som et eksempel kan problemet med at farvelægge en graf med træbredde k løses ved hjælp af dynamisk programmering på trænedbrydningen af ​​grafen. For hvert sæt X i af trænedbrydning og hver opdeling af toppunkter Xi i farver, bestemmer algoritmen, om den resulterende farvning er tilladelig, og om den kan udvides til alle afledte knudepunkter af nedbrydningen ved at kombinere information af samme type og gemme i disse hjørner. Den resulterende algoritme finder den optimale farvning af en graf med n toppunkter i O( k k  + O(1) n ) tid, hvilket gør dette problem parametrisk vanskeligt med en fast parameter .

Relaterede parametre

Sporbredde

Stibredden af ​​en graf har en meget lignende definition til træbredde via trænedbrydning, men er begrænset til kun de nedbrydninger, hvor det resulterende træ er en sti . En anden måde er at definere stibredden fra intervalgrafen, svarende til definitionen af ​​træbredden fra akkordgraferne. Som en konsekvens heraf er stibredden af ​​en graf mindst lige så stor som dens træbredde, men den kan kun være større med en logaritmisk faktor. [5] En anden parameter, grafbåndbredde , har en lignende definition, baseret på grafer med regelmæssige interval , og værdien af ​​parameteren er ikke mindre end stibredden. Derudover er der trædybde , et tal bundet til mindre lukkede grafer, hvis og kun hvis familien ikke inkluderer alle stigrafer, og degeneration , et mål for grafens sparsitet, der ikke overstiger træets bredde.

Gitter mindre dimension

Da træbredden af ​​et n  ×  n gitter er n , er træbredden af ​​G altid større end eller lig med størrelsen af ​​det største kvadratiske mindre gitter af G. Omvendt er der en funktion f sådan, at træets bredde ikke overstiger f ( r ), hvor r er størrelsen af ​​det største kvadratiske mindre gitter. De kendte grænser for f er dog ikke små: f skal være mindst Ω( r 2  log  r ) og højst 20 2 r 5 . [16] Strengere grænser er kendt for afgrænsede familier af grafer, hvilket giver effektive algoritmer til mange optimeringsproblemer på disse graffamilier ifølge den todimensionelle teori . [17] Halins gittersætning giver en analog af forholdet mellem træets bredde og gitterets mindre størrelse for ubundne grafer. [atten]

Diameter og lokal træbredde

En familie F af grafer siges at have en begrænset lokal træbredde , hvis træbredden af ​​graferne i familien er afgrænset over af en funktion af diameteren . Hvis en mindreårig af et familiemedlem F også er i F , så har F afgrænset lokal træbredde, hvis og kun hvis en af ​​de forbudte mindreårige i F er en topgraf . [19] Det originale bevis for dette resultat viste, at træbredden i en familie af grafer uden mindreårige, der er vertex-grafer, ikke vokser hurtigere end det dobbelte af eksponenten af ​​diameteren. [20] Dette blev senere reduceret til blot en eksponentiel [17] og til sidst til en lineær grænse. [21] Afgrænset lokal træbredde er tæt forbundet med den algoritmiske teori om todimensionalitet [22] , og enhver grafegenskab, der kan defineres i form af førsteordens logik , kan beregnes for grafer fra en familie, der gør det ikke indeholde mindre-vertex-grafer, i kun lidt superlineær tid. [23]

Nogle klasser af grafer, der ikke er lukket under mindreårige, har stadig en begrænset lokal træbredde. Det drejer sig især om 1-plane grafer , det vil sige grafer, der kan tegnes på planet med højst én skæring af en kant, og mere generelle grafer, der kan tegnes på en overflade af begrænset slægt med et begrænset antal kant kryds. Som i tilfældet med familier af mindre lukkede grafer med begrænset lokal træbredde, baner denne egenskab vejen for effektive tilnærmelsesalgoritmer til sådanne grafer. [24]

Hadwiger nummer og S -funktioner

Halin ( 1976 ) definerer en klasse af grafparametre, som han kalder S -funktioner, og denne klasse inkluderer bredden af ​​et træ. Disse funktioner har grafer som deres domæne og heltal som deres domæne, og de skal have værdien nul på grafer uden kanter og skal være monotone med hensyn til minor , dvs. stige med én, når der tilføjes et nyt toppunkt, der støder op til alle tidligere hjørner. Det kræves også, at værdien af ​​graffunktionen er lig med den største af værdierne på to delmængder, hvis skæringspunkt er både en toppunktseparator og en klike på samme tid. Sættet af alle sådanne funktioner danner et komplet gitter med hensyn til elementvise minimerings- og maksimeringsoperationer. Det øverste element i dette gitter er træbredden, og det nederste element er Hadwiger-tallet , størrelsen af ​​den maksimale komplette mol i den givne graf.

Noter

  1. ↑ Robertson, Seymour, 1984
  2. ↑ Diestel, 2005 s. 354–355
  3. ↑ Diestel, 2005 , afsnit 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 . For Ω i den nedre grænse, se "O" stor og "o" lille .
  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 .

Links