1. Kaj je drevo in gozd?

Drevo

• V teoriji grafov je a drevo je neusmerjeni, povezani in aciklični graf . Z drugimi besedami, povezan graf, ki ne vsebuje niti enega cikla, imenujemo drevo.
• Drevo predstavlja hierarhično strukturo v grafični obliki.
• Elemente dreves imenujemo njihova vozlišča, robove drevesa pa veje.
• Drevo z n vozlišči ima (n-1) robov.
• Drevesa ponujajo številne uporabne aplikacije, tako preproste kot družinsko drevo do tako zapletene kot drevesa v podatkovnih strukturah računalništva.
• A list v drevesu je oglišče stopnje 1 ali vsako oglišče, ki nima otrok, se imenuje list.

Primer

V zgornjem primeru so vsa drevesa z manj kot 6 vozlišči.

Gozd

V teoriji grafov je a gozd je neusmerjen, nepovezan, acikličen graf . Z drugimi besedami, nepovezana zbirka dreves je znana kot gozd. Vsak del gozda je drevo.

Primer

Zgornji graf je videti kot dva podgrafa, vendar je en nepovezan graf. V zgornjem grafu ni ciklov. Zato je gozd.

2. Lastnosti dreves

1. Vsako drevo, ki ima vsaj dve oglišči, mora imeti vsaj dva lista.
2. Drevesa imajo številne značilnosti:
   Naj bo T graf z n vozlišči, potem so naslednje izjave enakovredne:
   • T je drevo.
   • T ne vsebuje ciklov in ima n-1 robov.
   • T je povezan in ima (n -1) rob.
   • T je povezan graf in vsak rob je rez.
   • Katerikoli dve točki grafa T sta povezani z natanko eno potjo.
   • T ne vsebuje ciklov in za vsak nov rob e ima graf T+ e natanko en cikel.
3. Vsak rob drevesa je odrezan.
4. Dodajanje enega roba drevesu definira točno en cikel.
5. Vsak povezan graf vsebuje vpeto drevo.
6. Vsako drevo ima vsaj dve točki druge stopnje.

3. Vpeto drevo

A vpeto drevo v povezanem grafu G je podgraf H od G, ki vključuje vsa oglišča od G in je tudi drevo.

Primer

Razmislite o naslednjem grafu G:

Iz zgornjega grafa G lahko implementiramo naslednja tri vpeta drevesa H:

Metode za iskanje vpetega drevesa

Vpeto drevo lahko sistematično najdemo z uporabo ene od dveh metod:

1. Metoda rezanja
2. Metoda gradnje

1. Metoda rezanja

• Začnite izbirati kateri koli cikel v grafu G.
• Odstranite enega od robov cikla.
• Ta postopek ponavljajte, dokler ne ostane noben cikel.

Primer

• Razmislite o grafu G,

• Če odstranimo rob ac, ki uniči cikel a-d-c-a v zgornjem grafu, dobimo naslednji graf:

• Odstranimo rob cb, ki uniči cikel a-d-c-b-a iz zgornjega grafa in dobimo naslednji graf:

• Če odstranimo rob ec, ki uniči cikel d-e-c-d iz zgornjega grafa, dobimo naslednje vpeto drevo:

2. Metoda gradnje

• Izberite robove grafa G enega za drugim. Na tak način, da ni ustvarjenih ciklov.
• Ta postopek ponavljajte, dokler niso vključena vsa oglišča.

Primer

Razmislite o naslednjem grafu G,

• Izberite rob ab ,

• Izberite rob od ,

• Po tem izberite rob ek ,

• Nato izberite rob cb , potem končno dobimo naslednje vpeto drevo:

Uvrstitev kroga

Število robov, ki jih moramo izbrisati iz G, da dobimo vpeto drevo.

Vpeto drevo G = m- (n-1) , ki se imenuje mesto kroga od G.

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

Primer

V zgornjem grafu je robov m = 7 in oglišč n = 5

Potem je rang vezja,

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