Vnitro_4_12_2006

Výsledky písemné práce Domácí úlohy z minulého týdne Floydův algoritmus
Příklad1. 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říklad1. 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. 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.
Kterou hranu grafu K6 objeví algoritmus „prohledávání do šířkycsquotedblright,
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říklad2. Označme vrcholy v grafu K6 postupně čísly 1, 2,...6.
Kterou hranu grafu K6 objeví algoritmus „prohledávání do šířkycsquotedblright,
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).
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
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ří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
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. 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 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říklad1. 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. 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 5 a hrany ze zpra