TreeEdit

et træ er en ikke-rettet graf G, der opfylder en af følgende ækvivalente betingelser:

• G er forbundet og acyklisk (indeholder ingen cyklusser).
• G er acyklisk, og en simpel cyklus dannes, hvis der tilføjes en kant til G.
• G er tilsluttet, men ville blive afbrudt, hvis en enkelt kant fjernes fra G.
• G er forbundet, og 3-toppunktet komplet graf K3 er ikke mindre af G.
• Eventuelle to hjørner i G kan forbindes med en unik enkel sti.

Hvis G har endeligt mange hjørner, siger n af dem, svarer ovenstående udsagn også til en af følgende betingelser:

• G er forbundet og har n − 1 kanter.
• G er forbundet, og hver undergraf af G inkluderer mindst et toppunkt med nul eller en hændelseskant. (Det vil sige, G er forbundet og 1-degenereret.)
• G har ingen enkle cyklusser og har n − 1 kanter.

som andre steder i grafteori betragtes orden – nul-grafen (graf uden hjørner) generelt ikke som et træ: mens det er vakuumforbundet som en graf (to hjørner kan forbindes med en sti), er det ikke 0-forbundet (eller endda (-1)-forbundet) i algebraisk topologi, i modsætning til ikke-tomme træer, og krænker forholdet “et mere toppunkt end kanter”. Det kan dog betragtes som en skov bestående af nul træer.

en indre toppunkt (eller indre toppunkt eller gren toppunkt) er et toppunkt af grad mindst 2. Tilsvarende er et eksternt toppunkt (eller ydre toppunkt, terminal toppunkt eller blad) et toppunkt i grad 1.

et irreducerbart træ (eller seriereduceret træ) er et træ, hvor der ikke er noget toppunkt i grad 2 (opregnet ved sekvens A000014 i OEIS).

ForestEdit

en skov er en ikke-rettet graf, hvor to hjørner er forbundet med højst en sti. Tilsvarende er en skov en ikke-rettet acyklisk graf, hvis alle tilsluttede komponenter er træer; med andre ord består grafen af en uensartet forening af træer. Som særlige tilfælde er orden – nul-grafen (en skov bestående af nul træer), et enkelt træ og en kantløs graf eksempler på skove.Da for hvert træ V-e = 1, kan vi nemt tælle antallet af træer, der er inden for en skov ved at trække forskellen mellem samlede hjørner og samlede kanter. TV-TE = antal træer i en skov.

PolytreeEdit

en polytree (eller rettet træ eller orienteret træ eller enkeltforbundet netværk) er en rettet acyklisk graf (DAG), hvis underliggende ikke-rettet graf er et træ. Med andre ord, hvis vi erstatter dens rettede kanter med ikke-rettede kanter, får vi en ikke-rettet graf, der er både forbundet og acyklisk.

Nogle forfattere begrænser udtrykket “rettet træ” til det tilfælde, hvor kanterne alle er rettet mod et bestemt toppunkt eller alle rettet væk fra et bestemt toppunkt (se arborescens).

Polyforestededit

en polyforest (eller rettet skov eller orienteret skov) er en rettet acyklisk graf, hvis underliggende ikke-rettet graf er en skov. Med andre ord, hvis vi erstatter dens rettede kanter med ikke-rettede kanter, får vi en ikke-rettet graf, der er acyklisk.

Nogle forfattere begrænser udtrykket “rettet skov” til det tilfælde, hvor kanterne på hver tilsluttet komponent alle er rettet mod et bestemt toppunkt eller alle rettet væk fra et bestemt toppunkt (se forgrening).

Rooted treeEdit

et rodfæstet træ er et træ, hvor et toppunkt er blevet betegnet roden. Kanterne på et rodfæstet træ kan tildeles en naturlig orientering, enten væk fra eller mod roden, i hvilket tilfælde strukturen bliver et rettet rodfæstet træ. Når et rettet rodfæstet træ har en orientering væk fra roden, kaldes det en arborescens eller out-tree; når det har en orientering mod roden, kaldes det en anti-arborescens eller in-tree. Træordren er den delvise rækkefølge på hjørnerne af et træ med u < V hvis og kun hvis den unikke sti fra rod til v passerer gennem u. et rodfæstet træ T, som er en undergraf af en eller anden graf G, er et normalt træ, hvis enderne af hver T-sti i G er sammenlignelige i denne trærækkefølge (Diestel 2005, s. 15). Rodfæstede træer, ofte med yderligere struktur såsom bestilling af naboerne ved hvert toppunkt, er en nøgledatastruktur inden for datalogi; se trædatastruktur.

i en sammenhæng, hvor træer skal have en rod, kaldes et træ uden nogen udpeget rod et frit træ.

et mærket træ er et træ, hvor hvert toppunkt får en unik etiket. Hjørnerne af et mærket træ på N hjørner er typisk givet etiketterne 1, 2,…, n. et rekursivt træ er et mærket rodfæstet træ, hvor toppunktsetiketterne respekterer trærækkefølgen (dvs., hvis u < v for to hjørner u og v, så er etiketten på u mindre end etiketten på v).

i et rodfæstet træ er forælderen til et toppunkt v det toppunkt, der er forbundet med v på stien til roden; hvert toppunkt har en unik forælder undtagen roden, der ikke har nogen forælder. Et barn af et toppunkt v er et toppunkt, hvoraf v er forælder. En opstigning af et toppunkt v er ethvert toppunkt, der enten er forælder til v eller er (rekursivt) opstigningen af forældrene til v. En efterkommer af et toppunkt v er ethvert toppunkt, der enten er barn af v eller er (rekursivt) efterkommer af et af børnene til v. et søskende til et toppunkt v er ethvert andet toppunkt på træet, der har den samme forælder som v. et blad er et toppunkt uden børn. Et indre toppunkt er et toppunkt, der ikke er et blad.

højden af et toppunkt i et rodfæstet træ er længden af den længste nedadgående sti til et blad fra det toppunkt. Træets højde er rodens højde. Dybden af et toppunkt er længden af stien til dens rod (rodsti). Dette er almindeligt nødvendigt i manipulationen af de forskellige selvbalancerende træer, AVL træer i særdeleshed. Roden har dybde nul, blade har højde nul, og et træ med kun et enkelt toppunkt (dermed både en rod og et blad) har dybde og højde nul. Konventionelt har et tomt træ (et træ uden hjørner, hvis sådanne er tilladt) dybde og højde -1.

et k-Ary træ er et rodfæstet træ, hvor hvert toppunkt højst har k-børn. 2-ary træer kaldes ofte binære træer, mens 3-ary træer undertiden kaldes ternære træer.

bestilt træredit

et bestilt træ (eller platantræ) er et rodfæstet træ, hvor en ordre er specificeret for børnene i hvert toppunkt. Dette kaldes et” platantræ”, fordi en bestilling af børnene svarer til en indlejring af træet i flyet, med roden øverst og børnene i hvert toppunkt lavere end det toppunkt. Givet en indlejring af et rodfæstet træ i flyet, hvis man løser en retning af børn, siger venstre mod højre, så giver en indlejring en ordre af børnene. Omvendt, givet et ordnet træ, og konventionelt tegning af roden øverst, så kan barnets hjørner i et ordnet træ trækkes fra venstre mod højre, hvilket giver en i det væsentlige unik plan indlejring.