Obsah prezentace
 Základní pojmy v teorii o grafech
 Úlohy a prohledávání grafů
 Hledání nejkratších cest
1
Základní pojmy
Vrchol grafu: {množina V}
Je to styčná vazba v grafu, nazývá se též
uzlem, prvkem nebo bodem v grafu.
2
VE: 
2
Hrana grafu: {množina E}
Reprezentuje spojení jednotlivých vrcholů. Toto
spojení vyjadřuje nějaký vztah mezi vrcholy.
Základní pojmy
Orientovaný a neorientovaný graf
V orientovaném grafu jsou vždy orientované hrany, tj. hrany s
definovaným počátečním a koncovým vrcholem.
V neorientovaných grafech se lze pohybovat přes hrany
oběma směry.
),E,V(G 
3
Hrany i vrcholy jsou v četných aplikacích
ohodnoceny Ohodnocený orientovaný
(neorientovaný) graf
Základní pojmy
Sled:
Orientovaný
v1, e1, v2, e2, v3, e5, v4
Neorientovaný
v2, e3, v3, e5, v4, e6, v1
Není sledem
v1, e2, v3, e5, v2, e1, v4
v2
v1
v3
v4
e4
e1
e2
e3
e5
e6
v2
v1
v3
v4
e4
e1
e2
e3
e5
e6
4
Posloupnost vrcholů a hran jak
jdou za sebou.
Základní pojmy
Tah
Sled, kde se neopakují hrany
Cesta
Sled, kde se neopakují vrcholy
r
5
Kořenový strom
- orientovaný graf, kde existuje vrchol r (kořen), ze
kterého jsou všechny vrcholy dostupné a nevede
do něj žádná hrana.
Ukázka grafu – základní pojmy
6
Speciální pojmy
 Hamiltonovská cesta:
Cesta, která projde všemi vrcholy a
každým pouze jedenkrát (turista).
 Eulerův tah:
Tah, který projde všemi hranami a
každou pouze jedenkrát (sedm mostů
v Königsbergu).
7
Popis grafu
 Incidenční maticí – orientace hran (+1, -1)
 Matice sousednosti – počet hran mezi sousedy
 Spojové seznamy – seznamy následníků
 Matice délek – délka hrany mezi vrcholy (i,j)
 Matice vzdáleností
8
Incidenční matice
9
Matice sousednosti
10
Seznam následníků
11
Úlohy s grafy
Grafické znázornění úlohy je názorné a v
jednoduchých případech lze odhalit řešení i bez
použití jakéhokoliv algoritmu.
1) v, k, z, p
2) 0
1) k, z
2) v, p
1) v, z
2) k, p
1) v, k
2) z, p
1) k, z, p
2) v
1) v, z, p
2) k
1) v, k, p
2) z
Nesmí nastat, nebudu kreslit
1) v
2) k, z, p
1) k
2) v, z, p
1) z
2) v, k, p
1) k, p
2) v, z
1) 0
2) v, k, z, p
12
Úloha pro
převozníka:
Vlk, koza, zelí
Vlk, koza, zelí
1) v, k, z, p
2) 0
1) v, z
2) k, p
1) k, z, p
2) v
1) v, z, p
2) k
1) v, k, p
2) z
1) v
2) k, z, p
1) k
2) v, z, p
1) z
2) v, k, p
1) k, p
2) v, z
1) 0
2) v, k, z, p
13
Vlk, koza, zelí
1) v, k, z, p
2) 0
1) v, z
2) k, p
1) k, z, p
2) v
1) v, z, p
2) k
1) v, k, p
2) z
1) v
2) k, z, p
1) k
2) v, z, p
1) z
2) v, k, p
1) k, p
2) v, z
1) 0
2) v, k, z, p
14
Vlk, koza, zelí
1) v, k, z, p
2) 0
1) v, z
2) k, p
1) k, z, p
2) v
1) v, z, p
2) k
1) v, k, p
2) z
1) v
2) k, z, p
1) k
2) v, z, p
1) z
2) v, k, p
1) k, p
2) v, z
1) 0
2) v, k, z, p
15
Prohledávání grafů
Úkolem prohledávání je hledání cesty z daného
výchozího vrcholu do jednotlivých vrcholů grafu. To
může pomoci i při vytváření grafu pro danou úlohu.
16
Tři způsoby prohledávání:
1) Značkování vrcholů
2) Prohledávání do šířky
3) Prohledávání do hloubky
Značkování vrcholů
Vrcholům přiřazujeme značky, pokud vrchol značku má,
pak do něj vede cesta z daného výchozího vrcholu =>
vyjadřuje možnost
17
Výsledek lze převézt na kořenový strom, pokud
zaznamenáme každou použitou hranu a její počáteční a
koncový vrchol.
U neorientovaných grafů má tato metoda malý význam
(pouze u velmi složitých, kde není zřejmé propojení
jednotlivých vrcholů částí grafu).
Algoritmus značkování vrcholů
18
Popis
metoda pro prohledávání grafu od výchozího vrcholu v, při
provádění algoritmu se udělují značky vrcholům, do kterých
vede cesta z výchozího vrcholu
Algoritmus
1. všechny vrcholy v grafu se nastaví jako neoznačkované a
označkuje se vrchol v
2. z pracovního vrcholu se vybere hrana h taková, že její počátek
je ve vrcholu se značkou a její konec je ve vrcholu bez značky
3. je-li nalezena takováto hrana, pak se pokračuje krokem 4,
jinak algoritmus končí a graf je prohledán
4. koncový vrchol hrany h (bez značky) se označkuje, pokračuje
se krokem 2
Značkování vrcholů
19
Značkování vrcholů
20
Značkování vrcholů
21
Značkování vrcholů
22
Značkování vrcholů
Vlastnosti:
Odpovídá na otázku: „Je možné?“
Jednoduchý algoritmus
Malé časové nároky: max V(G) – 1
Nelze jej použít při hledání cest s
určitými vlastnostmi (nejkratší,
nejdelší).
23
Prohledávání grafu do šířky
Algoritmus lze přirovnat ke štěpné reakci. Probíhá tak,
že počátečnímu vrcholu označíme všechny následníky,
pak označíme následníky následníků atd.
24
Metoda vede k nalezení nejkratší cesty, za předpokladu, že
hrany mají stejnou hodnotu => nejmenší počet tahů.
Algoritmus prohledávání do šířky
25
Popis
Tato metoda slouží k prohledávání grafu a to tím způsobem, že se označkují všichni následníci
výchozího vrcholu a dále se označkují všichni následníci těchto následníků atd.. Tato metoda
se využívá pro nalezení nejkratších cest = cest s nejmenším počtem hran (v případě hran
stejných délek).
Algoritmus
 máme orientovaný graf G s výchozím vrcholem v a hledáme všechny vrcholy i, do kterých
vede z vrcholu v orientovaná cesta, máme zjistit nejkratší cestu a její vzdálenost pro každý
vrchol
 každý vrchol bude při prohledávání označkován a budou mu přiděleny hodnoty : vrcholu, ze
kterého jsme do něj přišli a vzdálenost od výchozího vrcholu, dále bude zapotřebí seznam typu
fronta, do kterého budeme ukládat vrcholy, které byly označkovány, ale ještě nebyli
prohledáváni jejich následníci
 při popisu algoritmu označme funkci vzdálenosti jako V(i), funkci předchozího vrcholu jako P(i)
a frontu nazveme jako fronta
1. přidělíme značku vrcholu v a všechny ostatní vrcholy zůstanou beze značky, vrcholu v
přidělíme vzdálenost V(v) = 0 a přidáme vrchol v do fronty
2. zjistíme, je-li ve frontě nějaký vrchol, jestliže není algoritmus končí
3. z fronty odebereme vrchol a budeme s ním pracovat pod názvem i
4. proměnnou j budeme postupně plnit neoznačkovanými vrcholy takovými, kde mezi vrcholem i
a tímto vrcholem je hrana. Vrchol j označkujeme a přidělíme mu předchůdce P(j) = i, dále
nastavíme vzdálenost od výchozího vrcholu V(j) = V(i) + velikost hrany (i -> j) a přidáme
vrchol j do fronty a vrátíme se ke kroku 2
Prohledávání do šířky
D
A
B
C
1 2 3 4
D
A
B
C
1 2 3 4
26
Prohledávání do šířky
D
A
B
C
1 2 3 4
D
A
B
C
1 2 3 4
27
Prohledávání do šířky
D
A
B
C
1 2 3 4
D
A
B
C
1 2 3 4
28
Prohledávání do šířky
D
A
B
C
1 2 3 4
D
A
B
C
1 2 3 4
29
Prohledávání do šířky
D
A
B
C
1 2 3 4
D
A
B
C
1 2 3 4
30
Prohledávání grafu do šířky
Vlastnosti:
Podobné časové nároky jako v případě
značkování vrcholů: max V(G) – 1
Získáme kořenový strom s nejmenším
počtem úrovní
31
Prohledávání do hloubky
Podobá se průzkumu neznámých tras. Je základem pro
další metody. Jdeme do hloubky grafu kam až můžeme
a pak se vracíme a hledáme odbočky, kterými lze dále
pokračovat.
32
Algoritmus je časově náročnější než oba předešlé, avšak
jeho úpravou a zaznamenáváním jednotlivých tras jej lze
využít pro hledání cest splňujících nějakou speciální
podmínku. Například cesta začínající v r a obsahující
všechny vrcholy =Hamiltonovská cesta
Algoritmus prohledávání do hloubky
33
Popis
Prohledávání do hloubky najde v grafu všechny vrcholy do nichž vede orientovaná
cesta, s tím že se algoritmus vrací po nalezené cestě zpět
Algoritmus
 máme orientovaný graf G s výchozím vrcholem v
 aktuální vrchol, ve kterém se nacházíme budeme označovat i a seznam cesta
bude obsahovat cestu k aktuálnímu vrcholu
1. jako aktuální vrchol se nastaví vrchol výchozí (i = v), vyprázdní se seznam cesta
a označkuje se vrchol v a ostatní zůstanou beze značek
2. jako h označíme hranu začínající v i, která ještě nebyla použita, jestliže taková
hrana existuje pokračujeme krokem 3, jinak krokem 5
3. koncový vrchol hrany h označme jako j, je-li vrchol j již označkován pokračujeme
krokem 2, jinak krokem 4
4. do seznamu cesta přidáme hranu h, označkujeme vrchol j a nastavíme výchozí
vrchol na j (i = j), pokračujeme krokem 2
5. jestliže je seznam cesta prázdný algoritmus končí, jinak odebereme ze seznamu
hranu h, její počáteční vrchol označíme jako i a pokračujeme krokem 2
Eulerův tah
 Uzavřený:
 Vrátíme se do stejného vrcholu
34
• Otevřený:
 Skončíme v jiném vrcholu
Eulerův tah
Uzavřený:
 Neorientovaný – vrcholy mají sudý stupeň
 Orientovaný – počet vstupních hran je stejný jako
počet výstupních
35
Otevřený:
• Neorientovaný – obsahuje právě dva vrcholy s lichým
stupněm
• Orientovaný – stejně jako neor. + do jednoho vrcholu musí
hrana vcházet, z druhého vycházet.
Eulerův tah
36
Musí se začít ve spodních
vrcholech!
Sedm mostů v Königsbergu
Nejkratší cesty
Úloha: najít nejkratší cestu
 z daného výchozího vrcholu do daného cílového
vrcholu
 z daného výchozího vrcholu do každého vrcholu
 z každého vrcholu do daného cílového vrcholu
 mezi všemi uspořádanými dvojicemi
37
Lze vynechat smyčky a rovnoběžné hrany
Dijkstrův alg.
38
Slouží k vyhledání nejkratší cesty z počátečního
uzlu do všech ostatních uzlů ohodnoceného grafu
MATICE DÉLEK
Charakterizuje délky hran mezi jednotlivými
vrcholy. Definice:
39
aii= 0,
aij= délka hrany mezi vrcholy i a j;
Pokud zde hrana nevede, pak značím nekonečno.
MATICE VZDÁLENOSTÍ
Charakterizuje vzdálenosti jednotlivých
vrcholů. Definice:
40
uii= 0,
uij= vzdálenost mezi vrcholy i a j;
Pokud do vrcholu j nevede cesta z i pak je uij
rovno nekonečnu.
MATICE VZDÁLENOSTÍ
Matice vzdáleností je přímo maticí nejkratších cest.
Pokud nás nezajímá kudy cesta vede, lze použít k jejímu
výpočtu následující způsoby:
41
1. Upravené násobení matic
2. Floydův algoritmus
MATICE VZDÁLENOSTÍ
Floydův algoritmus:
)j,k(U)k,i(U)j,i(U)j,k(U)k,i(U)j,i(U 
ij
kj
ik
42
Podmínka:
MATICE VZDÁLENOSTÍ
Příklad: Minimální náklady na dopravu zboží
1
2
4
5
3
11 Kč
6 Kč
5 Kč
4 Kč
3 Kč
7 Kč
8 Kč
3 Kč
2 Kč
0 86
7
11
1 2 3 4 5
1
2
3
4
5
0
0
0
0
0
3
3
86
4 2
57
11
1 2 3 4 5
1
2
3
4
5
0
0
0
0
3
3
4 2
5
0 86
7
11
1 2 3 4 5
1
2
3
4
5
0
0
0
0
3
3
4 2
518 15
0 86
7
11
1 2 3 4 5
1
2
3
4
5
0
0
0
0
3
3
4 2
518 15
14
43
MATICE VZDÁLENOSTÍ
Příklad: Minimální náklady na dopravu zboží
1
2
4
5
3
11 Kč
6 Kč
5 Kč
4 Kč
3 Kč
7 Kč
8 Kč
3 Kč
2 Kč
0 86
7
11
1 2 3 4 5
1
2
3
4
5
0
0
0
0
3
3
4 2
518 8
14 0 86
7
11
1 2 3 4 5
1
2
3
4
5
0
0
0
0
3
3
4 2
518 8
10
7 5
0 86
7
11
1 2 3 4 5
1
2
3
4
5
0
0
0
0
3
3
4 2
518 8
10
7 5
10
12
9
8
7
11
Součty
35 Kč
32 Kč
27 Kč
22 Kč
38 Kč
44
Závěrem
 Použití grafů je názornou pomůckou při řešení
složitých problémů.
 Složitá řešení se zpravidla již neobejdou bez
použití výpočetní techniky.
 Byl to jen letmý úvod, grafy se dále zabývají
toky, hledání cyklů, nejlevnějších tahů, úlohami
o párování…
45