4EK311 – Operační výzkum
Cvičení 8
Cvičení 8 – teorie grafů
Příklad 1 – optimální cesty v grafu
Nalezněte nejkratší cestu z uzlu 1 do uzlu 5 v následujícím grafu a vypočtěte její délku.
1
2
2
5
4
5
4
3
2
3
5
3
Příklad 2 – optimální cesty v grafu
Nalezněte nejkratší cestu z uzlu 1 do uzlu 10 v následujícím grafu a vypočtěte její délku.
5
2
2
3
5
4
3
1
3
4
10
1
6
2
3
7
2
6
5
8
7
1
3
3
8
7
9
9
Příklad 3 – optimální spojení míst
Nalezněte minimální kostru následujícího grafu a spočítejte její délku.
3
10
1
16
7
2
6
5
8
3
13
6
7
8
6
6
7
4
4
4EK311, Ing. Veronika Skočdopolová
1
4EK311 – Operační výzkum
Cvičení 8
Příklad 4 – optimální toky na síti
Nalezněte maximální tok z uzlu 1 do uzlu 8 na následující síti a spočítejte jeho objem.
6
2
7
2
5
5
8
3
3
1
6
12
8
2
4
9
4
7
11
10
4
7
Příklad 5 – optimální toky na síti
Nalezněte maximální tok z uzlu 1 do uzlu 6 na následující síti a spočítejte jeho objem.
10
1
11
2
5
7
4
5
4
11
18
6
5
12
9
3
Příklad 6 – řízení projektů – sestavení grafu
Sestavte grafy, které odpovídají následujícímu zadání předchůdců, a topologicky je očíslujte.
a)
činnost
předchůdci
A
-
B
-
C
A
D
A
E
B,C
F
B,C
činnost
předchůdci
A
-
B
A
C
A
D
B
E
B,C
F
D,E
činnost
předchůdci
A
-
B
A
C
A
D
E
B,C B
činnost
předchůdci
A
-
B
A
C
A
D
B
G
D,E
b)
c)
F
D
G
B,C
H
G
I
E,F,H
F
G
B,C B,C
H
F
I
F,G
J
H
d)
4EK311, Ing. Veronika Skočdopolová
E
D
J
H,I
2
Download

8.cvičení - Ing. Veronika Skočdopolová