Träddjup (grafteori)

I grafteorin är träddjupet för en sammankopplad oriktad graf G den numeriska invarianten av G , den minsta höjden på Tremaux-trädet för en supergraf av G . Detta invarianta och relaterade begrepp förekommer under olika namn i litteraturen, inklusive vertexrankningsnummer, ordnat kromatiskt tal och minsta trädelimineringshöjd. Konceptet ligger också nära sådana begrepp som den cykliska rangordningen för riktade grafer och iterationshöjden för språket i reguljära språk [1] [2] ; [3] . Intuitivt, medan trädbredden på en graf mäter hur långt grafen är från trädet, mäter trädets djup hur långt grafen är från stjärnan.

Definitioner

Träddjupet för en graf G kan definieras som den minsta höjden av en skog F med egenskapen att vilken kant av G som helst förbinder ett par hörn sammankopplade av en förälder-barn-relation i F [4] . Om G är kopplat måste denna skog vara ett enda träd. Skogen behöver inte vara en subgraf till G , men om den är det så är det ett Tremaux-träd för G .

Uppsättningen av förälder-barn-par i F bildar en trivialt perfekt graf , och höjden på F är storleken på den största klicken i denna graf. Sålunda kan träddjupet alternativt definieras som storleken på den största klicken i den trivialt perfekta supergrafen av G , som är en spegelbild av trädbredden , som är en mindre än storleken på den största klicken i den ackordala supergrafen av G [ 5]

En annan definition är följande:

där V är uppsättningen av hörn i grafen G och är de sammankopplade komponenterna i G [6] . Denna definition speglar den cykliska rangdefinitionen för riktade grafer, som använder stark anslutning och starkt anslutna komponenter istället för oriktade anslutningar och anslutna komponenter.

Djupet på ett träd kan bestämmas med hjälp av graffärgning . En centrerad graffärgning är en vertexfärgning som har egenskapen att alla anslutna genererade subgrafer har en färg som förekommer exakt en gång. Då är trädets djup den minsta storleken på färgerna som krävs för en centrerad färgning av grafen. Om F är en skog på höjden d som har egenskapen att valfri kant på G förbinder en förfader och ett barn i trädet, så kan man få en centrerad färgning av G med d färger genom att färga varje vertex med ett färgnummer lika med avstånd från roten i F [7] .

Slutligen kan man definiera det i termer av ett chip-spel . Mer exakt, precis som spelet "polis-rånare" . Föreställ dig följande spel på en oriktad graf. Det är två spelare, en rånare och en polis. Rånaren har en bit, som han flyttar längs kanterna på grafen. Polismannen har ett obegränsat antal marker, men han vill minimera antalet marker som används. Polismannen kan inte flytta sina pjäser placerade på grafen. Spelet går så här. Rånaren placerar sin pjäs, sedan berättar polisen var han vill placera nästa pjäs och rånaren kan sedan flytta sin pjäs längs kanterna, men inte över de ockuperade hörnen. Spelet slutar när polismannen placerar nästa pjäs ovanpå rånarpjäsen. Träddjupet för en given graf bestämmer det minsta antal marker som krävs för en garanterad vinst [8] [9] . För stjärnor räcker det med två polletter - placera den första poletten i mitten av stjärnan, tvinga rånaren att flytta in i någon stråle, och placera sedan den andra poletten på rånarens pollett. För en väg med hörn använder polisen en binär sökstrategi som garanterar att inga fler tokens används.

Exempel

Träddjupet för en komplett graf är lika med antalet av dess hörn, i vilket fall den enda möjliga skogen F för vilken ett par av hörn måste vara i en förfader-barn-relation är en enda väg. På liknande sätt är träddjupet för en komplett tvådelad graf K x , y min( x , y ) + 1, och hur vi än placerar hörnen måste skogens F löv ha minst min( x , y ) förfäder i F . Skogen på vilken min( x , y ) + 1 nås kan konstrueras genom att bilda en bana från hörnen på den mindre delen av grafen, och hörnen på den större delen bildar bladen på trädet F kopplade till den nedre delen av grafen. spetsen på banan.

Djupet på ett vägträd med n hörn är exakt . En skog F som representerar denna väg med detta djup kan bildas genom att placera roten i mitten av banan F och fortsätta rekursionen i två mindre banor på vardera sidan om roten [10] .

Trädens djup och förhållande till trädets bredd

Varje skog med n hörn har träddjup O(log  n ). För en skog kan man alltid hitta ett konstant antal hörn, vars borttagande ger en skog som kan delas upp i två mindre delskogar med högst 2 n /3 hörn vardera. Genom att rekursivt dela dessa två undervegetationer kan man lätt nå en logaritmisk övre gräns för träddjupet. Samma teknik, tillämpad på grafträdsupplösning , visar att om trädbredden för en n -vertexgraf G är t , så är träddjupet för G O( t  logn  ) . [11] [12] Eftersom ytterplanära grafer , parallellsekventiella grafer och Halin-grafer har en begränsad trädbredd, har de alla också ett maximalt logaritmiskt träddjup.

I den andra riktningen överstiger trädets bredd på en graf inte dess träddjup. Närmare bestämt, trädets bredd överstiger inte grafens vägbredd , som är högst en mindre än dess träddjup [11] [13] .

Räkna minderåriga

En mindre av en graf G är en annan graf som bildas av en subgraf av G genom att dra ihop några kanter. Djupet på ett träd är monotont i moll — vilken moll som helst i en graf G har ett träddjup som inte överstiger träddjupet för själva grafen G [14] . Sålunda, enligt Robertson-Seymour-satsen , för varje fast d , har uppsättningen grafer med träddjup som inte överstiger d ett ändligt antal förbjudna minderåriga .

Om C är en klass av grafer stängda under bildandet av mindreåriga, så har grafer i C träddjup om och endast om C inte inkluderar alla vägar [15] .

Genererade subgrafer

Träddjupet har ett nära samband med teorin om genererade subgrafer i en graf. I klassen av grafer med träddjup som mest d (för alla fasta naturliga d ), är egenskapen att vara en genererad subgraf väl kvasiordnad [16] . Huvudtanken bakom beviset på att denna koppling är helt kvasiordnad är att använda induktion på d . Skogar med höjden d kan tolkas som en sekvens av skogar med höjden d  − 1 (bildade genom att träd med höjden d rötts ner ) och Higmans lemma kan användas för att visa att dessa sekvenser är väl kvasi-ordnade.

Det följer av välkvasiordningen att varje egenskap hos en graf som är monoton i genererade subgrafer har ett ändligt antal förbjudna genererade subgrafer och därför kan kontrolleras i polynomtid på grafer med ett begränsat träddjup. Grafer med högst träddjup d har själva ett ändligt antal förbjudna underordnade subgrafer. Nexetril och Ossona de Mendez [17] visade 14 förbjudna subgrafer för grafer med trädbredd tre eller mindre (med hänvisning till 2007 års avhandling av Zdenek Dvorak).

Om C är en klass av grafer med begränsad degeneration , har grafer i C begränsad trädbredd om och endast om det finns en väg som inte kan visas som en genererad subgraf i C [15] .

Svårighet

Att bestämma ett träds djup är ett komplext beräkningsproblem - motsvarande igenkänningsproblem är NP-komplett [18] . Problemet förblir NP-komplett för tvådelade grafer [1] , såväl som för ackordsgrafer [19] .

På den positiva sidan kan ett träds djup beräknas i polynomtid för intervallgrafer [20] , såväl som för permutationsgrafer, trapetsformade grafer, cirkelbågsskärningsgrafer, cykliska permutationsgrafer och samjämförbarhetsgrafer av avgränsade dimensioner [21 ] . För oriktade träd kan träddjupet beräknas i linjär tid [22] [23] .

Bodlender, Gilbert, Hufsteinsson och Klox [11] föreslog en approximationsalgoritm för att hitta djupet på ett träd med en approximationskoefficient . Algoritmen bygger på att ett träds djup logaritmiskt beror på grafens trädbredd.

Eftersom ett träds djup är monotont i grafens molor, är problemet med att hitta det fixparametriskt lösbart — det finns en algoritm för att beräkna djupet på ett träd som fungerar i tiden , där d är djupet av den givna grafen och n är antalet hörn. Således kan problemet med att kontrollera om ett träds djup är större än d lösas i polynomtid för varje fast värde på d . Mer specifikt kan beroendet av n i denna algoritm göras linjärt på följande sätt: vi bygger ett djup-först sökträd och kontrollerar om trädets djup är större än 2 d eller inte. Om fler är trädets djup större än d och problemet är löst. Om inte, kan grunda sökträdsbyggnad användas för att bryta ner trädet , och standardtekniken för dynamisk programmering för grafer med avgränsad trädbredd kan användas för att beräkna djupet i linjär tid [24] . En mer sofistikerad linjär-tidslösningsalgoritm baserad på planariteten hos eliminerade minderåriga i djup-först-sökning föreslogs tidigare av Bodlander, Deogan, Jensen och Klox [1] . För en förbättrad parametrisk algoritm, se Reidl, Rossmanite, Villamil och Sikdar [25] .

Det är möjligt att beräkna träddjupet exakt för grafer vars djupvärde kan vara stort i O ( c n ) tid med en konstant c något mindre än 2. [26]

Anteckningar

  1. ↑ 1 2 3 Bodlaender et al, 1998 .
  2. ↑ Rossman, 2008 .
  3. ↑ Nešetřil, Ossona de Mendez, 2012 , sid. 116.
  4. ↑ Nešetřil, Ossona de Mendez, 2012 , sid. 115, Definition 6.1.
  5. ↑ David Eppstein. Diagramparametrar och klickar i supergrafer. — 2012 (15 november). Arkiverad från originalet den 9 januari 2014. .
  6. ↑ Nešetřil, Ossona de Mendez, 2012 , sid. 117, Lemma 6.1.
  7. ↑ Nešetřil, Ossona de Mendez, 2012 , sid. 125–128, avsnitt 6.5, "Centrerade färger".
  8. ↑ Gruber och Holzer 2008 , sid. Sats 5.
  9. ↑ Hunter, 2011 , Huvudsats.
  10. ↑ Nešetřil, Ossona de Mendez, 2012 , sid. 117, Formel 6.2.
  11. ↑ 1 2 3 Bodlaender et al, 1995 .
  12. ↑ Nešetřil, Ossona de Mendez, 2012 , sid. 124, följd 6.1.
  13. ↑ Nešetřil, Ossona de Mendez, 2012 , sid. 123.
  14. ↑ Nešetřil, Ossona de Mendez, 2012 , sid. 117, Lemma 6.2.
  15. ↑ 1 2 Nešetřil, Ossona de Mendez, 2012 , sid. 122, förslag 6.4.
  16. ↑ Nešetřil, Ossona de Mendez, 2012 , sid. 137, Lemma 6.13.
  17. ↑ Nešetřil, Ossona de Mendez, 2012 , sid. 138. Bild 6.6 på sid. 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 , sid. 138.
  25. ↑ Reidl et al, 2014 .
  26. ↑ Fomin et al, 2013 .

Litteratur