Základy matematiky a statistiky pro humanitní obory II Pavel Rychlý Vojtěch Kovář Fakulta informatiky, Masarykova univerzita Botanická 68a, 602 00 Brno, Czech Republic {pary, xkovar3}@fi.muni.cz část 3 Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 3 1 / 15 Obsah přednášky Obsah přednášky Další pojmy z teorie grafů Algoritmy procházení grafu Kruskalův algoritmus Dijkstrův algoritmus Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 3 2 / 15 Další pojmy z teorie grafů Souvislé komponenty Souvislé komponenty Souvislé komponenty největší souvislé podgrafy → mezi každými dvěma vrcholy existuje cesta Silně souvislé komponenty v případě orientovaných grafů mezi každými dvěma vrcholy existuje cesta tam i zpět Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 3 3 / 15 Další pojmy z teorie grafů Vzdálenost v grafu Vzdálenost v grafu Délka cesty neohodnocený graf: počet hran v cestě ohodnocený graf: součet ohodnocení jednotlivých hran v cestě Vzdálenost mezi dvěma vrcholy X a Y je délka nejkratší cesty z X do Y Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 3 4 / 15 Další pojmy z teorie grafů Kořen a listy stromu Kořen a listy stromu Kořen stromu jeden vyznačený vrchol kreslíme většinou nahoře :) Listy stromu vrcholy stupně 1, které nejsou kořenem kreslíme většinou dole Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 3 5 / 15 Další pojmy z teorie grafů Kořen a listy stromu Příklad – syntaktický strom I saw a man with a telescope . Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 3 6 / 15 Další pojmy z teorie grafů Kostra grafu Kostra grafu Podgraf, který obsahuje všechny vrcholy původního grafu je strom → musíme odstranit všechny cykly Minimální kostra grafu pro ohodnocený graf kostra s nejmenším součtem ohodnocení hran analogicky maximální kostra Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 3 7 / 15 Algoritmy procházení grafu Procházení grafu Procházení grafu Např. hledáme určitý vrchol, chceme projít všechny, ... Procházení do hloubky – depth-first search začínáme z nějakého vrcholu, ten označíme označíme libovolný sousední neoznačený vrchol a pokračujeme z něj pokud to dál nejde (všechny sousední vrcholy jsou označené), vrátíme se k nejbližšímu vrcholu, ze kterého to ještě jde Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 3 8 / 15 Algoritmy procházení grafu Procházení grafu Procházení grafu Procházení do šířky – breadth-first search začínáme z nějakého vrcholu, ten označíme vybereme všechny sousední neoznačené vrcholy a přidáme je do seznamu postupně ze začátku seznamu odebíráme a provádíme předchozí kroky končíme, když je seznam prázdný Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 3 9 / 15 Algoritmy procházení grafu Procházení grafu Procházení do hloubky z vrcholu u DFS(G, u) ============ označ u for všechny hrany (u, v) vycházející z vrcholu u: if v není označen: DFS(G, v) Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 3 10 / 15 Algoritmy procházení grafu Procházení grafu Procházení do šířky z vrcholu u BFS(G, u) ============ Q = [u] while Q je neprázdný: odstraň první prvek z Q a přiřaď jej do t označ t přidej všechny neoznačené sousedy t na konec Q Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 3 11 / 15 Kruskalův algoritmus Kruskalův algoritmus Kruskalův algoritmus Vstup neorientovaný graf G ohodnocení hran w Výstup minimální kostra grafu G Algoritmus je tzv. hladový v každém kroku vybírá lokálně optimální možnost Idea setřídit hrany podle ohodnocení v každém kroku přidat do kostry tu nejmenší, která nevytvoří cyklus udržujeme si seznam souvislých komponent kostry Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 3 12 / 15 Kruskalův algoritmus Kruskalův algoritmus Kruskalův algoritmus (G, w) K ← [ ]; comp ← {} for u in G(V ): comp[u] ← set(u) setřiď G(E) podle w for (u, v) in G(E): if comp[u] = comp[v] : K.append((u, v)) newset = union(comp[u], comp[v]) for x in newset : comp[x] ← newset K je minimální kostra grafu Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 3 13 / 15 Dijkstrův algoritmus Dijkstrův algoritmus Dijkstrův algoritmus Vstup graf s hranami ohodnocenými funkcí w ohodnocení hran musí být nezáporné počáteční vrchol s Výstup vzdálenosti z vrcholu s do všech dalších vrcholů grafu Idea udržujeme si nejmenší známé vzdálenosti do všech vrcholů na začátku nekonečno procházíme postupně vrcholy a hodnoty upravujeme Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 3 14 / 15 Dijkstrův algoritmus Dijkstrův algoritmus Dijkstrův algoritmus (G, s) for u in G(V ): d[u] ← infinity d[s] ← 0 N ← G(V ) p ← {} while N = [ ]: u ← vrchol z N s nejmenší hodnotou d[u] for všechny hrany (u, x) vycházející z vrcholu u: alt ← d[u] + w((u, x)) if alt < d(x) : d[x] ← alt; p[x] ← u odstraň u z N d jsou vzdálenosti vrcholů z vrcholu s p obsahuje předchozí vrcholy na nejkratší cestě z s Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 3 15 / 15