1. Grafy: Pojem grafu, vzdálenost v grafu, Dijkstrův algoritmus pro hledání nejkratší cesty. Stromy a jejich charakterizace, nejkratší cesty v orientovaných stromech. Kostra grafu, problém minimální kostry.
Graf je uspořádaná dvojice množiny vrcholů a množiny hran. Množina hran je množina neuspořádaných dvojich vrcholů.
Graf je z pohledu algebry symetrická nereflexivní binární relace.
Varianty grafů
Pro některé účely je vhodné uvažovat ohodnocené grafy - vrcholy nebo hrany mají nějakou hodnotu (cenu). To má využití například na modelování toků nebo pro navigaci.
Nejobecnějí variantou je multigraf. Multigraf je uspořádaná trojice . představuje indexovou množinu, je funkce z do množiny vrcholů, která mapuje indexy z na (multi)hrany: .
V této definici:
Pro graf je procházka grafem délky . Cesta v grafu je procházka grafem taková, že se v ní každý vrchol procházky vyskytuje právě jednou.
Vzdálenost mezi vrcholy grafu je definovaná jako délka nejkratší cesty v grafu , kde a jsou koncové vrcholy cesty. Vzdálenost je označována jako , případně . Speciální případ: .
Pokud neexistuje prochádzka (cesta) grafem mezi vrcholy a , značíme .
Dijkstrův algoritmus spočítá vzdálenost, resp. nejkratší cesty, mezi jedním vrcholem grafu a ostatními vrcholy, resp. mezi dvěma zvolenými vrcholy.
Algoritmus je reprezentován následovným psedokódem, kde je cenová funkce hrany :
starting vertex
ending vertex
Pozn.: Algortimus do ukládá spracované uzly, je nejbližší nespracovaný uzel.
Strom je acyklický spojitý jednoduchý graf. Uzly stupně 1 jsou označovány jako listy. Každý strom o uzlech má právě hran. Mezi každým párem uzlů vede ve stromě právě jedna cesta.
Přidáním jedné hrany do stromu vznikne právě jeden cyklus. Strom je minimální spojitý graf (je svojí kostrou a minimální kostrou).
Orientovaný strom je strom, jehož hrany jsou orientované. Vrchol, ze kterého existuje v orientovaném stromě cesta do každého vrcholu, se nazývá kořen. Pokud existuje cesta medzi dvěma vrcholy orientovaného stromu, je zároveň nejkratší (vlastnost každého stromu).
Graf má kostru , přičemž je strom. je minimální kostra grafu , pokud je nejmenší ze všech koster grafu .
Problém minimální kostry je problémem nalezení kostry grafu , jejíž suma cen všech hran bude nejmenší možná.
Hladový algoritmus:
Jarníkův algoritmus:
-
DevelX - Martin Jurča
stav - 100 %