1. Vad är träd och skog?
Träd
- I grafteori, a träd är en oriktad, sammankopplad och acyklisk graf . Med andra ord, en sammankopplad graf som inte innehåller ens en enda cykel kallas ett träd.
- Ett träd representerar hierarkisk struktur i en grafisk form.
- Trädens element kallas deras noder och trädets kanter kallas grenar.
- Ett träd med n hörn har (n-1) kanter.
- Träd tillhandahåller många användbara applikationer så enkla som ett släktträd till lika komplexa som träd i datastrukturer inom datavetenskap.
- A blad i ett träd finns en vertex av grad 1 eller någon vertex som inte har några barn kallas ett löv.
Exempel
I exemplet ovan är alla träd med färre än 6 hörn.
Skog
I grafteori, a skog är en oriktad, frånkopplad, acyklisk graf . Med andra ord kallas en osammanhängande samling träd som skog. Varje del av en skog är träd.
Exempel
Ovanstående graf ser ut som två undergrafer men det är en enda frånkopplad graf. Det finns inga cykler i diagrammet ovan. Därför är det en skog.
2. Trädens egenskaper
- Varje träd som har minst två hörn bör ha minst två löv.
- Träd har många egenskaper:
Låt T vara en graf med n hörn, då är följande påståenden ekvivalenta:- T är ett träd.
- T innehåller inga cykler och har n-1 kanter.
- T är ansluten och har (n -1) kant.
- T är en sammankopplad graf, och varje kant är en skärkant.
- Varje två hörn av graf T är sammankopplade med exakt en väg.
- T innehåller inga cykler, och för varje ny kant e har grafen T+ e exakt en cykel.
- Varje kant på ett träd är avskuren.
- Att lägga till en kant till ett träd definierar exakt en cykel.
- Varje ansluten graf innehåller ett spännträd.
- Varje träd har minst två hörn av grad två.
3. Spännande träd
A Spanning Tree i en sammankopplad graf är G en undergraf H av G som inkluderar alla hörn av G och är också ett träd.
Exempel
Betrakta följande graf G:
Från ovanstående graf G kan vi implementera följande tre spännande träd H:
Metoder för att hitta det spännande trädet
Vi kan hitta spännträdet systematiskt genom att använda någon av två metoder:
- Nedskärningsmetod
- Uppbyggnadsmetod
1. Nedskärningsmetod
- Börja välja valfri cykel i diagram G.
- Ta bort en av cykelns kanter.
- Upprepa denna process tills det inte finns några cykler kvar.
Exempel
- Betrakta en graf G,
- Om vi tar bort kanten ac som förstör cykeln a-d-c-a i grafen ovan får vi följande graf:
- Ta bort kanten cb, som förstör cykeln a-d-c-b-a från ovanstående graf så får vi följande graf:
- Om vi tar bort kanten ec, som förstör cykeln d-e-c-d från grafen ovan, får vi följande spännträd:
2. Uppbyggnadsmetod
- Välj kanter på graf G en i taget. På ett sådant sätt att det inte finns några cykler skapas.
- Upprepa denna process tills alla hörn är inkluderade.
Exempel
Betrakta följande graf G,
hur man konverterar från int till sträng i java
- Välj kanten ab ,
- Välj kanten av ,
- Efter det väljer du kanten ec ,
- Välj sedan kanten cb , så får vi äntligen följande spännträd:
Circuit Rank
Antalet kanter vi behöver ta bort från G för att få ett spännträd.
Spännande träd G = m- (n-1) , som kallas krets rang av G.
Where, m = No. of edges. n = No. of vertices.
Exempel
I grafen ovan är kanterna m = 7 och hörnen n = 5
Då är kretsrankningen,
G = m - (n - 1) = 7 - (5 - 1) = 3