Razapinjuće stablo

Razapinjuće stablo (plavo) u grafu

Razapinjuće stablo, pojam iz teorije grafova. Ako je graf povezan i neusmjeren, razapinjuće stablo u tom grafu je podgraf koji je stablo i razapinje taj graf. Stablo težine (tj. zbroja težina njegovih bridova) manje ili jednake težini svakog drugog razapinjućeg stabla u težinskom grafu predstavlja minimalno razapinjuće stablo u tom grafu.

Razapinjući podgraf grafa $G=(V,E)$ je graf oblika $G^{\prime }=(V,E^{\prime })$, gdje je $E^{\prime }\subseteq E$.