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
- Hvert tre som har minst to topper bør ha minst to blader.
- 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.
- Hver kant av et tre er kuttet.
- Å legge til én kant til et tre definerer nøyaktig én syklus.
- Hver tilkoblet graf inneholder et spenntre.
- 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:
- Nedskjæringsmetode
- 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