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ýOhodnocený orientovaný
(neorientovaný) graf(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
Ú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
9
Ú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
10
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
11
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
12
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.
13
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
14
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).
Značkování vrcholů
15
Značkování vrcholů
16
Značkování vrcholů
17
Značkování vrcholů
18
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ší).
19
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.
20
Metoda vede k nalezení nejkratší cesty, za předpokladu, že
hrany mají stejnou hodnotu => nejmenší počet tahů.
Prohledávání do šířky
D
A
B
C
1 2 3 4
D
A
B
C
1 2 3 4
21
Prohledávání do šířky
D
A
B
C
1 2 3 4
D
A
B
C
1 2 3 4
22
Prohledávání do šířky
D
A
B
C
1 2 3 4
D
A
B
C
1 2 3 4
23
Prohledávání do šířky
D
A
B
C
1 2 3 4
D
A
B
C
1 2 3 4
24
Prohledávání do šířky
D
A
B
C
1 2 3 4
D
A
B
C
1 2 3 4
25
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í
26
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.
27
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
Návštěvník zábavního parku
 Chce se dostat na
všechny atrakce
 Atrakce jsou spojeny
elektrickým vláčkem
 Žádné nádraží nechce
navštívit dvakrát
28
Návštěvník zábavního parku
 Naplánuje jednu trasu a
kouká kam až dojde.
 Označí si koncový vrchol a
vrchol, který mu zabránil
v cestě.
29
Návštěvník zábavního parku
 Vrací s e zpět, až k
prvnímu vrcholu, kde
může odbočit.
 Označí hranu, kterou se
vrátil.
 Pokud narazí na další
koncový bod, vrátí se až
za nejbližší vrchol, který
působí konec a začne
hledat znovu
30
Návštěvník zábavního parku
31
Návštěvník zábavního parku
32
Návštěvník zábavního parku
33
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
MATICE DÉLEK
Charakterizuje délky hran mezi jednotlivými
vrcholy. Definice:
38
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:
39
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:
40
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
41
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
42
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č
43
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í...
44