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
Došiel 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ť iba tento kurz
Získaj okamžitý prístup ku kurzu bez
časového obmedzenia.
100 kreditov
Obsah článku spadá pod licenciu Premium, kúpou článku súhlasíš so zmluvnými podmienkami.
- Prístup k jednotlivým lekciám podľa spôsobu obstarania.
- 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ť.
