1. Što je stablo i šuma?

Drvo

• U teoriji grafova, a drvo je neusmjereni, povezani i aciklički graf . Drugim riječima, povezani graf koji ne sadrži niti jedan ciklus naziva se stablo.
• Stablo predstavlja hijerarhijsku strukturu u grafičkom obliku.
• Elementi stabla nazivaju se njihovim čvorovima, a rubovi stabla granama.
• Stablo s n vrhova ima (n-1) bridova.
• Stabla pružaju mnoge korisne aplikacije od jednostavnih poput obiteljskog stabla do složenih poput stabala u podatkovnim strukturama računalne znanosti.
• A list u stablu je vrh stupnja 1 ili bilo koji vrh koji nema djece naziva se list.

Primjer

U gornjem primjeru, sva su stabla s manje od 6 vrhova.

Šuma

U teoriji grafova, a šuma je neusmjereni, nepovezani, aciklički graf . Drugim riječima, nepovezana zbirka drveća poznata je kao šuma. Svaka komponenta šume je drvo.

Primjer

Gornji graf izgleda kao dva pod-grafa, ali to je jedan nepovezani graf. U gornjem grafikonu nema ciklusa. Stoga je šuma.

2. Svojstva stabala

1. Svako stablo koje ima najmanje dva vrha mora imati najmanje dva lista.
2. Drveće ima mnogo karakteristika:
   Neka je T graf s n vrhova, tada su sljedeće izjave ekvivalentne:
   • T je drvo.
   • T ne sadrži cikluse i ima n-1 bridova.
   • T je povezan i ima (n -1) brid.
   • T je povezani graf, a svaki brid je rezni brid.
   • Bilo koja dva vrha grafa T povezana su točno jednom stazom.
   • T ne sadrži cikluse, a za svaki novi rub e, graf T+ e ima točno jedan ciklus.
3. Svaki rub drveta je odsječen.
4. Dodavanje jednog ruba stablu definira točno jedan ciklus.
5. Svaki povezani graf sadrži razapinjuće stablo.
6. Svako stablo ima najmanje dva vrha drugog stupnja.

3. Razapinjuće stablo

A razapinjuće stablo u povezanom grafu G je podgraf H od G koji uključuje sve vrhove od G i također je stablo.

Primjer

Razmotrite sljedeći grafikon G:

Iz gornjeg grafa G možemo implementirati sljedeća tri razapinjuća stabla H:

Metode za pronalaženje razapinjućeg stabla

Razapinjuće stablo možemo pronaći sustavno pomoću jedne od dvije metode:

1. Metoda rezanja
2. Metoda izgradnje

1. Metoda sječe

• Počnite birati bilo koji ciklus na grafikonu G.
• Uklonite jedan od rubova ciklusa.
• Ponavljajte ovaj postupak dok ne preostane nijedan ciklus.

Primjer

• Razmotrimo graf G,

• Ako uklonimo rub ac koji uništava ciklus a-d-c-a u gornjem grafu, tada ćemo dobiti sljedeći graf:

• Uklonimo brid cb, koji uništava ciklus a-d-c-b-a iz gornjeg grafa, tada dobivamo sljedeći graf:

• Ako uklonimo rub ec, koji uništava ciklus d-e-c-d iz gornjeg grafa, tada ćemo dobiti sljedeće razapinjuće stablo:

2. Metoda nadogradnje

• Odaberite rubove grafa G jedan po jedan. Na takav način da nema ciklusa se stvaraju.
• Ponavljajte ovaj postupak dok ne uključite sve vrhove.

Primjer

Razmotrimo sljedeći grafikon G,

• Odaberite rub ab ,

• Odaberite rub od ,

• Nakon toga odaberite rub ek ,

• Zatim odaberite rub cb , tada konačno dobivamo sljedeće razapinjuće stablo:

Rang kruga

Broj bridova koje trebamo izbrisati iz G da bismo dobili razapinjuće stablo.

Razapinjuće stablo G = m- (n-1) , koji se naziva krugovni rang od G.

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

Primjer

U gornjem grafu, bridovi m = 7 i vrhovi n = 5

Tada je rang kruga,

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