MA2BP_CDM1 Cvičeni z diskrétní matematiky 1
3. Minimální kostra, nej kratší cesta
Lukáš Másilko
Středisko pro pomoc studentům se specifickými nároky
Masarykova univerzita
1. 11. 2017
Milkova - Cvičení 4.2, příklad 1
Rozhodněte, zda posloupnost (2, 2, 2, 3, 3, 4, 4) může být skóre souvislého grafu. Své rozhodnutí zdůvodněte.
Rada: Nejprve zjistěte, zda je posloupnost skóre grafu. Pak určete, zda graf může být souvislý.
1. 11. 2017       2 / 10
Milkova - Cvičení 4.2, příklad 3
V následujícím grafu určete počet koster.
Taha - Example 6.1-1
Společnost MidWest TV plánuje nabídnout svou kabelovou televizi pěti nově budovaným sídlištím. Vrchol 1 reprezentuje hlavní stanici kabelové televize, vrcholy 2-6 pak jednotlivá sídliště. Návěští hrany mezi dvěma vrcholy představuje skutečnou vzdálenost (v mílích) mezi nimi. Chybí-li hrana mezi dvěma vrcholy, znamená to, že vybudovat kabelové spojení mezi nimi je příliš drahé nebo technicky nemožné.
Cílem společnosti je nalézt spojení mezi všemi prvky kabelové sítě tak, aby bylo spotřebováno co nejméně kabelu a zaručeno, že všechna sídliště budou přímo či nepřímo připojena na hlavní stanici kabelové televize.
Mapu včetně vzdáleností mezi jednotlivými prvky kabelové sítě najdete na následujícím slajdu.
1. 11. 2017       4 / 10
Taha - Example 6.1-1 (pokračování)
Ukol k samostatnému řešení: Milkova - Příklad 5.1
Pomocí Kruskalova algoritmu naleznete minimální kostru grafu.
22 30     35 24 13
Taha - Problém 6-3
Obrázek na dalším slajdu znázorňuje vzdálenost (v mílích) mezi devíti ložisky zemního plynu a pobřežním stanovištěm pro vývoz tohoto paliva. Ložisko 1 je nejblíže pobřežnímu stanovišti. Je vybaveno silným čerpadlem a velkokapacitními nádržemi, ve kterých je možné skladovat výsledek těžby ze všech devíti ložisek.
Nalezněte nejkratší možné vedení plynovodu mezi ložiskem 1 a ostatními ložisky. Použijte Dijkstrův algoritmus.
1. 11. 2017       7 / 10
Taha - Problem 6-3 (pokračovaní)
1. 11. 2017       8 / 10
/ _
Ukol k samostatnému řešení: Taha - Problém 6-7
Na následujícím obrázku je znázorněna vzdálenost (v mílích) mezi osmi různými městy. Najděte nej kratší cestu mezi městem 1 a 8. Použijte Dijkstrův algoritmus.
1. 11. 2017       9 / 10
Použité zdroje
■ TAH A, Hamdy A. Operations Research. An Introduction. 4th edition. New York: Macmillan Publishing Company, 1989. ISBN 0-02-946750-0.
■ MILKOVA, Eva. Teorie grafů a grafové algoritmy. 1. vyd. Hradec Králové: Nakladatelství Gaudeamus, 2013. ISBN 978-80-7435-267-6.
1. 11. 2017       10 / 10