Tremaux-træet i en ikke-rettet graf G er et spændingstræ med rodfæstet spænding i G med den egenskab, at to tilstødende hjørner i G er relateret til hinanden af en forfader/efterkommer-relation. Alle dybde-første søgetræer og alle Hamiltonske stier er Tremo-træer. Tremaux-træer er opkaldt efter Charles Pierre Tremaux, en fransk forfatter fra det 19. århundrede, der brugte en variation af dybde-først-søgning som en labyrintudgangsstrategi [1] [2] . Tremaux-træer kaldes også normalspændende træer , især i sammenhæng med uendelige grafer [3] .
I endelige grafer, selvom dybde-først-søgning i sig selv er sekventiel, kan Tremo-træer bygges af en randomiseret parallel algoritme med RNC -kompleksitetsklasse . Tremo-træer kan bruges til at bestemme trædybden af en graf, og som en del af planaritetstesten til at teste, om en graf er plan . At beskrive Tremo-træer med en andenordens unær graflogik [ gør det muligt effektivt at genkende orienteringsafhængige grafegenskaber for grafer med begrænset træbredde ved hjælp af Courcelles sætning .
Ikke alle uendelige grafer har et Tremo-træ, og grafer, der ikke har et sådant træ, kan beskrives af forbudte mindreårige . Et Tremo-træ findes i enhver graf med et tælleligt antal hjørner, selvom den uendelige dybde-første søgevariant ikke kan teste alle hjørnerne af grafen. I en uendelig graf skal et Tremaux-træ have nøjagtig én uendelig sti for hver stråle i grafen, og eksistensen af et Tremaux-træ karakteriserer grafer, hvis topologiske afslutninger, dannet ved at tilføje et punkt ved uendelighed for hver stråle, er metriske mellemrum .
I grafen vist nedenfor er et træ med kanterne 1–3, 2–3 og 3–4 et Tremaux-træ, hvis dets rod er toppunkt 1 eller toppunkt 2 – enhver kant på grafen hører til træet undtagen kant 1–2 , som (når du vælger den angivne rod) forbinder et forfader-efterkommer-par.
Men vælger vi node 3 eller node 4 som rod til det samme træ, får vi et rodfæstet træ, der ikke er et Tremo-træ, for med disse rødder vil node 1 og 2 ikke længere være en forfader/efterkommer.
Enhver endelig forbundet urettet graf har mindst ét Tremo-træ. Man kan konstruere et sådant træ ved at bruge dybde-først-søgning og forbinde hvert toppunkt (bortset fra søgningens indledende toppunkt) med et tidligere toppunkt, hvorfra det aktuelle toppunkt blev tilgået. Et træ bygget på denne måde er kendt som et dybde-først søgetræ. Hvis uv er en vilkårlig kant i grafen, og u er den tidligere af de to toppunkter, der nås af søgningen, så skal v tilhøre et undertræ af u 's efterkommere i dybde-første søgetræet, da søgningen vil finde toppunktet v efter behov ved at se på det pågældende træ enten fra et af hjørnernes undertræ eller direkte fra vertex u . Ethvert endeligt Tremo-træ kan dannes som et Dybde-Første-Første Træ - hvis T er et Tremo-træ af en endelig graf, og Dybde -Først Udforsk T 's efterkommere af hvert toppunkt, før du overvejer ethvert andet toppunkt, er dette nødvendigvis genererer T som et Dybde-Første-Første-Tree af grafen.
Et Tremo-træsøgningsproblem er P-complete , hvis det søges ved hjælp af en sekventiel dybde-først søgealgoritme, hvor naboerne til hvert vertex slås op i numerisk rækkefølge [4] . Det er dog muligt at finde et andet Tremo-træ ved hjælp af en randomiseret parallel algoritme , som viser, at konstruktionen af Tremo-træer tilhører RNC -kompleksitetsklassen [5] . Det er stadig uvist, om Tremo-træet kan konstrueres af en deterministisk parallelalgoritme, der tilhører NC -klassen [6] .
Det er muligt at udtrykke den egenskab, at sættet T af kanter med det valgte rodspids r danner et Tremaux-træ, i et-stedslogikken af grafer af anden orden, og et sådant udtryk kaldes MSO 2 . Denne egenskab kan udtrykkes som en kombination af følgende egenskaber:
Når først et Tremo-træ er blevet identificeret på denne måde, kan man beskrive orienteringen af en given graf i en et-steds andenordens logik ved at specificere et sæt kanter, der er orienteret fra forælder til barn. Kanter, der ikke er inkluderet i dette sæt, skal være orienteret i den modsatte retning. Denne teknik gør det muligt at beskrive en grafs egenskaber ved hjælp af orientering i en et-steds andenordens logik, hvilket gør det muligt at teste disse egenskaber effektivt på grafer med en begrænset træbredde ved hjælp af Courcelles sætning [7] .
Hvis en graf har en Hamiltonsk sti , så er den sti (med roden som en af dens ender) også et Tremaux-træ. Sættet af urettede grafer, som ethvert Tremaux-træ har denne form for, består af cyklusser , komplette grafer og afbalancerede komplette todelte grafer [8] .
Tremo træer er tæt forbundet med begrebet trædybde . Trædybden af G kan defineres som det mindste tal d , således at G kan indlejres som en undergraf af H , der har et Tremaux-træ T med dybden d . Den afgrænsede dybde af et træ i en familie af grafer svarer til eksistensen af en sti, der ikke kan optræde som en graf minor i familien. Mange komplekse computerproblemer på grafer har fast-parametriske løselige -algoritmer, hvis de parametriseres af trædybden [9] .
Tremaux-træer spiller også en nøglerolle i De Freysex-Rosenstil planaritetstesten for at teste om en graf er plan . Ifølge dette kriterium er en graf G plan, hvis de resterende kanter for ethvert Tremo-træ T af graf G kan placeres til venstre og højre for træet, hvilket forhindrer kanterne i at krydse (af denne grund kan du nogle gange se navnet "LP algorithm" - en forkortelse af Left / Right) [10] [11] .
Ikke enhver uendelig graf har et normalt spændingstræ. For eksempel har en komplet graf på et utalligt sæt af hjørner ikke et normalt spændende træ - et sådant træ i en komplet graf kan kun være en sti, men en sti har kun et tælleligt antal hjørner. Men enhver graf på et tælleligt sæt af hjørner har et normalt spændingstræ [3] .
Selv i tællelige grafer kan dybde-først-søgning mislykkes, når man ser på hele grafen [3] , og ikke ethvert normalt spændingstræ kan genereres ved dybde-først-søgning - for at være et dybde-først søgetræ, et tælligt normalt spændingstræ skal kun have én uendelig sti, eller én en node med et uendeligt antal naboer (men ikke begge tilfælde på samme tid).
Hvis en uendelig graf G har et normalt spændende træ, så har enhver tilsluttet mol af G også . Dette indebærer, at grafer med normalt spændende træer kan beskrives af forbudte mindreårige . En af de to klasser af forbudte mindreårige består af todelte grafer , hvor den ene del er tællig og den anden utællig, og ethvert toppunkt har uendelig grad. En anden klasse af forbudte mindreårige består af visse grafer afledt af Aronshine-træer [12] .
Detaljerne i denne beskrivelse afhænger af valget af mængdeteoretisk aksiomatik brugt i formaliseringen af matematik. Især i modeller for mængdeteori, hvor Martins aksiom er sandt, men kontinuumhypotesen ikke er sand, kan klassen af todelte grafer erstattes af en enkelt forbudt mol. Men for modeller, hvor kontinuumhypotesen er sand, indeholder denne klasse grafer, der er uforlignelige i rækkefølgen af mindreårige [13] .
Normalspændende træer er tæt beslægtet med strålerne en uendelig graf, ækvivalensklasserne af uendelige stier, der går i samme retning. Hvis en graf har et normalt spændende træ, skal det træ have nøjagtig en uendelig bane for hver stråle på grafen [14] .
En uendelig graf kan bruges til at danne et topologisk rum ved at behandle selve grafen som et simpelt kompleks og tilføje et uendeligt punkt for hver stråle af grafen. Med en sådan topologi har en graf et normalt spændingstræ, hvis og kun hvis dets toppunktssæt kan opdeles i en tællig forening af lukkede sæt . Desuden kan dette topologiske rum repræsenteres af et metrisk rum, hvis og kun hvis grafen har et normalt spændingstræ [14] .