Pokud jsi ještě nečetl kapitolu Grafy, teď je vhodný čas, jinak
budou cvičení níže zbytečně těžká.
Většina příkladů v této kapitole obsahuje i řešení (zobrazí se ti po kliknutí).
Více než v jiných kapitolách a cvičeních i zde platí, že prezentované správné
výsledky nemusí být jediné správné. Pokud vymyslíš jiné (správné) řešení, tím
lépe pro tebe.
Základní pojmy: cesta, podgraf, souvislost, kostra
1) Spočítej v následujících grafech délku všech nejkratších cest mezi vrcholy.
A
B
C
D
E
F
A
0
3
2
3
2
1
B
3
0
2
2
1
2
C
2
2
0
2
1
1
D
3
2
2
0
1
2
E
2
1
1
1
0
1
F
1
2
1
2
1
0
A
B
C
D
E
F
A
0
6
6
9
5
2
B
6
0
6
5
1
4
C
6
2
0
5
1
4
D
9
5
5
0
4
7
E
5
1
1
4
0
3
F
2
4
4
7
3
0
A
B
C
D
E
F
A
0
3
3
3
7
1
B
3
0
5
1
9
3
C
3
5
0
6
4
4
D
3
1
6
0
10
2
E
7
9
4
10
0
8
F
1
4
4
2
8
0
2) Vyber v následujích grafech podgraf, který splňuje dané podmínky.
3) Odpověz na otázky ke kostrám následujících grafů.
Neohodnocené a ohodnocené grafy
1) Převeď následující neohodnocené grafy na ohodnocené tak, aby podmínky u každého
grafu byly zachovány.
2) Zatím jsme převáděli grafy z neohodnocených na ohodnocené. Převeď následující
ohodnocené grafy na neohodnocené tak, aby délka nejkratších cest zůstala zachována
(např. pokud je cesta mezi vrcholy X a Y dvakrát tak dlouhá jako cesta mezi vrcholy
V a W, pak v neohodnoceném grafu musí být tento vztah zachován).
Nápověda: Možná ti pomůže, když do nových (neohodnocených) grafů přidáš nějaké vrcholy nebo hrany, případně když nějaké odebereš.
Vyhledej si
1) S pomocí online map vytvoř graf v okolí školy nebo domova s vyznačenou
cestou na zastávku městské hromadné dopravy nebo obchodu.