TreeEdit

ett träd är en oriktad graf G som uppfyller något av följande ekvivalenta villkor:

• G är ansluten och acyklisk (innehåller inga cykler).
• G är acyklisk och en enkel cykel bildas om någon kant läggs till G.
• G är ansluten, men skulle kopplas bort om någon enda kant tas bort från G.
• G är ansluten och 3-vertex komplett graf K3 är inte en mindre av G.
• Alla två hörn i G kan anslutas med en unik enkel väg.

om G har ändligt många hörn, säg n av dem, motsvarar ovanstående uttalanden också något av följande villkor:

• G är ansluten och har n − 1 kanter.
• G är ansluten, och varje delgraf av G innehåller minst ett toppunkt med noll eller en infallande kanter. (Det vill säga G är ansluten och 1-degenererad.)
• G har inga enkla cykler och har n-1 kanter.

som på andra håll i grafteori anses ordningsnollgrafen (graf utan hörn) i allmänhet inte vara ett träd: medan den är vakuumansluten som en graf (vilka två hörn som helst kan anslutas med en bana), är den inte 0-ansluten (eller till och med (-1)-ansluten) i algebraisk topologi, till skillnad från icke-tomma träd, och bryter mot ”en mer vertex än kanter” relation. Det kan dock betraktas som en skog som består av noll träd.

ett inre vertex (eller inre vertex eller gren vertex) är ett vertex av grad minst 2. På samma sätt är ett yttre vertex (eller yttre vertex, terminal vertex eller blad) ett vertex av grad 1.

ett irreducibelt träd (eller seriereducerat träd) är ett träd där det inte finns något toppunkt av grad 2 (uppräknat i sekvens A000014 i OEIS).

ForestEdit

en skog är en oriktad graf där två hörn är förbundna med högst en väg. Likvärdigt är en skog en oriktad acyklisk graf, vars alla anslutna komponenter är träd; med andra ord består grafen av en ojämn förening av träd. Som speciella fall är order-zero-grafen (en skog som består av nollträd), ett enda träd och en kantlös graf, exempel på skogar.Eftersom för varje träd V-E = 1 kan vi enkelt räkna antalet träd som ligger inom en skog genom att subtrahera skillnaden mellan totala hörn och totala kanter. TV-te = antal träd i en skog.

PolytreeEdit

en polytree (eller riktat träd eller orienterat träd eller enskilt anslutet nätverk) är en riktad acyklisk graf (DAG) vars underliggande oriktade graf är ett träd. Med andra ord, om vi ersätter dess riktade kanter med oriktade kanter, får vi en oriktad graf som är både ansluten och acyklisk.

Vissa författare begränsar frasen” riktat träd ” till fallet där kanterna alla riktas mot ett visst toppunkt, eller alla riktas bort från ett visst toppunkt (se arborescens).

PolyforestEdit

en polyforest (eller riktad skog eller orienterad skog) är en riktad acyklisk graf vars underliggande oriktad graf är en skog. Med andra ord, om vi ersätter dess riktade kanter med oriktade kanter, får vi en oriktad graf som är acyklisk.

Vissa författare begränsar frasen” riktad skog ” till fallet där kanterna på varje ansluten komponent alla riktas mot ett visst toppunkt, eller alla riktas bort från ett visst toppunkt (se förgrening).

rotat trädredigera

ett rotat träd är ett träd där ett toppunkt har utsetts till roten. Kanterna på ett rotat träd kan tilldelas en naturlig orientering, antingen bort från eller mot roten, i vilket fall strukturen blir ett riktat rotat träd. När ett riktat rotat träd har en orientering bort från roten kallas det en arborescence eller out-tree; när den har en orientering mot roten kallas den en anti-arborescence eller in-tree. Trädordningen är den partiella ordningen på ett träds hörn med u < v om och endast om den unika vägen från roten till v passerar genom u. ett rotat träd T som är en delgraf av någon graf G är ett normalt träd om ändarna på varje T-bana i G är jämförbara i denna trädordning (Diestel 2005, s. 15). Rotade träd, ofta med ytterligare struktur som beställning av grannarna vid varje toppunkt, är en viktig datastruktur inom datavetenskap; se träddatastruktur.

i ett sammanhang där träd ska ha en rot kallas ett träd utan någon utsedd rot ett fritt träd.

ett märkt träd är ett träd där varje toppunkt ges en unik etikett. De hörn av en märkt träd På n hörn ges typiskt etiketterna 1, 2,…, n. ett rekursivt träd är ett märkt rotat träd där vertexetiketterna respekterar trädets ordning (dvs., om u < v för två hörn u och v, är etiketten på u mindre än etiketten på v).

i ett rotat träd är föräldern till ett toppunkt v det toppunkt som är anslutet till v på vägen till roten; varje toppunkt har en unik förälder utom roten som inte har någon förälder. Ett barn av ett vertex v är ett vertex av vilket v är föräldern. En ascendant av en vertex v är varje vertex som antingen är förälder till v eller är (rekursivt) ascendant av förälder till v. En ättling till en vertex v är varje vertex som antingen är barn till v eller är (rekursivt) ättling till något av barnen till v. ett syskon till ett vertex v är något annat vertex på trädet som har samma förälder som v. ett blad är ett vertex utan barn. Ett internt toppunkt är ett toppunkt som inte är ett blad.

höjden på ett toppunkt i ett rotat träd är längden på den längsta nedåtgående vägen till ett blad från det toppunktet. Trädets höjd är rotens höjd. Djupet på ett toppunkt är längden på vägen till dess rot (rotväg). Detta behövs vanligtvis vid manipulering av de olika självbalanserande träden, särskilt AVL-träd. Roten har djup noll, löv har höjd noll och ett träd med endast ett enda toppunkt (därmed både en rot och ett blad) har djup och höjd noll. Konventionellt har ett tomt träd (ett träd utan hörn, om sådana är tillåtna) djup och höjd -1.

ett k-ary träd är ett rotat träd där varje toppunkt har högst k-barn. 2-ary träd kallas ofta binära träd, medan 3-ary träd kallas ibland ternära träd.

beställt trädredigera

ett ordnat träd (eller Platan) är ett rotat träd där en beställning anges för barnen i varje toppunkt. Detta kallas ett” planträd ” eftersom en beställning av barnen motsvarar en inbäddning av trädet i planet, med roten högst upp och barnen i varje toppunkt lägre än det toppunktet. Med tanke på en inbäddning av ett rotat träd i planet, om man fixar en riktning av barn, säger vänster till höger, då ger en inbäddning en beställning av barnen. Omvänt, med tanke på ett ordnat träd, och konventionellt ritar roten på toppen, kan barnets hörn i ett ordnat träd dras från vänster till höger, vilket ger en väsentligen unik plan inbäddning.