Treet (grafteori) - Tree (graph theory)

Trær
Et merket tre med 6 hjørner og 5 kanter.
Hjørner	v
Kanter	v  - 1
Kromatisk tall	2 hvis v > 1
Tabell over grafer og parametere

I grafteori er et tre en ikke -styrt graf der to to hjørner er koblet med nøyaktig en bane , eller tilsvarende en tilkoblet asyklisk, ikke -styrt graf. En skog er en ikke -styrt graf der to to hjørner er forbundet med høyst én bane, eller tilsvarende en asyklisk, ikke -dirigert graf, eller tilsvarende en usammenhengende forening av trær.

Et polytree (eller styrt tre eller orientert tre eller enkeltstående tilkoblet nettverk ) er en dirigert asyklisk graf (DAG) hvis underliggende uregulerte graf er et tre. En polyforest (eller rettet skog eller orientert skog ) er en rettet asyklisk graf hvis underliggende ikke -styrte graf er en skog.

De forskjellige typer datastrukturer referert til som trær i informatikk har underliggende grafer som er trær i grafteori, selv om slike datastrukturer generelt er forankrede trær . Et rotfestet tre kan bli rettet, kalt et rettet rotet tre , enten få alle kantene til å peke vekk fra roten-i så fall kalles det et arborescence eller ut-tre- eller få alle kantene til å peke mot roten-i så fall det kalles en anti-arborescence eller in-tree . Et rotet tre i seg selv har blitt definert av noen forfattere som en rettet graf. En forankret skog er en usammenhengende forening av rotfaste trær. En rotskog kan bli rettet, kalt en rettet skog , enten få alle kantene til å peke vekk fra roten i hvert rotet tre-i så fall kalles den en forgrening eller utskog- eller få alle kantene til å peke mot roten i hvert rotet tre-i så fall kalles det en forgrening eller i skogen .

Begrepet "tre" ble laget i 1857 av den britiske matematikeren Arthur Cayley .

Definisjoner

Tre

Et tre er en urettet graf G som tilfredsstiller noen av følgende likeverdige betingelser:

• G er tilkoblet og asyklisk (inneholder ingen sykluser).
• G er acyklisk, og en enkel syklus dannes hvis en kant tilsettes til G .
• G er koblet til, men skulle bli frakoplet hvis noen enkelt kant er fjernet fra G .
• G er tilkoblet og 3-toppunktet fullstendig graf K ₃ er ikke et mindre av G .
• Alle to hjørner i G kan kobles sammen med en unik enkel bane .

Hvis G har uendelig mange hjørner, si n av dem, så tilsvarer utsagnene ovenfor også noen av følgende betingelser:

• G er tilkoblet og har n - 1 kanter.
• G er koblet til, og hvert underbilde av G inkluderer minst ett toppunkt med null eller en hendende kant. (Det vil si at G er tilkoblet og 1-degenerert .)
• G har ingen enkle sykluser og har n - 1 kanter.

Som andre steder i grafteorien blir ordre-null-grafen (graf uten hjørner) generelt ikke ansett som et tre: mens den er vakuum forbundet som en graf (to hjørner kan kobles med en bane), er den ikke 0 -koblet (eller til og med (−1) -koblet) i algebraisk topologi, i motsetning til ikke-tomme trær, og bryter forholdet "ett mer toppunkt enn kanter". Den kan imidlertid betraktes som en skog som består av null trær.

En intern toppunktet (eller indre toppunktet eller gren toppunkt ) er et topp-punkt av grad på minst 2. På samme måte, en ytre toppunkt (eller ytre toppunkt , terminal toppunkt eller blad ) er et topp-punkt av en grad.

Et irreduserbart tre (eller serieredusert tre ) er et tre der det ikke er noen toppunkt i grad 2 (oppført i sekvens A000014 i OEIS ).

skog

En skog er en ikke -dirigert graf der to hjørner er forbundet med høyst én bane. Tilsvarende er en skog en ustyrt asyklisk graf, som alle sammenkoblede komponenter er trær; med andre ord, grafen består av en usammenhengende forening av trær. Som spesielle tilfeller er rekkefølgen-null-grafen (en skog som består av null trær), et enkelt tre og en kantløs graf, eksempler på skog. Siden for hvert tre V - E = 1 , kan vi enkelt telle antall trær i en skog ved å trekke fra forskjellen mellom totale hjørner og totale kanter. TV - TE = antall trær i en skog .

Polytree

Et polytree (eller styrt tre eller orientert tre eller enkeltstående tilkoblet nettverk ) er en dirigert asyklisk graf (DAG) hvis underliggende uregulerte graf er et tre. Med andre ord, hvis vi erstatter de rettede kantene med ikke -styrte kanter, får vi en ikke -styrt graf som er både tilkoblet og asyklisk.

Noen forfattere begrenser uttrykket "rettet tre" til tilfellet der kantene alle er rettet mot et bestemt toppunkt, eller alle rettet bort fra et bestemt toppunkt (se arborescence ).

Polyforest

En polyforest (eller rettet skog eller orientert skog ) er en rettet asyklisk graf hvis underliggende ikke -styrte graf er en skog. Med andre ord, hvis vi erstatter de rettede kantene med ikke -styrte kanter, får vi en ikke -styrt graf som er asyklisk.

Noen forfattere begrenser uttrykket "rettet skog" til tilfellet der kantene på hver tilkoblede komponent alle er rettet mot et bestemt toppunkt, eller alle rettet bort fra et bestemt toppunkt (se forgrening ).

Rotet tre

Et forankret tre er et tre der ett toppunkt har blitt betegnet som rot . Kantene på et rotfestet tre kan tildeles en naturlig orientering, enten vekk fra eller mot roten, i så fall blir strukturen et rettet rotet tre . Når et rettet rotet tre har en orientering vekk fra roten, kalles det et arborescence eller ut-tre ; når den har en orientering mot roten, kalles den en anti-arborescence eller in-tree . Den tre-orden er den delvise bestilling på topp-punktene av et tre med u < v hvis og bare hvis den unike bane fra roten til v passerer gjennom u . Et forankret tre T som er en undergrafi av en eller annen graf G er et normalt tre hvis endene på hver T-bane i G er sammenlignbare i denne tre-rekkefølgen ( Diestel 2005 , s. 15). Rotete trær, ofte med tilleggsstruktur som bestilling av naboene ved hvert toppunkt, er en sentral datastruktur i informatikk; se tre datastruktur .

I en sammenheng der trær vanligvis har en rot, kalles et tre uten noen bestemt rot et fritt tre .

Et merket tre er et tre der hvert toppunkt får en unik etikett. Hodepunktene til et merket tre på n hjørner er vanligvis gitt etikettene 1, 2, ..., n . Et rekursivt tre er et merket rotet tre der toppunktetikettene respekterer trerekkefølgen (dvs. hvis u < v for to hjørner u og v , så er etiketten til u mindre enn etiketten til v ).

I et rotfestet tre er overordnet til et toppunkt v toppunktet som er koblet til v på stien til roten; hvert toppunkt har en unik forelder unntatt roten som ikke har noen forelder. Et barn av et toppunkt v er et toppunkt som v er overordnet. En oppstigende av et toppunkt v er ethvert toppunkt som enten er overordnet til v eller (rekursivt) er oppstigeren til overordnet til v . En etterkommer av et toppunkt v er ethvert toppunkt som enten er barnet til v eller (rekursivt) er etterkommer av et av barna til v . Et søsken til et toppunkt v er ethvert annet toppunkt på treet som har samme forelder som v . Et blad er et toppunkt uten barn. Et indre toppunkt er et toppunkt som ikke er et blad.

Den høyde av et topp-punkt i en rotet tre er lengden av den lengste vei nedover til et blad fra dette hjørnet. Den høyde av treet er høyden av roten. Den dybde fra et topp-punkt er lengden av banen til sin rot ( rotbane ). Dette er ofte nødvendig ved manipulering av de forskjellige selvbalanserende trærne, spesielt AVL-trær . Roten har null dybde, blader har høyde null, og et tre med bare et toppunkt (derav både en rot og et blad) har dybde og høyde null. Vanligvis har et tomt tre (et tre uten hjørner, hvis slike er tillatt) dybde og høyde −1.

Et k-ary-tre er et rotfestet tre der hvert toppunkt har høyst k- barn. 2-ary-trær kalles ofte binære trær , mens 3-ary-trær noen ganger kalles ternære trær .

Bestilt tre

Et ordnet tre (eller plantre ) er et rotfestet tre der det er angitt en rekkefølge for barna til hvert toppunkt. Dette kalles et "plantre" fordi en rekkefølge av barna tilsvarer en innstøping av treet i planet, med roten på toppen og barna til hvert toppunkt lavere enn det toppunktet. Gitt en innstøping av et rotfestet tre i flyet, hvis man fikser en barns retning, si fra venstre til høyre, så gir en innebygging en ordning av barna. Omvendt, gitt et ordnet tre, og konvensjonelt tegning av roten på toppen, kan barnet hjørner i et ordnet tre trekkes fra venstre til høyre, noe som gir en i hovedsak unik plan innebygging.

Egenskaper

• Hvert tre er en todelt graf . En graf er todelt hvis og bare hvis den ikke inneholder sykluser med ulik lengde. Siden et tre ikke inneholder sykluser i det hele tatt, er det todelt.
• Hvert tre er en median graf .
• Hvert tre med bare mange mange hjørner er en plan graf .
• Hver tilkoblet graf G medgir en forbindelses tre , som er et tre som inneholder hvert topp-punkt av G og hvis kanter er kanter av G .
• Hver tilkoblet graf med bare mange mange hjørner innrømmer et normalt spennende tre ( Diestel 2005 , Prop. 8.2.4).
• Det finnes sammenhengende grafer med utallige mange hjørner som ikke innrømmer et normalt spennende tre ( Diestel 2005 , Prop. 8.5.2).
• Hvert endelig tre med n hjørner, med n > 1 , har minst to terminale hjørner (blader). Dette minimale antallet blader er karakteristisk for banediagrammer ; det maksimale tallet, n - 1 , oppnås bare av stjernediagrammer . Antall blader er minst den maksimale toppunktsgraden.
• For alle tre hjørner i et tre har de tre banene mellom dem nøyaktig ett toppunkt felles (dette toppunktet kalles medianen for disse tre hjørnene).
• Hvert tre har et senter bestående av ett toppunkt eller to tilstøtende hjørner. Senteret er midtpunktet eller midtre to hjørner i hver lengste bane. På samme måte har hvert n -vertex -tre et sentroid bestående av ett toppunkt eller to tilstøtende hjørner. I det første tilfellet deler fjerning av toppunktet treet i undertrær på færre enn n /2 hjørner. I det andre tilfellet deler fjerning av kanten mellom de to sentroidale hjørnene treet i to undertrær med nøyaktig n /2 hjørner.

Oppregning

Merkede trær

Cayleys formel sier at det er n ^{n −2} trær på n merkede hjørner. Et klassisk bevis bruker Prüfer -sekvenser , som naturligvis viser et sterkere resultat: Antall trær med hjørner 1, 2, ..., n av grader d ₁ , d ₂ , ..., d _n er multinomial koeffisient

${\ displaystyle {n-2 \ velg d_ {1} -1, d_ {2} -1, \ ldots, d_ {n} -1}.}$

Et mer generelt problem er å telle spennende trær i en ikke -styrt graf , som er adressert av matrisetre -setningen . (Cayleys formel er det spesielle tilfellet med å spanne trær i en komplett graf .) Det samme problemet med å telle alle undertrærne uavhengig av størrelse er #P-komplett i det generelle tilfellet ( Jerrum (1994) ).

Umerkede trær

Å telle antall umerkede gratis trær er et vanskeligere problem. Ingen lukket formel for antall t ( n ) trær med n hjørner opp til grafisomorfisme er kjent. De første verdiene til t ( n ) er

1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159,… (sekvens A000055 i OEIS ).

Otter (1948) beviste det asymptotiske estimatet

${\ displaystyle t (n) \ sim C \ alpha ^{n} n ^{-5/2} \ quad {\ text {as}} n \ to \ infty,}$

med verdiene C og α kjent for å være henholdsvis omtrent 0,534949606 ... og 2,95576528565 ... (sekvens A051491 i OEIS ). (Her betyr f ~ g at lim _{n → ∞} f / g = 1. ) Dette er en konsekvens av hans asymptotiske estimat for antallet r ( n ) av umerkede forankrede trær med n hjørner:

${\ displaystyle r (n) \ sim D \ alpha ^{n} n ^{-3/2} \ quad {\ text {as}} n \ to \ infty,}$

med D rundt 0,43992401257 ... og samme α som ovenfor (jf. Knuth (1997) , kap. 2.3.4.4 og Flajolet & Sedgewick (2009) , kap. VII.5, s. 475).

De første verdiene til r ( n ) er

1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973,… (sekvens A000081 i OEIS )

Typer trær

• Et banediagram (eller lineær graf ) består av n hjørner arrangert på en linje, slik at hjørner i og i +1 er forbundet med en kant for i = 1, ..., n −1.
• Et stjernelignende tre består av et sentralt toppunkt som kalles rot og flere banediagrammer festet til det. Mer formelt er et tre stjernelignende hvis det har nøyaktig ett toppunkt med en grad større enn 2.
• Et stjernetre er et tre som består av et enkelt indre toppunkt (og n −1 blader). Med andre ord, et stjernetre av orden n er et tre av orden n med så mange blader som mulig.
• Et larvetre er et tre der alle hjørner befinner seg innenfor avstand 1 til et sentralbanesubgraf.
• Et hummer -tre er et tre der alle hjørner befinner seg innenfor avstand 2 til et sentralbanesubgraf.
• Et vanlig tre av grad d er det uendelige treet med d kanter ved hvert toppunkt. Disse oppstår som Cayley -grafer for frie grupper , og i teorien om Tits -bygninger .

Se også

• Hypertree
• Trestruktur
• Treet (datastruktur)
• Beslutningstre
• Pseudoforest
• Ikke rotet binært tre

Merknader

Referanser

• Bender, Edward A .; Williamson, S. Gill (2010), lister, beslutninger og grafer. Med en introduksjon til sannsynlighet
• Dasgupta, Sanjoy (1999), "Learning polytrees", i Proc. 15. konferanse om usikkerhet i kunstig intelligens (UAI 1999), Stockholm, Sverige, juli – august 1999 (PDF) , s. 134–141.
• Deo, Narsingh (1974), Graph Theory with Applications to Engineering and Computer Science (PDF) , Englewood, New Jersey: Prentice-Hall, ISBN 0-13-363473-6
• Harary, Frank ; Prins, Geert (1959), "Antallet homeomorfisk irreduserbare trær og andre arter" , Acta Mathematica , 101 (1–2): 141–162, doi : 10.1007/BF02559543 , ISSN  0001-5962
• Harary, Frank ; Sumner, David (1980), "The dichromatic number of an oriented tree", Journal of Combinatorics, Information & System Sciences , 5 (3): 184–187, MR  0603363.
• Kim, Jin H .; Pearl, Judea (1983), "En beregningsmodell for årsakssammenheng og diagnostisk resonnement i slutningsmotorer", i Proc. 8. internasjonale felles konferanse om kunstig intelligens (IJCAI 1983), Karlsruhe, Tyskland, august 1983 (PDF) , s. 190–193.
• Li, Gang (1996), "Generation of Rooted Trees and Free Trees", MS Thesis, Institutt for informatikk, University of Victoria, BC, Canada (PDF) , s. 9.
• Simion, Rodica (1991), "Trær med 1-faktorer og orienterte trær", Diskret matematikk , 88 (1): 93–104, doi : 10.1016/0012-365X (91) 90061-6 , MR  1099270.

Videre lesning

• Diestel, Reinhard (2005), Graph Theory (3. utg.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4.
• Flajolet, Philippe; Sedgewick, Robert (2009), Analytic Combinatorics , Cambridge University Press, ISBN 978-0-521-89806-5
• "Tree" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Knuth, Donald E. (14. november 1997), The Art of Computer Programming Volume 1: Fundamental Algorithms (3. utg.), Addison-Wesley Professional
• Jerrum, Mark (1994), "Telling av trær i en graf er #P-komplett", Informasjonsbehandlingsbrev , 51 (3): 111–116, doi : 10.1016/0020-0190 (94) 00085-9 , ISSN  0020- 0190.
• Otter, Richard (1948), "The Number of Trees", Annals of Mathematics , Second Series, 49 (3): 583–599, doi : 10.2307/1969046 , JSTOR  1969046.