Vnitro_4_12_2006

rá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
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ří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
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. 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,...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říklad1. 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. 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 šířkycsquotedblright, 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 šířkycsquotedblright, 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). 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
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ří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
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. a50