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
- Svako stablo koje ima najmanje dva vrha mora imati najmanje dva lista.
- 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.
- Svaki rub drveta je odsječen.
- Dodavanje jednog ruba stablu definira točno jedan ciklus.
- Svaki povezani graf sadrži razapinjuće stablo.
- 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:
- Metoda rezanja
- 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