1. Hva er tre og skog?

Tre

• I grafteori, a tre er en urettet, koblet og asyklisk graf . Med andre ord, en tilkoblet graf som ikke inneholder en eneste syklus kalles et tre.
• Et tre representerer hierarkisk struktur i en grafisk form.
• Elementene til trær kalles deres noder og kantene på treet kalles grener.
• Et tre med n topper har (n-1) kanter.
• Trær gir mange nyttige applikasjoner så enkle som et slektstre til like komplekse som trær i datastrukturer innen informatikk.
• EN blad i et tre er et toppunkt av grad 1 eller ethvert toppunkt uten barn kalles et blad.

Eksempel

I eksemplet ovenfor er alle trær med færre enn 6 topper.

skog

I grafteori, a skog er en urettet, frakoblet, asyklisk graf . Med andre ord er en usammenhengende samling av trær kjent som skog. Hver komponent i en skog er tre.

Eksempel

Grafen ovenfor ser ut som to undergrafer, men det er en enkelt frakoblet graf. Det er ingen sykluser i grafen ovenfor. Derfor er det en skog.

2. Egenskaper til trær

1. Hvert tre som har minst to topper bør ha minst to blader.
2. Trær har mange karakteriseringer:
   La T være en graf med n toppunkter, da er følgende utsagn ekvivalente:
   • T er et tre.
   • T inneholder ingen sykluser og har n-1 kanter.
   • T er koblet sammen og har (n -1) kant.
   • T er koblet graf, og hver kant er en cut-edge.
   • Alle to hjørner av graf T er forbundet med nøyaktig én bane.
   • T inneholder ingen sykluser, og for enhver ny kant e har grafen T+ e nøyaktig én syklus.
3. Hver kant av et tre er kuttet.
4. Å legge til én kant til et tre definerer nøyaktig én syklus.
5. Hver tilkoblet graf inneholder et spenntre.
6. Hvert tre har minst to toppunkter av grad to.

3. Spanning Tree

EN spennende tre i en sammenhengende graf er G en undergraf H av G som inkluderer alle toppunktene til G og er også et tre.

Eksempel

Tenk på følgende graf G:

Fra grafen G ovenfor kan vi implementere følgende tre spennede trær H:

Metoder for å finne det spennede treet

Vi kan finne spenntreet systematisk ved å bruke en av to metoder:

1. Nedskjæringsmetode
2. Oppbyggingsmetode

1. Nedskjæringsmetode

• Begynn å velge hvilken som helst syklus i graf G.
• Fjern en av syklusens kanter.
• Gjenta denne prosessen til det ikke er noen sykluser igjen.

Eksempel

• Tenk på en graf G,

• Hvis vi fjerner kanten ac som ødelegger syklusen a-d-c-a i grafen ovenfor, får vi følgende graf:

• Fjern kanten cb, som ødelegger syklusen a-d-c-b-a fra grafen ovenfor, så får vi følgende graf:

• Hvis vi fjerner kanten ec, som ødelegger syklusen d-e-c-d fra grafen ovenfor, får vi følgende spenntre:

2. Oppbyggingsmetode

• Velg kanter av graf G én om gangen. På en slik måte at det ikke er noen sykluser opprettes.
• Gjenta denne prosessen til alle toppunktene er inkludert.

Eksempel

Tenk på følgende graf G,

• Velg kanten ab ,

• Velg kanten av ,

• Etter det velger du kanten ec ,

• Deretter velger du kanten cb , så får vi til slutt følgende spenntre:

Kretsrangering

Antall kanter vi må slette fra G for å få et spenntre.

Spennende tre G = m- (n-1) , som kalles krets rangering av G.

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

Eksempel

I grafen ovenfor er kantene m = 7 og toppunktene n = 5

Da er kretsrangeringen,

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