Kostra grafu
V teórii grafov je kostra grafu množina všetkých vrcholov a určitá podmnožina hrán pôvodného grafu. Podmnožina hrán musí spĺňať podmienku, že ak v pôvodnom grafe existovala z vrcholu v do vrcholu u cesta, tak existuje aj v kostre. V neorientovanom grafe G je kostra podgraf G - strom T taký, že existuje cesta medzi ľubovolnými dvoma vrcholmi grafu G len po hranách stromu T. Najlacnejšia kostra je taká, ktorá ma spomedzi všetkých kostier G minimálny súčet ohodnotení.
^ TOPZákladná vlastnosť
Kostry v neorientovaných grafoch majú dôležitú vlastnosť, ktorá umožnuje vytvoriť algoritmus konštruujúci pre daný
graf G najlacnejšiu kostru. Táto vlastnosť znie nasledovne (uvádzané bez dôkazu):
Pre ľubovolné rozdelenie vrcholov grafu G do dvoch disjunktných množín V a
W, obsahuje minimálna kostra grafu najkratšiu z hrán, ktoré vedú medzi V a
W.
Algoritmy
- Kruskalov algoritmus
- Algoritmus je priamo založený na uvedenej vlastnosti kostier. Pred hľadaním si usporiadame hrany podľa ich ceny. Potom ich postupne vyberáme a skúšame ich pridať ku kostre T (začína sa s prázdnou kostrou). Ak vznikne pridaním hrany cyklus, hranu vynecháme a pokračujeme ďalšou.
- Primov algoritmus
- Tento algoritmus postupne pridáva do kostry vrcholy. Začneme (s prázdnou kostrou) v ľubovolnom vrchole grafu. V jednom kroku algoritmu priberieme vrchol v taký, že hrana e=(u,v) je najlacnejšia zo všetkých hrán, pre ktoré platí, že u je z T a v je z G–T.