Övning 1: Ett träd har 15 noder. Hur många kanter har det?

Ett träd med n noder har alltid n-1 kanter För 15 noder: 15-1 = 14 kanter Svar: 14 kanter

Medel

Träd och skogar

Träd som speciella grafer, rötade träd och trädegenskaper.

träd skog löv rot höjd binärt träd

Träd är överallt omkring oss - inte bara i naturen, utan i datorstrukturer, beslutsprocesser och organisationsscheman. Ett träd i grafteori är den enklaste formen av sammanhängande nätverk: det finns exakt en väg mellan varje par av punkter. Denna eleganta enkelhet gör träd till en av de mest användbara strukturerna inom datavetenskap och matematik.

Fördjupning

Ett träd är en sammanhängande graf utan cykler. Detta ger träd unika egenskaper: de har exakt n-1 kanter för n noder, varje två noder förbinds av exakt en väg, och att ta bort en kant gör grafen icke-sammanhängande. Rotade träd introducerar hierarki med begrepp som föräldrar, barn och blad.

Definition och egenskaper hos träd

Ett träd är en sammanhängande acyklisk graf. Denna enkla definition leder till många kraftfulla egenskaper som gör träd unika bland grafer. Träd är minimalt sammanhängande (ta bort en kant → ej sammanhängande) och maximalt acyklisk (lägg till en kant → cykel uppstår).

Definition av träd: sammanhängande \land acyklisk

Fundamental egenskap: träd med n noder har exakt n-1 kanter

Ekvivalenta definitioner av träd

För graf G med n noder är följande ekvivalent:

· G är sammanhängande och acyklisk

· G är sammanhängande och har n-1 kanter

· G är acyklisk och har n-1 kanter

· G är sammanhängande och minimalt sammanhängande

· Varje par av noder förbinds av exakt en väg

Olika exempel på träd med samma antal noder men olika struktur

Rotade träd och hierarkier

Ett rötat träd har en utpekad rot-nod som skapar en naturlig hierarki. Varje nod (utom roten) har exakt en förälder och kan ha flera barn. Blad är noder utan barn. Denna struktur är fundamental för många algoritmer och datastrukturer.

Hierarkiska relationer i rötat träd: rot, föräldrar, barn, blad

Terminologi för rotade träd

I ett rötat träd:

· Rot: enda noden utan förälder

· Förälder: nod direkt ovanför

· Barn: noder direkt nedanför

· Syskon: noder med samma förälder

· Blad: noder utan barn

· Inre noder: noder med minst ett barn

· Höjd: längsta vägen från rot till blad

Illustration av terminologi i rotade träd

Binära träd

Ett binärt träd är ett rötat träd där varje nod har högst två barn, ofta kallade vänster och höger barn. Binära träd är extremt viktiga i datavetenskap för sökträd, heaps och uttrycksträd. De kan vara kompletta, fulla eller perfekta beroende på struktur.

Definition av binärt träd: varje nod har högst 2 barn

Egenskaper: max 2^h noder på höjd h, max 2^(h+1)-1 noder totalt

Typer av binära träd

· Fullt binärt träd: varje nod har 0 eller 2 barn

· Komplett binärt träd: alla nivåer fyllda utom möjligen sista (fylls från vänster)

· Perfekt binärt träd: alla inre noder har 2 barn, alla blad på samma nivå

· Degenererat träd: varje nod har högst 1 barn (som en länkad lista)

Olika typer av binära träd och deras egenskaper

Traversering av träd

Att besöka alla noder i ett träd kallas traversering. För binära träd finns tre huvudmetoder: preorder (rot-vänster-höger), inorder (vänster-rot-höger) och postorder (vänster-höger-rot). Breadth-first traversering besöker noder nivå för nivå.

Definitioner av preorder, inorder och postorder traversering

Traversering av binärt träd

Träd med struktur: A(B(D,E),C(F,G))

Preorder: A, B, D, E, C, F, G (rot först)

Inorder: D, B, E, A, F, C, G (rot mellan)

Postorder: D, E, B, F, G, C, A (rot sist)

Breadth-first: A, B, C, D, E, F, G (nivå för nivå)

Visualisering av olika traverseringsordningar

Spanning trees

Ett spanning tree för en sammanhängande graf G är ett delträd som innehåller alla noder i G. Varje sammanhängande graf har minst ett spanning tree. Antalet spanning trees i en graf ges av Matrix-Tree-satsen och har tillämpningar inom nätverksdesign.

Definition av spanning tree: delgraf som är träd och innehåller alla noder

Matrix-Tree-satsen för att räkna antalet spanning trees

Konstruktion av spanning trees

Graf med noder {A,B,C,D} och kanter {AB,BC,CD,DA,AC,BD}

Spanning trees behöver 4-1 = 3 kanter

Exempel: {AB, BC, CD} skapar spanning tree

Annat exempel: {AB, AC, BD} skapar annat spanning tree

Total: kan visa att det finns 16 olika spanning tree

Exempel på olika spanning tree för samma graf

Skogar och skogegenskaper

En skog är en graf där varje sammanhängande komponent är ett träd. Skogar är acykliska men behöver inte vara sammanhängande. Om en skog har k komponenter och n noder, har den n-k kanter. Skogar förekommer naturligt när man tar bort kanter från träd.

Definition av skog: acyklisk graf (union av träd)

Skog med n noder och k komponenter har n-k kanter

Analys av skog

Skog med 10 noder och 3 komponenter:

· Komponent 1: träd med 4 noder (3 kanter)

· Komponent 2: träd med 3 noder (2 kanter)

· Komponent 3: träd med 3 noder (2 kanter)

· Totalt: 10 noder, 7 kanter = 10-3 kanter ✓

Vanliga misstag

❌ Tro att alla träd ser likadana ut

Träd med samma antal noder kan ha helt olika strukturer och egenskaper

Exempel: 4 noder kan bilda en 'stjärna' (höjd 1) eller en 'kedja' (höjd 3)

❌ Förväxla trädhöjd och träddjup

Höjd mäts från rot till längsta blad, djup mäts från given nod till rot

Exempel: I träd med höjd 3: rot har djup 0, blad har djup 3

❌ Räkna fel antal spanning tree

Antalet spanning tree växer snabbt och kräver systematisk metod

Exempel: Komplett graf K₄ har 16 spanning tree, inte 4 eller 6

Tillämpningar

Datastrukturer

Binära sökträd, heaps, tries och B-träd för effektiv datalagring och sökning

Exempel: Filsystem använder trädstruktur för mappar och filer

Beslutsträd

AI och maskininlärning använder träd för klassificering och regression

Exempel: Medicinska diagnosträd: symtom → tester → diagnos

Nätverksdesign

Minimala spanning tree för att koppla punkter med minimal kostnad

Exempel: Telefomnätverk, vägnät, kabeldragning mellan hus

Övningar

1 Lätt

Ett träd har 15 noder. Hur många kanter har det?

Tips

Använd grundläggande trädegenskap

Visa facit

Ett träd med n noder har alltid n-1 kanter
För 15 noder: 15-1 = 14 kanter

Svar: 14 kanter

2 Lätt

I ett binärt träd med höjd 4, vad är det maximala antalet noder?

Tips

Perfekt binärt träd har maximalt antal noder

Visa facit

Maximalt antal noder i binärt träd med höjd h: 2^(h+1) - 1
För höjd 4: 2^5 - 1 = 32 - 1 = 31 noder
Nivå 0: 1 nod, nivå 1: 2 noder, ..., nivå 4: 16 noder
Total: 1+2+4+8+16 = 31 noder

Svar: 31 noder

3 Medel

En skog har 20 noder och 15 kanter. Hur många träd består skogen av?

Tips

Använd formeln för kanter i skog

Visa facit

Skog med n noder, k komponenter har n-k kanter
20 noder, 15 kanter: 15 = 20 - k
k = 20 - 15 = 5
Skogen består av 5 träd

Svar: 5 träd

Sammanfattning

Träd är sammanhängande acykliska grafer med n-1 kanter för n noder. Rotade träd skapar hierarkier med begrepp som föräldrar och barn. Binära träd är särskilt viktiga med högst 2 barn per nod. Traversering (preorder, inorder, postorder) ger olika sätt att besöka alla noder. Spanning trees och skogar utvidgar begreppen till mer allmänna sammanhang. Träd är fundamentala för datastrukturer och algoritmer.