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

vlak

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

Vedomosti v hodnote stoviek tisíc získaš za pár eur

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émiovej sekcie.

Obsah článku spadá pod licenciu Premium, kúpou článku súhlasíš s Prevádzkovými podmienkami.

Čo od nás v ďalších lekciách dostaneš?
  • 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.
Článok pre vás napísal Ondřej Michálek
Avatar
Autor se věnuje teoretické informatice. Ve svých volných chvílích nepohrdne šálkem dobrého čaje, kaligrafickým brkem a foukací harmonice.
Aktivity