TreeEdit

et tre er en ikke-rettet graf G Som oppfyller noen av følgende ekvivalente forhold:

• G er tilkoblet Og asyklisk (inneholder ingen sykluser).
• G er acyklisk, Og en enkel syklus dannes hvis en kant legges til G.
• G er tilkoblet, Men vil bli frakoblet hvis en enkelt kant fjernes fra G.
• G er tilkoblet Og 3-toppunktet komplett graf K3 er ikke en mindre Av G.
• noen to hjørner I G kan kobles sammen med en unik enkel bane.

Hvis G har endelig mange hjørner, si n av dem, så er de ovennevnte setningene også ekvivalente med noen av følgende forhold:

• G er koblet og har n − 1 kanter.
• G er tilkoblet, og hver undergraf Av G inneholder minst ett toppunkt med null eller en hendelseskant. (Det Vil Si At G er tilkoblet og 1-degenerert.)
• G har ingen enkle sykluser og har n-1 kanter.

som andre steder i grafteori, er order-zero-grafen (graf uten hjørner) generelt ikke ansett som et tre: selv om det er vacuously forbundet som en graf (noen to hjørner kan kobles til med en bane), er det ikke 0-tilkoblet (eller til og med (-1)-tilkoblet) i algebraisk topologi, i motsetning til ikke-tomme trær, og bryter med «ett toppunkt enn kanter» – forholdet. Det kan imidlertid betraktes som en skog som består av null trær.Et indre vertex (eller indre vertex eller gren vertex) er et vertex av grad minst 2. På samme måte er et eksternt toppunkt (eller ytre toppunkt, terminal toppunkt eller blad) et toppunkt av grad 1.et irreducible tre (eller serie-redusert tre) er et tre der det ikke er noe toppunkt av grad 2 (nummerert i sekvens A000014 I OEIS).

ForestEdit

en skog er en ikke-rettet graf der to hjørner er forbundet med maksimalt en bane. Tilsvarende er en skog en ikke-styrt asyklisk graf, alle hvis tilkoblede komponenter er trær; med andre ord består grafen av en disjoint union av trær. Som spesielle tilfeller er order-zero-grafen (en skog som består av null trær), et enkelt tre og en kantløs graf, eksempler på skoger.Siden for hvert tre V-E = 1, kan vi enkelt telle antall trær som er innenfor en skog ved å trekke forskjellen mellom totale hjørner og totale kanter. TV-TE = antall trær i en skog.

PolytreeEdit

en polytree (eller rettet tre eller orientert tre eller enkelt tilkoblet nettverk) er en rettet asyklisk graf (DAG) hvis underliggende urettet graf er et tre. Med andre ord, hvis vi erstatter de rettede kantene med ikke-rettede kanter, får vi en ikke-rettet graf som er både tilkoblet og acyklisk.

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

PolyforestEdit

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

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

Rooted treeEdit

et rotfestet tre er et tre der ett toppunkt har blitt betegnet roten. Kantene på et rotfestet tre kan tilordnes en naturlig orientering, enten vekk fra eller mot roten, i så fall blir strukturen et rettet rotfestet tre. Når et rettet rotfestet tre har en orientering vekk fra roten, kalles det en arborescence eller out-tree; når det har en orientering mot roten, kalles det en anti-arborescence eller in-tree. Trerekkefølgen er den delvise rekkefølgen på hjørnene til et tre med u < v hvis og bare hvis den unike banen fra roten til v går gjennom u. et rotfestet tre T Som er en undergraf Av noen graf G er et normalt tre hvis endene på Hver t-bane I G er sammenlignbare i denne trerekkefølgen (Diestel 2005, s. 15). Rotte trær, ofte med ekstra struktur som bestilling av naboene på hvert toppunkt, er en viktig datastruktur i datavitenskap; se tre datastruktur.

i en kontekst der trær skal ha en rot, kalles et tre uten noen utpekt rot et fritt tre.

et merket tre er et tre der hvert toppunkt er gitt en unik etikett. Hjørnene av et merket tre på n topp-punkt er vanligvis gitt etikettene 1, 2,…, n. et rekursivt tre er et merket rotfestet tre hvor 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 forelderen til et toppunkt v det toppunktet som er koblet til v på banen til roten; hvert toppunkt har en unik forelder bortsett fra roten som ikke har noen forelder. Et barn av et toppunkt v er et toppunkt hvorav v er foreldre. En ascendant av et vertex v er et vertex som enten er foreldre til v eller er (rekursivt) ascendant av foreldre til v. En etterkommer av et toppunkt v er et hvilket som helst toppunkt som er enten barnet til v eller er (rekursivt) etterkommeren av noen av barna til v. et søsken til et toppunkt v er et hvilket som helst annet toppunkt på treet som har samme forelder som v. et blad er et toppunkt uten barn. Et internt toppunkt er et toppunkt som ikke er et blad.

høyden på et toppunkt i et rotfestet tre er lengden på den lengste nedadgående banen til et blad fra det toppunktet. Høyden på treet er høyden på roten. Dybden på et toppunkt er lengden på banen til roten (rotbanen). Dette er vanligvis nødvendig i manipulering av de ulike selvbalanserende trær, AVL trær spesielt. Roten har dybde null, bladene har høyde null ,og et tre med bare et enkelt toppunkt (dermed både en rot og et blad) har dybde og høyde null. Konvensjonelt har et tomt tre (et tre uten hjørner, hvis det er tillatt) dybde og høyde -1.Et k-ary-tre er et rotfestet tre hvor hvert toppunkt har maksimalt k-barn. 2-ary trær kalles ofte binære trær, mens 3-ary trær kalles ternære trær.

Bestilt treedit

et bestilt tre (eller platantreet) er et rotfestet tre der en bestilling er spesifisert for barna til hvert toppunkt. Dette kalles en «plane tree» fordi en bestilling av barn tilsvarer en innebygging av treet i flyet, med roten på toppen og barn av hvert toppunkt lavere enn det toppunktet. Gitt en embedding av et rotfestet tre i flyet, hvis man løser en retning av barn, si venstre til høyre, så gir en embedding en bestilling av barna. Omvendt, gitt et bestilt tre, og konvensjonelt tegner roten øverst, så kan barnets hjørner i et bestilt tre trekkes fra venstre til høyre, noe som gir en vesentlig unik plan innebygging.