Vnitro_4_12_2006

cová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říklad2. 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 hloubkycsquotedblright, 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) a50
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Příklad3. 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říklad3. 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. a50
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Příklad1. 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říklad1. 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. a50
Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Příklad2. 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 hloubkycsquotedblright, 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říklad2. 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 hloubkycsquotedblright, 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). a50
Výsledky písemné p