Predstavme si situáciu, že máme vybudovaných sedem stanovíšť a chceme medzi nimi natiahnuť telefónne káble tak, aby sa dalo dovolať z každého stanovišťa na všetky ostatné. Jedno z riešení vidíme aj na obrázku.

Ako môže vyzerať riešenie tejto úlohy? Predstavme si, že jednotlivé stanovištia sú vrcholy grafu a telefónne káble sú hrany. Aby sa dalo dovolať z každého stanovišťa na ľubovoľné iné, musí byť graf súvislý. Naviac, zrejme nemá zmysel, aby graf obsahoval cyklus, lebo ak z neho odstránime ľubovoľnú hranu, požiadavky v úlohe budú stále splnené. Teda akákoľvek kostra kompletného grafu s danými vrcholmi je riešením úlohy.

V praxi je však dôležité nájsť také riešenie, aby bolo čo najlacnejšie, teda aby sme potrebovali natiahnuť čo najmenej telefónneho kábla. Spomedzi všetkých kostier teda hľadáme takú, pri ktorej je súčet vzdialeností, ktoré predstavujú hrany, čo najkratší.

Všimnime si, že pri takýchto úlohách sú jednotlivým hranám grafu priradené čísla (napríklad ich vzdialenosti). Takéto grafy budeme nazývať ohodnotené a presne si ich zadefinujeme na nasledujúcej obrazovke. Naviac, povieme si aj spôsob, ako nájsť minimálnu kostru v takýchto grafoch.