Trædybde (grafteori)

I grafteori er trædybden af ​​en forbundet urettet graf G den numeriske invariant af G , den mindste højde af Tremaux-træet for en supergraf af G . Denne invariante og beslægtede begreber forekommer under forskellige navne i litteraturen, herunder toppunktsrangeringsnummer, ordnet kromatisk tal og minimum træelimineringshøjde. Begrebet er også tæt på sådanne begreber som den cykliske rang af rettede grafer og iterationshøjden af ​​sproget i regulære sprog [1] [2] ; [3] . Intuitivt, mens træbredden på en graf måler, hvor langt grafen er fra træet, måler træets dybde, hvor langt grafen er fra stjernen.

Definitioner

Trædybden af ​​en graf G kan defineres som minimumshøjden af ​​en skov F med den egenskab, at en hvilken som helst kant af G forbinder et par hjørner forbundet af en forældre-barn-relation i F [4] . Hvis G er forbundet, skal denne skov være et enkelt træ. Skoven behøver ikke at være en undergraf af G , men hvis den er det, så er det et Tremaux-træ for G .

Sættet af forældre-barn-par i F danner en trivielt perfekt graf , og højden af ​​F er på størrelse med den største klike på denne graf. Trædybden kan således alternativt defineres som størrelsen af ​​den største klike i den trivielt perfekte supergraf af G , som er et spejlbillede af træbredden , som er en mindre end størrelsen af ​​den største klike i den akkordale supergraf af G [ 5]

En anden definition er følgende:

hvor V er sættet af hjørner af grafen G og er de forbundne komponenter af G [6] . Denne definition afspejler den cykliske rangdefinition af rettede grafer, som bruger stærk forbindelse og stærkt forbundne komponenter i stedet for urettede tilslutningsmuligheder og forbundne komponenter.

Dybden af ​​et træ kan bestemmes ved hjælp af graffarvning . En centreret graffarvning er en toppunktfarvning, der har den egenskab, at enhver forbundet genereret undergraf har en farve, der forekommer nøjagtigt én gang. Så er træets dybde den mindste størrelse af de farver, der kræves for en centreret farvning af grafen. Hvis F er en skov med højden d , der har den egenskab, at enhver kant af G forbinder en forfader og et barn i træet, så kan man opnå en centreret farvning af G med d farver ved at farve hvert hjørne med et farvetal lig med afstand fra roden i F [7] .

Endelig kan man definere det i form af et chipspil . Mere præcist, præcis som spillet "cops-robbers" . Forestil dig følgende spil på en urettet graf. Der er to spillere, en røver og en politimand. Røveren har et stykke, som han flytter langs grafens kanter. Politimanden har et ubegrænset antal jetoner, men han ønsker at minimere antallet af brugte jetoner. Politimanden kan ikke flytte sine brikker placeret på grafen. Spillet går sådan her. Røveren placerer sin brik, så fortæller politibetjenten, hvor han vil placere den næste brik, og røveren kan så flytte sin brik langs kanterne, men ikke over de besatte hjørner. Spillet slutter, når politimanden placerer den næste brik oven på røverbrikken. Trædybden af ​​en given graf bestemmer det mindste antal jetoner, der kræves for en garanteret gevinst [8] [9] . For stjerner er to tokens nok - placer det første token i midten af ​​stjernen, og tving røveren til at flytte ind i en stråle, og placer derefter den anden token på røverens token. For en sti med hjørner bruger politibetjenten en binær søgestrategi , der garanterer, at der ikke bruges flere tokens.

Eksempler

Trædybden af ​​en komplet graf er lig med antallet af dens toppunkter, i hvilket tilfælde den eneste mulige skov F , for hvilken et par hjørner skal være i et forfader-barn-forhold, er en enkelt sti. På samme måde er trædybden af ​​en komplet todelt graf K x , y min( x , y ) + 1, og uanset hvordan vi placerer toppunkterne, skal skovens Fs blade have mindst min( x , y ) forfædre i F . Skoven, hvorpå min( x , y ) + 1 nås, kan konstrueres ved at danne en sti fra hjørnerne i den mindre del af grafen, og hjørnerne i den største del danner bladene på træet F forbundet med den nederste del. toppen af ​​stien.

Dybden af ​​et stitræ med n toppunkter er nøjagtig . En skov F , der repræsenterer denne sti med denne dybde, kan dannes ved at placere roden i midten af ​​stien F og fortsætte rekursionen i to mindre stier på hver side af roden [10] .

Træernes dybde og forhold til træets bredde

Enhver skov med n toppunkter har trædybde O(log  n ). For en skov kan man altid finde et konstant antal knudepunkter, hvis fjernelse giver en skov, der kan opdeles i to mindre underskove med maksimalt 2 n /3 spidser hver. Ved rekursivt at opdele disse to underskov, kan en logaritmisk øvre grænse for trædybden let nås. Den samme teknik, anvendt til graftrænedbrydning , viser, at hvis træbredden af ​​en n -vertex graf G er t , så er trædybden af ​​G O( t  log  n ). [11] [12] Fordi ydreplanære grafer , parallel-sekventielle grafer og Halin-grafer har en afgrænset træbredde, har de alle også en maksimal logaritmisk trædybde.

I den anden retning overstiger træbredden af ​​en graf ikke dens trædybde. Mere præcist overstiger træets bredde ikke kurvens stibredde , som højst er en mindre end træets dybde [11] [13] .

Tæl mindreårige

En mindre af en graf G er en anden graf dannet ud fra en undergraf af G ved at trække nogle kanter sammen. Dybden af ​​et træ er monotont i mol - enhver mol af en graf G har en trædybde, der ikke overstiger trædybden af ​​selve grafen G [14] . Således, ved Robertson-Seymour-sætningen , for enhver fast d , har sættet af grafer med trædybde, der ikke overstiger d , et begrænset antal forbudte mindreårige .

Hvis C er en klasse af grafer lukket under dannelsen af ​​mindreårige, så har grafer i C trædybde, hvis og kun hvis C ikke inkluderer alle stier [15] .

Genererede undergrafer

Trædybden har et tæt forhold til teorien om genererede undergrafer af en graf. I klassen af ​​grafer med højst trædybde d (for enhver fast naturlig d ), er egenskaben ved at være en genereret undergraf vel kvasi-ordnet [16] . Hovedtanken bag beviset for, at denne forbindelse er fuldstændig kvasi-ordnet, er at bruge induktion på d . Skove med højden d kan tolkes som en sekvens af skove med højden d  − 1 (dannet ved at fjerne træer med højden d ) og Higmans lemma kan bruges til at vise, at disse sekvenser er godt kvasi-ordnede.

Det følger af brønd-kvasi-ordningen, at enhver egenskab ved en graf, der er monoton i genererede undergrafer, har et begrænset antal forbudte genererede undergrafer, og derfor kan kontrolleres i polynomiel tid på grafer med en afgrænset trædybde. Grafer med højst trædybde d har selv et begrænset antal forbudte underordnede undergrafer. Nexetril og Ossona de Mendez [17] viste 14 forbudte undergrafer for grafer med træbredde tre eller mindre (med reference til 2007-afhandlingen af ​​Zdenek Dvorak).

Hvis C er en klasse af grafer med afgrænset degeneration , har grafer i C begrænset træbredde, hvis og kun hvis der er en sti, der ikke kan vises som en genereret undergraf i C [15] .

Sværhedsgrad

At bestemme dybden af ​​et træ er et komplekst beregningsproblem - det tilsvarende genkendelsesproblem er NP-komplet [18] . Problemet forbliver NP-komplet for todelte grafer [1] såvel som for akkordgrafer [19] .

På den positive side kan dybden af ​​et træ beregnes i polynomiel tid for intervalgrafer [20] såvel som for permutationsgrafer, trapezgrafer, cirkelbueskæringsgrafer, cykliske permutationsgrafer og grafer for samsammenlignelighed af afgrænsede dimensioner [21 ] . For ikke-rettede træer kan trædybden beregnes i lineær tid [22] [23] .

Bodlender, Gilbert, Hufsteinsson og Klox [11] foreslog en tilnærmelsesalgoritme til at finde dybden af ​​et træ med en tilnærmelseskoefficient . Algoritmen er baseret på, at et træs dybde logaritmisk afhænger af grafens træbredde.

Da dybden af ​​et træ er monotont i grafens mol, er problemet med at finde det fast-parametrisk løseligt — der er en algoritme til at beregne dybden af ​​et træ, der fungerer i tid , hvor d er dybden af den givne graf, og n er antallet af hjørner. For enhver fast værdi af d kan problemet med at kontrollere, om et træs dybde er større end d , således løses i polynomisk tid . Mere specifikt kan afhængigheden af ​​n i denne algoritme gøres lineær på følgende måde: vi bygger et dybde-først søgetræ og tjekker om træets dybde er større end 2 d eller ej. Hvis mere, er træets dybde større end d , og problemet er løst. Hvis ikke, kan lavvandet søgetræbygning bruges til at dekomponere træet , og standard dynamisk programmeringsteknik for afgrænsede træbreddegrafer kan bruges til at beregne dybden i lineær tid [24] . En mere sofistikeret lineær-tidsløsningsalgoritme baseret på planheden af ​​eliminerede mindreårige i dybde-først-søgning blev tidligere foreslået af Bodlander, Deogan, Jensen og Klox [1] . For en forbedret parametrisk algoritme, se Reidl, Rossmanite, Villamil og Sikdar [25] .

Det er muligt at beregne trædybden nøjagtigt for grafer, hvis dybdeværdi kan være stor i O ( c n ) tid med en konstant c lidt mindre end 2. [26]

Noter

  1. ↑ 1 2 3 Bodlaender et al, 1998 .
  2. ↑ Rossman, 2008 .
  3. ↑ Nešetřil, Ossona de Mendez, 2012 , s. 116.
  4. ↑ Nešetřil, Ossona de Mendez, 2012 , s. 115, Definition 6.1.
  5. ↑ David Eppstein. Graf parametre og kliker i supergrafer. — 2012 (15. november). Arkiveret fra originalen den 9. januar 2014. .
  6. ↑ Nešetřil, Ossona de Mendez, 2012 , s. 117, Lemma 6.1.
  7. ↑ Nešetřil, Ossona de Mendez, 2012 , s. 125–128, afsnit 6.5, "Centrerede farvelægninger".
  8. ↑ Gruber og Holzer 2008 , s. Sætning 5.
  9. ↑ Hunter, 2011 , Hovedsætning.
  10. ↑ Nešetřil, Ossona de Mendez, 2012 , s. 117, Formel 6.2.
  11. ↑ 1 2 3 Bodlaender et al, 1995 .
  12. ↑ Nešetřil, Ossona de Mendez, 2012 , s. 124, konsekvens 6.1.
  13. ↑ Nešetřil, Ossona de Mendez, 2012 , s. 123.
  14. ↑ Nešetřil, Ossona de Mendez, 2012 , s. 117, Lemma 6.2.
  15. ↑ 1 2 Nešetřil, Ossona de Mendez, 2012 , s. 122, forslag 6.4.
  16. ↑ Nešetřil, Ossona de Mendez, 2012 , s. 137, Lemma 6.13.
  17. ↑ Nešetřil, Ossona de Mendez, 2012 , s. 138. Figur 6.6 på s. 139.
  18. ↑ Pothen, 1988 .
  19. ↑ Dereniowski, Nadolski, 2006 .
  20. ↑ Aspvall, Heggernes, 1994 .
  21. ↑ Deogun et al., 1999 .
  22. ↑ Iyer et al., 1988 .
  23. ↑ Schaffer, 1989 .
  24. ↑ Nešetřil, Ossona de Mendez, 2012 , s. 138.
  25. ↑ Reidl et al., 2014 .
  26. ↑ Fomin et al, 2013 .

Litteratur