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.
Souvislý podgraf o alespoň třech vrcholech.
Podgraf o čtyřech vrcholech s hranami tak, aby mezi dvěma libovolnými vrcholy vedla cesta (podmínka souvislosti).
Podgraf s alespoň jednou hranou takový, že obsahuje 3 vrcholy, mezi kterými nevede žádná cesta.
Podgraf obsahuje hranu AF a mezi jeho vrcholy A, E, C nevede žádná cesta.
Podgraf, který obsahuje právě ty vrcholy, které leží na nejkratší cestě mezi C a F se všemi hranami.
Nejkratší cesta z F do C vede přes vrcholy A, B, E. Vynechali jsme tedy vrchol D se všemi hranami, které
do něj vedou.
3) Odpověz na otázky ke kostrám následujících grafů.
Je vyznačený podgraf minimální kostrou grafu?
Vyznačený podgraf není kostrou, protože mezi vrcholy A-B-E-C-F existuje cyklus, takže můžeme jednu
z hran odebrat bez toho, aniž by graf přestal být souvislý. Odebráním libovolné z těchto hran dostaneme kostru.
Má graf níže kostru? Pokud ano, vyznač ji. Pokud ne, dokáže přidáním nebo
odebráním hrany nebo vrcholu vytvořit graf, který má minimální kostru?
Původní graf neměl kostru, přidáním hrany mezi DE jsme vytvořili graf, který kostru má.
Je vyznačená kostra minimální kostrou?
Není. Kostra obsahující hranu DF místo hrany AB je menší (součet hodnot hran je nižší).
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.
Všechny nejkratší cesty v novém ohodnoceném grafu musí vést přes stejné vrcholy ve stejném pořadí.
Stačí všem hranám přiřadit stejnou cenu.
Ohodnoť následující graf tak, aby hrana EF byla nejdražší v celém grafu a nejkratší cesta
z D do F vedla přes A.
Je potřeba dát si pozor, aby hrany CE a EF nebyly příliš levné.
Ohodnoť následující graf tak, aby hrana BD byla nejdražší v celém grafu a tato cena odpovídala součtu
ohodnocení hran BE a CD. Nejkratší cesta z C do A musí vést přes vrchol F.
Hraně BD jsme určili cenu 66, hranám BE a CD jsme přiřadili polovinu.
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š.
Všechny hrany měly stejné ohodnocení, takže při délce cest rozhodovala struktura grafu. Zapomeneme
na ohodnocení a máme odpovídající neohodnocený graf.
Univerzálním řešením je přidat nové pomocné vrcholy, které odpovídajícím způsobem prodlouží dané cesty.
V tomto případě jsme si dovolili dvě hrany smazat a vrcholem jsme nafoukli pouze hranu mezi BF. Alternativně
jsme mohli zvolit stejný přístup jako v předchozím grafu.
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.
