Hľadanie kostry grafu
V dnešnej lekcii sa budeme zaoberať kostrou grafu. Než sa však pustíme do riešenia problému ako ju nájsť, ujasníme si, čo že to vlastne tá kostra je a prečo je pre nás dôležitá.
Kostra grafu
Kostra grafu je podgraf, kedy medzi každými dvoma vrcholmi existuje práve jedna cesta. To znamená, že všetky vrcholy v grafe sú prepojené, ale graf nemá žiadne "hrany navyše", preto kostra, bez jedinej hrany by sa už rozsypal:) Keďže definícia nijako neobmedzuje ako hrany vybrať, jeden graf teda môže mať viac rôznych kostier.
Ak by sme to chceli povedať trochu na úrovni, potom kostra grafu
G(V, E), kde V je množina vrcholov a E
je množina hrán, je graf G'(V, E'), kde E' je
podmnožina E taká, že neobsahuje cyklus.
Všimnite si, že graf a jeho kostra majú teda logicky rovnakú množinu
vrcholov V.
Ak stále nerozumiete písmenkám V a
E, odporúčam prečítať si Úvod do
grafových algoritmov.
Príklad využitia kostry grafu
Majme sieť miest, medzi ktorými chceme natiahnuť koľaje. Chceme ale
minimalizovať náklady, takže budeme chcieť, aby vždy existovala z mesta
A do mesta B len jedna cesta. Medzi mestami však sú
rôzne údolia a rokliny, cena trati sa líši v jednotlivých úsekoch
nielen
...koniec náhľadu článku...
Pokračuj ďalej
Minul si až sem a to je super! Veríme, že ti prvé lekcie ukázali niečo nového a užitočného.
Chceš v kurze pokračovať? Prejdi do prémiové sekcie.
Kúpiť tento kurz
Obsah článku spadá pod licenciu Premium, kúpou článku súhlasíš so zmluvnými podmienkami.
- Neobmedzený a trvalý prístup k jednotlivým lekciím.
- Kvalitné znalosti v oblasti IT.
- Zručnosti, ktoré ti pomôžu získať vysnívanú a dobre platenú prácu.
Popis článku
Požadovaný článok má nasledujúci obsah:
V tutoriálu sa pozrieme na tradičné kombinatoriky problém - nájdenie kostry grafy s najmenšou váhou pomocou troch rôznych algoritmov.
Kredity získaš, keď podporíš našu sieť. To môžeš urobiť buď zaslaním symbolickej sumy na podporu prevádzky alebo pridaním obsahu na sieť.
