Aktuálně: Postihly zákazy tvou profesi? Poptávka po ajťácích prudce roste, využij slevové akce 50% výuky zdarma!
Pouze tento týden sleva až 80 % na e-learning týkající se Javy
Discount week - May - 50

Lekce 8 - Hledání kostry grafu

V minulé lekci, Implementace algoritmu Floyd-Warshall - Nejkratší cesty, jsme si ukázali implementaci algoritmu Floyd-Warshall.

V dnešní lekci se budeme zabývat kostrou grafu. Než se však pustíme do řešení problému jak ji najít, ujasníme si, co že to vlastně ta kostra je a proč je pro nás důležitá.

Kostra grafu

Kostra grafu je podgraf, kdy mezi každými dvěma vrcholy existuje právě jedna cesta. To znamená, že všechny vrcholy v grafu jsou propojené, ale graf nemá žádné "hrany navíc", proto kostra, bez jediné hrany by se již rozsypal :) Jelikož definice nijak neomezuje jak hrany vybrat, jeden graf tedy může mít více různých koster.

Pokud bychom to chtěli říci trochu na úrovni, pak kostra grafu G(V, E), kde V je množina vrcholů a E je množina hran, je graf G'(V, E'), kde E' je podmnožina E taková, že neobsahuje cyklus. Všimněte si, že graf a jeho kostra mají tedy logicky stejnou množinu vrcholů V.

Pokud stále nerozumíte písmenkům V a E, doporučuji přečíst si Úvod do grafových algoritmů.

Příklad využití kostry grafu

Vlak

Mějme síť měst, mezi kterými chceme natáhnout koleje. Chceme ale minimalizovat náklady, takže budeme chtít, aby vždy existovala z města A do města B jen jedna cesta. Mezi městy však jsou různá údolí a rokliny, cena trati se liší v jednotlivých úsecích nejen


 

...konec náhledu článku...
Pokračuj dál

Znalosti v hodnotě stovek tisíc získáš za pár korun

Došel jsi až sem a to je super! Věříme, že ti první lekce ukázaly něco nového a užitečného.
Chceš v kurzu pokračovat? Přejdi do prémiové sekce.

Omezená nabídka: Nauč se vše a ušetři

Koupit lekce a funkce postupně a po jednom 40 bodů
Koupit všechny aktuálně dostupné lekce s funkcí odevzdávání úloh za exkluzivní cenu 34 bodů (85 Kč)
Na svém účtu máš aktuálně 0 bodů
Koupí tohoto výhodného balíčku získáš přístup ke všem 9 lekcím s kontrolou a certifikací a ještě navíc ušetříš 15 Kč. Nabídka je omezená pouze pro první lekce z kurzu a obsahuje exkluzivní slevu 15%.
34 bodů získáš za přidání svého článku na síť nebo odpovídá 100 Kč 85 Kč

Pozor, pokud si koupíš pouze tuto lekci, ztratíš nárok na speciální slevu 15% na balíček všech lekcí.

Koupit jen lekci 10 bodů
Na svém účtu máš aktuálně 0 bodů
10 bodů získáš za přidání svého článku na síť nebo odpovídá 25 Kč

Obsah článku spadá pod licenci Premium, koupí článku souhlasíš se smluvními podmínkami.

Co od nás v dalších lekcích dostaneš?
  • Neomezený a trvalý přístup k jednotlivým lekcím.
  • Kvalitní znalosti v oblasti IT.
  • Dovednosti, které ti pomohou získat vysněnou a dobře placenou práci.

Popis článku

Požadovaný článek má následující obsah:

V tutoriálu se podíváme na tradiční kombinatorický problém - nalezení kostry grafy s nejmenší váhou pomocí tří různých algoritmů.

Body získáš, když podpoříš naši síť. To můžeš udělat buď zasláním symbolické částky na podporu provozu nebo přidáním obsahu na síť.

Článek pro vás napsal 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 (6)