Разапињуће стабло минималног степена

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

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

У теорији графова, за повезан граф G, разапињуће стабло T је подграф G, са најмањим бројем ивица које разапињу G. Различити број својстава о T може бити доказано. T је ациклично, има (|V|-1) ивица где је V број чворова у G и тако даље.

Разапињуће стабло минималног степена T' је разапињуће стабло које има најмањи могући степен. Чвор највећег степена у T' је најмањег степена међу свим чворовима у G.

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

Види још[уреди]