Минимално разапињуће стабло

Граф на коме је подебљаном линијом означено његово минимално разапињуће стабло

Минимално разапињуће стабло је стабло неког неусмреног графа које садржи све чворове тог графа, а збир дужина његових грана је минималан. Један граф може имати више оваквих стабала, зависно од своје конфигурације.

Типичан проблем који се везује за ово стабло је на пример достављање услуга кабловске телевизије на више локација на што исплативији начин. Рецимо да се знају места на која треба доставити услугу и цена поставања кабла између сваког од њих. На некима од тих места ће бити потребна мања дужина кабла него на другим, а на неким ће трошкови постављања бити повољнији, те су иста аутоматски пожељнија од стране добављача услуге. Уколико се свако од могућих места између локација представи одговарајућом ценом постављања кабла, налажењем минималног разапињућег стабла тако формираног графа се долази до оптималног решења проблема.