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

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