Træ (grafteori)

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 16. juni 2020; checks kræver 6 redigeringer .

Et træ er en forbundet acyklisk graf . [1] Forbindelse betyder tilstedeværelsen af en rute mellem et hvilket som helst par af hjørner, acyklicitet betyder fravær af cyklusser. Heraf følger det især, at antallet af kanter i et træ er én mindre end antallet af toppunkter, og der er én og kun én vej mellem ethvert par af toppunkter.

Skoven er en masse træer.

Et rettet (rettet) træ er en acyklisk digraf ( en rettet graf , der ikke indeholder cyklusser), hvor kun et toppunkt har en indgangsgrad på nul (der er ingen buer i det), og alle andre hjørner har en indgangsgrad på 1 (nøjagtig en bue fører til dem). Et toppunkt med nul grad af indgang kaldes træets rod , toppunkter med nul grad af udfald (hvorfra der ikke kommer nogen bue ud) kaldes terminale toppunkter eller blade . [2]

Relaterede definitioner

Graden af et toppunkt er antallet af kanter, der falder ind på det.

En endeknude ( blad , endepunkt ) er en knude med grad 1 (det vil sige en knude, hvortil kun en kant fører; i tilfælde af et rettet træ, en knude, hvortil kun en bue fører, og ingen buer går ud) .

En grenknude er en ikke-terminal knude.

Et træ med et markeret toppunkt kaldes et rodfæstet træ .
- $m$ Træets th tier er sættet af træknuder i niveauet fra træets rod. $T$ $m$
- delrækkefølge på toppunkterne: hvis toppunkterne og er forskellige og toppunktet ligger på den (unikke!) elementære kæde, der forbinder roden med toppunktet . $u\prec v$ $u$ $v$ $u$ $v$
- rod undertræ forankret som undergraf . $v$ $\{v\}\kop \{w\midt v<w\}$
- I en sammenhæng, hvor et træ antages at have en rod, siges et træ uden en fornem rod at være frit .

Node niveau - længden af stien fra roden til noden. Kan defineres rekursivt:

trærodniveauet er 0; $T$
niveauet af enhver anden knude er en højere end niveauet af roden af det nærmeste undertræ i træet , der indeholder den knude. $T$

Et spændingstræ ( skelet ) er en undergraf af en given graf, der indeholder alle dens hjørner og er et træ. De kanter af grafen, der ikke er inkluderet i skelettet, kaldes grafens akkorder i forhold til skelettet.

Et træ kaldes irreducibelt, hvis det ikke har nogen toppunkter på grad 2.

En skov er et sæt (normalt ordnet), der ikke indeholder et enkelt ikke-skærende træ eller indeholder flere ikke-skærende træer.
Centroid - et toppunkt, ved fjernelse af hvilket dimensionerne af de resulterende tilsluttede komponenter ikke overstiger (halvdelen af det originale træs størrelse) ${\dfrac {n}{2))$

Binært træ

Udtrykket binært træ (udtrykket binært træ bruges også) har flere betydninger:

Et urettet træ med topgrader på højst 3.
Et rettet træ, hvor de udgående grader af hjørner (antallet af udgående kanter) ikke overstiger 2.
En abstrakt datastruktur brugt i programmering . Datastrukturer såsom binært søgetræ , binært hob , rød-sort træ , AVL-træ , Fibonacci-dynge osv. er baseret på et binært træ.

N-ære træer

N-ære træer er defineret i analogi med et binært træ. De har også rettede og urettede cases, såvel som tilsvarende abstrakte datastrukturer.

Et N-ært træ (urettet) er et træ (almindeligt, urettet), hvor graderne af toppunkter ikke overstiger N + 1.
Et N-ært træ (rettet) er et rettet træ, hvor de udgående grader af hjørner (antallet af udgående kanter) ikke overstiger N.

Egenskaber

Træet har ingen flere kanter eller sløjfer .
Ethvert træ med toppunkter indeholder en kant. Desuden er en endelig forbundet graf et træ, hvis og kun hvis , hvor er antallet af hjørner og er antallet af grafkanter. $n$ $n-1$ $BP=1$ $B$ $P$
En graf er et træ, hvis og kun hvis to af dens distinkte hjørner kan forbindes med en enkelt simpel kæde .
Ethvert træ er entydigt bestemt af afstandene (længden af den mindste kæde) mellem dets terminale (grad 1) hjørner.
Ethvert træ er en todelt graf .
Ethvert træ, hvis toppunktssæt højst kan tælles, er en plan graf .
For alle tre træhjørner har stierne mellem par af disse knudepunkter nøjagtigt et fælles knudepunkt.

Trætælling

Antallet af særskilte træer, der kan bygges på nummererede hjørner er ( Cayleys sætning [3] ). $n$ $n^{{n-2}}$
Genererende funktion

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

for antallet af ikke-isomorfe rodfæstede træer med toppunkter opfylder den funktionelle ligning

T_{n}

n

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

Genererende funktion

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

for antallet af ikke- isomorfe træer med toppunkter kan repræsenteres ved hjælp af listeserien for rodfæstede træer:

t_{n}

n

t(z)=T(z)-{\frac {1}{2}}\venstre(T^{2}(z)-T(z^{2})\højre).

For følgende asymptotik er sandt $n\til\infty$

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

hvor og er visse konstanter, , .

C

\alfa

C=0,534948...

\alpha =2,95576...

Trækodning

Et træ kan kodes som sæt af nuller og etaller. Overvej for eksempel at lægge et træ på et fly. Startende fra et eller andet toppunkt, vil vi bevæge os langs kanterne af træet, dreje ved hvert toppunkt til kanten tættest på højre og dreje tilbage ved træets endespidser. Når vi passerer langs en kant, skriver vi, når vi bevæger os langs kanten for første gang, og når vi bevæger os langs kanten anden gang (i den modsatte retning). Hvis er antallet af kanter af træet, så vil vi efter trin vende tilbage til det oprindelige toppunkt og gå gennem hver kant to gange. Den resulterende sekvens af og (trækode) længder gør det muligt entydigt at genoprette ikke kun selve træet , men også dets lægning på planet. Et vilkårligt træ svarer til flere sådanne koder. Især følger følgende grove estimat for antallet af træer med toppunkter fra denne kodningsmetode: $0$ $en$ $m$ $2m$ $0$ $en$ $2m$ $D$ $n$ $t_{n}\leq T_{n}<2^{2n}$

Prufer-koden afbildes til et vilkårligt endeligt træ med knudepunkter en sekvens af tal fra til med mulige gentagelser. For eksempel har træet i figuren Prufer-koden (4,4,4,5). Der er en en-til-en-korrespondance mellem mærkede vertextræer og deres Prufer-koder. Cayleys formel er afledt af Prüfer-koden . $n$ $n-2$ $en$ $n$

Træet kan angives som en streng, der indeholder tegn, der markerer træets noder, samt åbne- og lukkeparenteser. Der er en en-til-en overensstemmelse mellem træer og deres lineære parentesnotationer.

Se også

Ordliste over grafteori
Skov af usammenhængende sæt
Liste over datastrukturer (træer)

Noter

↑ § 13. Definition af et træ // Forelæsninger om grafteori / Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I. - M . : Nauka, Fizmatlit, 1990. - S. 53. - 384 s. — 22.000 eksemplarer. — ISBN 5-02-013992-0 .
↑ Alfs Berztiss. Kapitel 3. Grafteori. 3.6. Træer // Datastrukturer = AT Berztiss. datastrukturer. teori og praksis. - M. : Statistik, 1974. - S. 131. - 10.500 eksemplarer.
↑ Diskret matematik: Algoritmer. Cayleys formel (utilgængeligt link) . Hentet 29. oktober 2009. Arkiveret fra originalen 14. juni 2009. (ubestemt)

Litteratur

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

Træ (datastruktur)
Binært søgetræ Træ (grafteori) træstruktur
Binære træer	binært træ T-træ
Selvbalancerende binære træer	AA træ AVL træ Rød-sort træ Splay træ træ med bøder kartesisk træ Fibonacci træ B-træ T-træ
B-træer	2-3-træ B⁺-træ B*-træ B x -træ UB træ 2-3-4 træ (a,b)-træ dansende træ
præfiks træer	suffiks træ Komprimeret præfikstræ Ternært søgetræ
Binær opdeling af rummet	k-dimensionelt træ VP træ
Ikke-binære træer	Quadtree oktre Sparsom Voxel Octree eksponentielt træ PQ træ
At bryde rummet op	R-træ Hilbert R-træ R+-træ R*-træ X-træ M-træ Fenwick træ Segmenttræ
Andre træer	dynge hash træ fingertræ metrisk træ Belægning træ BK-træ Dobbeltkædet træ iDistance Linkskåret træ LSM træ
Algoritmer	Bredde først søgning Dybde første søgning DSW algoritme spanning tree protokol