Träd (grafteori)

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 16 juni 2020; kontroller kräver 6 redigeringar .

Ett träd är en sammankopplad acyklisk graf . [1] Anslutning innebär närvaron av en rutt mellan valfritt par av hörn, acyklicitet betyder frånvaron av cykler. Särskilt av detta följer att antalet kanter i ett träd är en mindre än antalet hörn, och det finns en och bara en väg mellan vilket par av hörn som helst.

Skogen är mycket träd.

Ett riktat (riktat) träd är en acyklisk digraf ( en riktad graf som inte innehåller cykler), där endast en vertex har en nollgrad av ingång (det finns inga bågar i den), och alla andra hörn har en ingångsgrad på 1 (exakt en båge leder till dem). En vertex med nollgrad av ingång kallas trädets rot , hörn med noll grad av utfall (från vilken ingen båge kommer ut) kallas terminala hörn eller blad . [2]

Relaterade definitioner

Graden av en vertex är antalet kanter som träffar den.

En ändnod ( leaf , terminal vertex ) är en nod med grad 1 (det vill säga en nod till vilken endast en kant leder; i fallet med ett riktat träd, en nod till vilken endast en båge leder och inga bågar går ut) .

En grennod är en icke-terminal nod.

Ett träd med en markerad vertex kallas ett rotat träd .
- $m$ Trädets :e skikt är uppsättningen trädnoder, på nivån från trädets rot . $T$ $m$
- partiell ordning på hörnen: om hörnen och är olika och vertexen ligger på den (unika!) elementära kedjan som förbinder roten med vertexen . $u\prec v$ $u$ $v$ $u$ $v$
- rotunderträd rotat som undergraf . $v$ $\{v\}\cup \{w\mid v<w\}$
- I ett sammanhang där ett träd antas ha en rot sägs ett träd utan en förnämlig rot vara fritt .

Nodnivå - längden på vägen från roten till noden. Kan definieras rekursivt:

trädrotnivån är 0; $T$
nivån för någon annan nod är en högre än nivån på roten för det närmaste underträdet i trädet som innehåller den noden. $T$

Ett spännträd ( skelett ) är en subgraf till en given graf som innehåller alla dess hörn och är ett träd. De kanter på grafen som inte ingår i skelettet kallasgrafens ackord med avseende på skelettet.

Ett träd kallas irreducible om det inte har några hörn av grad 2.

En skog är en uppsättning (vanligtvis ordnad) som inte innehåller ett enda icke-korsande träd eller innehåller flera icke-korsande träd.
Centroid - en vertex, vid borttagning av vilken dimensionerna för de resulterande anslutna komponenterna inte överstiger (halva storleken på det ursprungliga trädet) ${\dfrac {n}{2))$

Binärt träd

Termen binärt träd (termen binärt träd används också) har flera betydelser:

Ett oriktat träd med vertexgrader på högst 3.
Ett riktat träd där de utgående graderna av hörn (antalet utgående kanter) inte överstiger 2.
En abstrakt datastruktur som används i programmering . Datastrukturer som binärt sökträd , binärt heap , rödsvart träd , AVL-träd , Fibonacci-hög , etc. är baserade på ett binärt träd.

N-ary trees

N-ära träd definieras i analogi med ett binärt träd. De har också riktade och oriktade fall, såväl som motsvarande abstrakta datastrukturer.

Ett N-ärt träd (oriktat) är ett träd (vanligt, oriktat) där graderna av hörn inte överstiger N + 1.
Ett N-ärt träd (riktat) är ett riktat träd där de utgående graderna av hörn (antalet utgående kanter) inte överstiger N.

Egenskaper

Trädet har inga flera kanter eller öglor .
Alla träd med hörn innehåller en kant. Dessutom är en finit sammankopplad graf ett träd om och endast om , där är antalet hörn och är antalet grafkanter. $n$ $n-1$ $BP=1$ $B$ $P$
En graf är ett träd om och endast om två av dess distinkta hörn kan kopplas samman med en enkel enkel kedja .
Varje träd bestäms unikt av avstånden (längden på den minsta kedjan) mellan dess terminala (grad 1) hörn.
Vilket träd som helst är en tvådelad graf .
Varje träd vars vertexuppsättning som mest är räknbar är en plan graf .
För tre trädhörn har banorna mellan paren av dessa hörn exakt en gemensam vertex.

Trädräkning

Antalet distinkta träd som kan byggas på numrerade hörn är ( Cayleys teorem [3] ). $n$ $n^{{n-2}}$
Genererande funktion

T(z)=\summa _{n=1}^{\infty }T_{n}z^{n}

för antalet icke-isomorfa rotade träd med hörn uppfyller den funktionella ekvationen

T_{n}

n

T(z)=z\exp \sum _{r=1}^{\infty }{\frac {1}{r}}T(z^{r})

Genererande funktion

t(z)=\summa _{n=1}^{\infty }t_{n}z^{n}

för antalet icke- isomorfa träd med hörn kan representeras med hjälp av listserien för rotade träd:

t_{n}

n

t(z)=T(z)-{\frac {1}{2}}\vänster(T^{2}(z)-T(z^{2})\höger).

För följande asymptotik är sant $n\till\infty$

t_{n}\sim C\alpha ^{n}/n^{5/2}

var och är vissa konstanter, , .

C

\alfa

C=0,534948...

\alpha =2,95576...

Trädkodning

Ett träd kan kodas som uppsättningar av nollor och ettor. Tänk till exempel på att lägga ett träd på ett plan. Med utgångspunkt från någon vertex, kommer vi att röra oss längs kanterna på trädet, vända vid varje vertex till kanten närmast höger och vända tillbaka vid trädets ändpunkter. När vi passerar längs någon kant, skriver vi när vi rör oss längs kanten för första gången och när vi rör oss längs kanten andra gången (i motsatt riktning). Om är antalet kanter på trädet, kommer vi efter steg att återgå till den ursprungliga vertexen och gå igenom varje kant två gånger. Den resulterande sekvensen av och (trädkod) längder gör det möjligt att entydigt återställa inte bara själva trädet utan också dess läggning på planet. Ett godtyckligt träd motsvarar flera sådana koder. I synnerhet följer följande grova uppskattning av antalet träd med hörn från denna kodningsmetod: $0$ $ett$ $m$ $2m$ $0$ $ett$ $2m$ $D$ $n$ $t_{n}\leq T_{n}<2^{2n}$

Prufer-koden mappar till ett godtyckligt ändligt träd med hörn en sekvens av tal från till med möjliga upprepningar. Till exempel har trädet i figuren Prufer-koden (4,4,4,5). Det finns en en-till-en-överensstämmelse mellan märkta vertexträd och deras Prufer-koder. Cayleys formel härrör från Prüfer-koden . $n$ $n-2$ $ett$ $n$

Trädet kan anges som en sträng som innehåller tecken som markerar trädets noder, samt öppnande och avslutande parenteser. Det finns en en-till-en-överensstämmelse mellan träd och deras linjära parentes.

Se även

Anteckningar

↑ § 13. Definition av ett träd // Föreläsningar om grafteori / Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I. - M . : Nauka, Fizmatlit, 1990. - P. 53. - 384 sid. — 22 000 exemplar. — ISBN 5-02-013992-0 .
↑ Alfs Berztiss. Kapitel 3. Grafteori. 3.6. Träd // Datastrukturer = AT Berztiss. data struktur. teori och praktik. - M. : Statistik, 1974. - S. 131. - 10 500 ex.
↑ Diskret matematik: Algoritmer. Cayleys formel (otillgänglig länk) . Hämtad 29 oktober 2009. Arkiverad från originalet 14 juni 2009. (obestämd)

Litteratur

Donald Knuth . The Art of Computer Programming, vol. 1. Grundläggande algoritmer. - 3:e uppl. - M .: Williams , 2006. - T. 1. Grundläggande algoritmer. — 720 s. - ISBN 0-201-89683-4 .
Ore O. Grafteori. - 2:a uppl. — M .: Nauka , 1980. — 336 sid.
Harari F. Grafteori. — M .: Mir , 1973. — 302 sid.

Träd (datastruktur)
Binärt sökträd Träd (grafteori) trädstruktur
Binära träd	binärt träd T-träd
Självbalanserande binära träd	AA-träd AVL-träd Röd-svart träd Splay träd träd med böter kartesiskt träd Fibonacci träd B-träd T-träd
B-träd	2-3-träd B⁺-träd B*-träd B x -träd UB-träd 2-3-4 träd (a,b)-träd dansande träd
prefix träd	suffixträd Komprimerat prefixträd Ternärt sökträd
Binär uppdelning av utrymme	k-dimensionellt träd VP-träd
Icke-binära träd	Quadtree octree Gles Voxel Octree exponentiellt träd PQ-träd
Bryter upp utrymmet	R-träd Hilbert R-träd R+-träd R*-träd X-träd M-träd Fenwick träd Segment träd
Andra träd	högen haschträd fingerträd metriskt träd Beläggning träd BK-träd Dubbelkedjat träd iDistance Länkklippt träd LSM-träd
Algoritmer	Utöka första sökningen Djup första sökning DSW-algoritm spaning tree-protokoll