Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Drsná matematika III ­ 12. demonstrovaná cvičení
Martin Panák
Masarykova univerzita
Fakulta informatiky
5.12. 2006
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
1 Výsledky písemné práce
Skupina 1
Skupina 2
Skupina 3
Skupina 4
2 Domácí úlohy z minulého týdne
Příklad 2
Příklad 3
3 Floydův algoritmus
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Příklad 1. Označme vrcholy v grafu K5 postupně čísly 1, 2,. . . 5 a
každou hranu i, j, i = 1, . . . , 5 ohodnoťme číslem 1, pokud je
(i + j) liché, číslem 2, pokud je (i + j) sudé. Kolik existuje různých
maximálních koster v tomto grafu?
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Příklad 1. Označme vrcholy v grafu K5 postupně čísly 1, 2,. . . 5 a
každou hranu i, j, i = 1, . . . , 5 ohodnoťme číslem 1, pokud je
(i + j) liché, číslem 2, pokud je (i + j) sudé. Kolik existuje různých
maximálních koster v tomto grafu?
Řešení. 18. 2
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Příklad 2. Označme vrcholy v grafu K6 postupně čísly 1, 2,. . . 6.
Kterou hranu grafu K6 objeví algoritmus ,,prohledávání do šířky ,
bude-li počátečním vrcholem vrchol 5 a hrany ze zpracovávaného
vrcholu budeme procházet postupně podle velikosti druhého
koncového vrcholu hrany (od nejmenšího).
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Příklad 2. Označme vrcholy v grafu K6 postupně čísly 1, 2,. . . 6.
Kterou hranu grafu K6 objeví algoritmus ,,prohledávání do šířky ,
bude-li počátečním vrcholem vrchol 5 a hrany ze zpracovávaného
vrcholu budeme procházet postupně podle velikosti druhého
koncového vrcholu hrany (od nejmenšího).
Řešení. (5, 1), (5, 2), (5, 3), (5, 4), (5, 6), (1, 2), (1, 3),. . . , (4, 6).
2
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Příklad 3. Určete maximální tok a jemu odpovídající minimální řez
v následujícím ohodnoceném orientovaném grafu:
01 01
01
0101
01 01
20
18
3
7
5 10
7
11
9
12
8
20
17
10
11
9
11
Z
S
A B
C D
E F
7
2
2
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Příklad 3. Určete maximální tok a jemu odpovídající minimální řez
v následujícím ohodnoceném orientovaném grafu:
01 01
01
0101
01 01
20
18
3
7
5 10
7
11
9
12
8
20
17
10
11
9
11
Z
S
A B
C D
E F
7
2
2
Řešení. Min. řez je dán množinou {Z, A, E}. Hodnota je 32. 2
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Příklad 1. Označme vrcholy v grafu K5 postupně čísly 1, 2,. . . 5 a
každou hranu {i, j}, i = 1, . . . , 5 ohodnoťme číslem 1, pokud je
(i + j) liché, číslem 2, pokud je (i + j) sudé. Kolik existuje různých
minimálních koster v tomto grafu?
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Příklad 1. Označme vrcholy v grafu K5 postupně čísly 1, 2,. . . 5 a
každou hranu {i, j}, i = 1, . . . , 5 ohodnoťme číslem 1, pokud je
(i + j) liché, číslem 2, pokud je (i + j) sudé. Kolik existuje různých
minimálních koster v tomto grafu?
Řešení. 12. 2
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Příklad 2. Označme vrcholy v grafu K6 postupně čísly 1, 2,. . . 6.
Napište posloupnost hran grafu K6 tak, jak je bude procházet
algoritmus ,,prohledávání do hloubky , bude-li počátečním
vrcholem vrchol 5 a hrany ze zpracovávaného vrcholu budeme
procházet postupně podle velikosti druhého koncového vrcholu
hrany (od nejmenšího).
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Příklad 2. Označme vrcholy v grafu K6 postupně čísly 1, 2,. . . 6.
Napište posloupnost hran grafu K6 tak, jak je bude procházet
algoritmus ,,prohledávání do hloubky , bude-li počátečním
vrcholem vrchol 5 a hrany ze zpracovávaného vrcholu budeme
procházet postupně podle velikosti druhého koncového vrcholu
hrany (od nejmenšího).
Řešení. (5, 1), (5, 2), (5, 3), (5, 4), (5, 6), (6, 1),. . . (1, 2) 2
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Příklad 3. Určete maximální tok a jemu odpovídající minimální řez
v následujícím ohodnoceném orientovaném grafu:
01 01
01
0101
01 01
10
20
30
9
9
19
20
20
5
10
8
9 7
4
8
11
5
9
12
14
Z
S
A B
C D
E F
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Příklad 3. Určete maximální tok a jemu odpovídající minimální řez
v následujícím ohodnoceném orientovaném grafu:
01 01
01
0101
01 01
10
20
30
9
9
19
20
20
5
10
8
9 7
4
8
11
5
9
12
14
Z
S
A B
C D
E F
Řešení. Min. řez odpovídá množině (B, D, S). Hodnota je 40. 2
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Příklad 1. Označme vrcholy v grafu K6 postupně čísly 1, 2,. . . 6 a
každou hranu i, j, i = 1, . . . , 6 ohodnoťme číslem 1, pokud je
(i + j) dává zbytek 1 po dělení třemi, číslem 2, pokud je (i + j)
dává zbytek 2 po dělení třemi a konečně číslem 3, pokud je (i + j)
dělitelné třemi. Kolik existuje různých minimálních koster v tomto
grafu?
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Příklad 1. Označme vrcholy v grafu K6 postupně čísly 1, 2,. . . 6 a
každou hranu i, j, i = 1, . . . , 6 ohodnoťme číslem 1, pokud je
(i + j) dává zbytek 1 po dělení třemi, číslem 2, pokud je (i + j)
dává zbytek 2 po dělení třemi a konečně číslem 3, pokud je (i + j)
dělitelné třemi. Kolik existuje různých minimálních koster v tomto
grafu?
Řešení. 16. 2
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Příklad 2. Označme vrcholy v grafu K6 postupně čísly 1, 2,. . . 6.
Napište posloupnost hran grafu K6 tak, jak je bude procházet
algoritmus ,,prohledávání do hloubky , bude-li počátečním
vrcholem vrchol 3 a hrany ze zpracovávaného vrcholu budeme
procházet postupně podle velikosti druhého koncového vrcholu
hrany (od nejmenšího).
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Příklad 2. Označme vrcholy v grafu K6 postupně čísly 1, 2,. . . 6.
Napište posloupnost hran grafu K6 tak, jak je bude procházet
algoritmus ,,prohledávání do hloubky , bude-li počátečním
vrcholem vrchol 3 a hrany ze zpracovávaného vrcholu budeme
procházet postupně podle velikosti druhého koncového vrcholu
hrany (od nejmenšího).
Řešení. (3, 1), (3, 2), (3, 4), (3, 5), (3, 6), (6, 1), (6, 2), (6, 4),
(6, 5), (5, 1), (5, 2), (5, 4), (4, 1), (4, 2), (2, 1). 2
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Příklad 3. Určete maximální tok a jemu odpovídající minimální řez
v následujícím ohodnoceném orientovaném grafu:
01 01
01
0101
01 01
13
19
23
8
7
11
9 7
10
15
14
7
17
23
11
9
20
15
10
2
Z S
A B
C D
E F
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Příklad 3. Určete maximální tok a jemu odpovídající minimální řez
v následujícím ohodnoceném orientovaném grafu:
01 01
01
0101
01 01
13
19
23
8
7
11
9 7
10
15
14
7
17
23
11
9
20
15
10
2
Z S
A B
C D
E F
Řešení. Řez je dán množinou {F, S, D}, hodnota je 29. 2
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Příklad 1. Označme vrcholy v grafu K6 postupně čísly 1, 2,. . . 5 a
každou hranu i, j, i = 1, . . . , 6 ohodnoťme číslem 1, pokud je
(i + j) dává zbytek 1 po dělení třemi, číslem 2, pokud je (i + j)
dává zbytek 2 po dělení třemi a konečně číslem 3, pokud je (i + j)
dělitelné třemi. Kolik existuje různých maximálních koster v tomto
grafu?
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Příklad 1. Označme vrcholy v grafu K6 postupně čísly 1, 2,. . . 5 a
každou hranu i, j, i = 1, . . . , 6 ohodnoťme číslem 1, pokud je
(i + j) dává zbytek 1 po dělení třemi, číslem 2, pokud je (i + j)
dává zbytek 2 po dělení třemi a konečně číslem 3, pokud je (i + j)
dělitelné třemi. Kolik existuje různých maximálních koster v tomto
grafu?
Řešení. 16. 2
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Příklad 2. Označme vrcholy v grafu K6 postupně čísly 1, 2,. . . 6.
Napište posloupnost hran grafu K6 tak, jak je bude procházet
algoritmus ,,prohledávání do šířky , bude-li počátečním vrcholem
vrchol 3 a hrany ze zpracovávaného vrcholu budeme procházet
postupně podle velikosti druhého koncového vrcholu hrany (od
nejmenšího).
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Příklad 2. Označme vrcholy v grafu K6 postupně čísly 1, 2,. . . 6.
Napište posloupnost hran grafu K6 tak, jak je bude procházet
algoritmus ,,prohledávání do šířky , bude-li počátečním vrcholem
vrchol 3 a hrany ze zpracovávaného vrcholu budeme procházet
postupně podle velikosti druhého koncového vrcholu hrany (od
nejmenšího).
Řešení. (3, 1), (3, 2), (3, 4), (3, 5), (3, 6), (1, 2), (1, 4), (1, 5),
(1, 6), (2, 4), (2, 5), . . . (5, 6). 2
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Příklad 3. Určete maximální tok a jemu odpovídající minimální řez
v následujícím ohodnoceném orientovaném grafu:
01 01
01
0101
01 01
8
7
10
7
12
13
8
18
28
16
5
9
18
17
7 6
20
17
8
Z
S
A B
C D
E F
13
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Příklad 3. Určete maximální tok a jemu odpovídající minimální řez
v následujícím ohodnoceném orientovaném grafu:
01 01
01
0101
01 01
8
7
10
7
12
13
8
18
28
16
5
9
18
17
7 6
20
17
8
Z
S
A B
C D
E F
13
Řešení. Min. řez. dán množinou {F, S}, jeho hodnota je 39. 2
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
1 Výsledky písemné práce
Skupina 1
Skupina 2
Skupina 3
Skupina 4
2 Domácí úlohy z minulého týdne
Příklad 2
Příklad 3
3 Floydův algoritmus
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Příklad 1. Řezem v síti (V , E, z, s, w) můžeme také rozumět
množinu hran C  S takovou, že v síti (V , E \ C, z, s, w)
neexistuje žádná cesta ze zdroje z do stoku (cíle, spotřebiče) s, ale
pokud z C odebereme libovolnou hranu e, tak už nová množina
tuto vlastnost mít nebude, tedy v (V , E \ C  e, z, s, w) existuje
cesta ze z do s. Určete všechny tyto řezy (a jejich hodnoty) v
následující síti:
4
5
6 2
1
2
10
Z
S
4
2
2
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Řešení. Označíme-li hrany dle obrázku
Z
S
a
b
c d e
f
gh
i
j
pak jsou řezy následující: {f,i},{f,h,j,a},{f,j,c,a,d,e},{f,j,c,a,d,f},
{b,j,c},{b,j,h},{b,i}, jejich hodnoty jsou pak 12, 9, 20, 18, 15, 10,
15. 2
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Příklad 2. Najděte maximální tok v síti z příkladu 1 pomocí
Fordova-Fulkersonova algoritmu.
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Příklad 2. Najděte maximální tok v síti z příkladu 1 pomocí
Fordova-Fulkersonova algoritmu.
Řešení. Hodnota je 9, (f (a) = 2, f (b) = 4, f (c) = 1, f (h) =
1, f (j) = 4, f (f ) = 2, f (i) = 7, jinak nuly), není určen jednoznačně.
2
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Příklad 3. Rozhodněte zda platí (při definici řezu z příkladu 1):
a) Minimální řez v libovolné síti je právě jeden.
b) Počet řezů v síti je roven počtu cest ze zdroje do stoku.
c) Řezů je v síti alespoň tolik, co různých cest ze zdroje do stoku.
d) Řezů v síti může být jak více tak méně než cest ze zdroje do
stoku.
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Příklad 3. Rozhodněte zda platí (při definici řezu z příkladu 1):
a) Minimální řez v libovolné síti je právě jeden.
b) Počet řezů v síti je roven počtu cest ze zdroje do stoku.
c) Řezů je v síti alespoň tolik, co různých cest ze zdroje do stoku.
d) Řezů v síti může být jak více tak méně než cest ze zdroje do
stoku.
Řešení.
a) Ne. (třeba zdroj a stok jsou propojeny právě dvěma
neprotínajícími se cestami se stejnou propustností)
b) Ne. (viz graf z př. 1)
c) Ano. (důkaz např. indukcí vzhledem k počtu vrcholů)
d) Ne.
2
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
1 Výsledky písemné práce
Skupina 1
Skupina 2
Skupina 3
Skupina 4
2 Domácí úlohy z minulého týdne
Příklad 2
Příklad 3
3 Floydův algoritmus
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Floydův algoritmus na výpočet nejkratších cest
Zlepšení algoritmu počítající matici vzdáleností v grafu.
Idea: počítáme postupně matice U0, U1,. . . , Uk, které udávají
nejkratší vzdálenosti vrcholů po cestách, které prochází pouze
vrcholy 1, . . . , k, tedy uk(i, j) je délka nekratší cesty mezi vrcholy i
a j, která jde pouze přes vrcholy 1, . . . , k.
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Nechť D je matice délek hran v grafu o n vrcholech. Následující
algoritmus z ní spočítá matici vzdáleností.
Algoritmus:
for k to n do
for i to n do
for j to n do
if D(i, j) > D(i, k) + D(k, j) then
D(i, j) := D(i, k) + D(k, j);
od;
od;
od;