1. Hvad er træ og skov?

Træ

• I grafteori, en træ er en urettet, forbundet og acyklisk graf . Med andre ord kaldes en forbundet graf, der ikke indeholder en enkelt cyklus, et træ.
• Et træ repræsenterer hierarkisk struktur i en grafisk form.
• Træernes elementer kaldes deres noder, og træets kanter kaldes grene.
• Et træ med n toppunkter har (n-1) kanter.
• Træer giver mange nyttige applikationer lige så enkle som et stamtræ til lige så komplekse som træer i datastrukturer inden for datalogi.
• EN blad i et træ er et toppunkt af grad 1 eller ethvert toppunkt uden børn kaldes et blad.

Eksempel

I ovenstående eksempel er alle træer med færre end 6 hjørner.

Skov

I grafteori, en Skov er en urettet, afbrudt, acyklisk graf . Med andre ord er en usammenhængende samling af træer kendt som skov. Hver komponent i en skov er træ.

Eksempel

Ovenstående graf ligner en to undergrafer, men det er en enkelt afbrudt graf. Der er ingen cyklusser i ovenstående graf. Derfor er det en skov.

2. Træers egenskaber

1. Hvert træ, der har mindst to toppunkter, skal have mindst to blade.
2. Træer har mange karakteristika:
   Lad T være en graf med n toppunkter, så er følgende udsagn ækvivalente:
   • T er et træ.
   • T indeholder ingen cyklusser og har n-1 kanter.
   • T er forbundet og har (n -1) kant.
   • T er forbundet graf, og hver kant er en cut-edge.
   • Enhver to hjørner af grafen T er forbundet med nøjagtig én vej.
   • T indeholder ingen cyklusser, og for enhver ny kant e har grafen T+ e nøjagtig en cyklus.
3. Hver kant af et træ er afskåret.
4. Tilføjelse af en kant til et træ definerer præcis én cyklus.
5. Hver forbundet graf indeholder et spændingstræ.
6. Hvert træ har mindst to hjørner af grad to.

3. Spændende træ

EN spændende træ i en sammenhængende graf er G en undergraf H af G, der omfatter alle hjørnerne af G og også er et træ.

Eksempel

Overvej følgende graf G:

Fra ovenstående graf G kan vi implementere følgende tre spændende træer H:

Metoder til at finde det spændende træ

Vi kan finde spændingstræet systematisk ved at bruge en af ​​to metoder:

1. Nedskæringsmetode
2. Opbygningsmetode

1. Nedskæringsmetode

• Begynd at vælge en hvilken som helst cyklus i graf G.
• Fjern en af ​​cyklussens kanter.
• Gentag denne proces, indtil der ikke er nogen cyklusser tilbage.

Eksempel

• Overvej en graf G,

• Hvis vi fjerner kanten ac, som ødelægger cyklussen a-d-c-a i ovenstående graf, får vi følgende graf:

• Fjern kanten cb, som ødelægger cyklussen a-d-c-b-a fra ovenstående graf, så får vi følgende graf:

• Hvis vi fjerner kanten ec, som ødelægger cyklussen d-e-c-d fra ovenstående graf, får vi følgende spændingstræ:

2. Opbygningsmetode

• Vælg kanter af graf G én ad gangen. På en sådan måde, at der ikke er nogen cyklusser oprettes.
• Gentag denne proces, indtil alle hjørnerne er inkluderet.

Eksempel

Overvej følgende graf G,

• Vælg kanten ab ,

• Vælg kanten af ,

• Vælg derefter kanten ec ,

• Vælg derefter kanten cb , så får vi endelig følgende spændingstræ:

Kredsløbsrang

Antallet af kanter, vi skal slette fra G for at få et spændingstræ.

Spændende træ G = m- (n-1) , som kaldes kredsløbsrang af G.

 Where, m = No. of edges. n = No. of vertices. 

Eksempel

I ovenstående graf er kanterne m = 7 og hjørnerne n = 5

Så er kredsløbsrangen,

 G = m - (n - 1) = 7 - (5 - 1) = 3