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
xkovar3@fi.muni.cz
část 11
Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 11 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 11 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 11 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 11 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 11 5 / 15
Další pojmy z teorie grafů Kořen a listy stromu
Příklad – syntaktický strom
I saw
a man with
a telescope
.
<sentence>
<clause>
<NP> <PP>
<NP>
<NP> <VP>
<DET> <NP> <PP>
<DET> <NP>
<ends>
Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 11 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 11 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 11 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 11 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 11 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 11 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 11 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 11 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 11 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 11 15 / 15