V tej vadnici boste s primeri in slikami izvedeli več o drevesu za raztezanje in minimalnem drevesu.
Preden se naučimo o razponu dreves, moramo razumeti dva grafa: neusmerjene in povezane grafe.
Neusmerjeno graf je graf, v katerem se robovi ne kažejo v vse smeri (npr. Robovi so dvosmerni).
Neusmerjeni graf
Povezan graf je graf, v katerem vedno obstaja pot iz tocke na vsako drugo tocko.
Povezani graf
Raztezajoče se drevo
Obsegajoče drevo je podgraf neusmerjenega povezanega grafa, ki vključuje vse točke grafa z najmanjšim možnim številom robov. Če je oglišče zgrešeno, to ni drevo, ki se razteza.
Robovi imajo lahko dodeljene uteži ali pa tudi ne.
Skupno število zajetih dreves z noglišči, ki jih je mogoče ustvariti iz celotnega grafa, je enako .n(n-2)
Če imamo n = 4, je največje število možnih dreves, ki se raztezajo, enako . Tako lahko iz celotnega grafa s 4 oglišči oblikujemo 16 dreves, ki se raztezajo.44-2 = 16
Primer drevesa, ki se razteza
Razumejmo razpeta drevesa s spodnjimi primeri:
Naj bo izvirni graf:
Običajni graf
Nekaj možnih dreves, ki jih je mogoče ustvariti iz zgornjega grafa, je:
Raztezajoče se drevo 
Raztezajoče se drevo 
Raztezajoče se drevo 
Raztezajoče se drevo 
Raztezajoče se drevo 
Raztegljivo drevo
Najmanjše drevo
Najmanjše razponsko drevo je drevo, pri katerem je vsota teže robov čim manjša.
Primer drevesa, ki se razteza
Razumejmo zgornjo definicijo s pomočjo spodnjega primera.
Začetni graf je:
Uteženi graf
Možna drevesa iz zgornjega grafa so:
Najmanjše drevo - 1 
Minimalno drevo - 2 
Minimalno drevo - 3 
Minimalno drevo - 4
Najmanjše drevo v zgornjem delu je:
Najmanjše drevo
Najmanjše drevo v grafu najdemo z uporabo naslednjih algoritmov:
- Primov algoritem
- Kruškalov algoritem
Programiranje dreves
- Protokol usmerjanja računalniškega omrežja
- Analiza grozdov
- Načrtovanje civilne mreže
Najmanjše število drevesnih aplikacij
- Za iskanje poti na zemljevidu
- Za načrtovanje omrežij, kot so telekomunikacijska omrežja, vodovodna omrežja in električna omrežja.
