Rastezno drvo i minimalno rasprostranjeno stablo

U ovom ćete tutorijalu uz primjere i slike naučiti o rasponu i minimalnom drveću.

Prije nego što naučimo o rasponima stabala, moramo razumjeti dva grafa: neusmjereni i povezani grafovi.

Neusmjereni graf je graf u kojem su rubovi ne ukazuju na bilo kojem smjeru (tj. Rubovi su dvosmjerno).

Neusmjereni grafikon

Povezani graf je grafikon u kojem je uvijek staza od vrha na bilo koji drugi tjeme.

Povezani graf

Rasprostranjeno stablo

Rasprostranjeno stablo podgraf je neusmjerno povezanog grafa, koji uključuje sve vrhove grafa s najmanjim mogućim brojem bridova. Ako je vrh propušten, to nije stablo koje se proteže.

Na rubovima mogu biti dodijeljeni utezi, ali ne moraju.

Ukupan broj raspona stabala s nvrhovima koji se mogu stvoriti iz cjelovitog grafa jednak je .n(n-2)

Ako imamo n = 4, maksimalan broj mogućih rasprostranjenih stabala jednak je . Tako se 16 cjelovitih stabala može oblikovati iz cjelovitog grafa s 4 vrha.44-2 = 16

Primjer rasprostranjenog stabla

Razumijemo rastegnuto stablo sa primjerima u nastavku:

Neka izvorni graf bude:

Normalan graf

Neka od mogućih rasprostranjenih stabala koja se mogu stvoriti iz gornjeg grafikona su:

Rastezno stablo Rastezno drvo Rastezajuće stablo Rastezajuće stablo Rastezajuće stablo Rastezajuće stablo

Minimalno rastezno drvo

Minimalno rastezno stablo je rastezno stablo u kojem je zbroj težine rubova što je moguće manji.

Primjer rasprostranjenog stabla

Shvatimo gornju definiciju uz pomoć primjera u nastavku.

Početni graf je:

Ponderirani graf

Moguća rasprostranjena stabla iz gornjeg grafikona su:

Minimalno rastegljivo stablo - 1 Minimalno rasprostiruće se stablo - 2 Minimalno rastezljivo stablo - 3 Minimalno rasponično stablo - 4

Minimalno rastegljivo stablo od gore navedenih rasprostranjenih stabala je:

Minimalno rasponično stablo

Minimalno stablo raspona iz grafa pronalazi se pomoću sljedećih algoritama:

1. Primov algoritam
2. Kruskalov algoritam

Primjene stabla koje se protežu

• Protokol usmjeravanja računalne mreže
• Analiza klastera
• Planiranje civilne mreže

Primjene minimalnog raspona stabala

• Da biste pronašli putove na karti
• Za projektiranje mreža poput telekomunikacijskih mreža, vodoopskrbnih mreža i električnih mreža.