Co se dá vyčíst z grafu
Parta kamarádů se rozhodla, že si vyjedou na výlet do ZOO.
Chtěli jet na kolech. Je v tom ale háček, každý bydlí v jiné obci. Martin je z Maršova, Lucka z Lažánek, David bydlí v Deblíně, Katka v Moravských Knínicích, Iva v Chudčicích, Hanka ve Hvozdci a Vašek ve Veverské Bítýšce. Tak jak to provedou?
Martin se do toho pustil. Nakreslil plánek všech míst, přidal ještě dvě křižovatky cest - Hálův mlýn pod Lažánkami a Podhájí u Chudčic.
"A teď se všichni podívejte a rozhodněte se, kudy pojedete. Můžeme se sejít v Bítýšce nebo u hradu Veveří."
"Tak, jak jsi to nakreslil, Katka, Iva a Hanka budou mít kratší cestu přímo na hrad. Možná i Martin přes Hvozdec. Ale je to opravdu tak?"
Martin nakreslil graf, ale chybí v něm údaje o vzdálenosti nebo o čase jízdy. Pokud propojíme místa odjezdu tak, aby nevznikl kruh, dostaneme kostru grafu. Koster grafu může být několik. Ale stále chybí údaje k délce cest.
Martin si vzal mapu a doplnil vzdálenosti mezi jednotlivými místy.
Vašek jede jen k hradu. Ani Lucka nemá na výběr - do Bítýšky a pak na hrad. Martin si může vybrat, jestli pojede údolím Bílého potoka nebo po silnici, ale cesta po silnici je o 2 km kratší. David má cestu přes Lažánky o 1 km kratší. Martin a David pojedou do Lažánek a odtud společně s Luckou. Hanka pojede přímo k hradu. Iva by mohla jet na Podhájí a potom k hradu nebo přes Bítýšku. Přes Bítýšku má trasu kratší. Katka má nejkratší cestu přímo do Brna k ZOO. Pokud chce jet k hradu, kratší cesta vede přes Podhájí. Ale z Pohájí k hradu vede cesta lesem, z kopce do kopce. Trasa je sice kratší, ale časově i fyzicky náročnější. Proto Katka pojede raději do Chudčic a odtud dál s Ivou.
Rozhodnuto a počítáme.
Hanka pojede přímo k hradu. Ostatní se sejdeme v Bítýšce a odtud pojedeme k hradu. Katka pojede do Chudčic a odtud s Ivou. David a Martin přijedou do Lažánek a pak s Luckou pojedou do Bítýšky.
K hradu má Hanka 4 km, Vašek 4 km, Iva 6 km, Katka 10 km, Lucka 8 km, Martin 11 km a David 15 km. A všichni ještě 10 km do Brna a pak zase zpět.
Tím, že do grafu doplnili potřebné údaje, získali ohodnocený graf. Každý si zvolil nejkratší cestu (buď vzdáleností nebo časovou náročností). To znamená, že společně vytvořili kostru grafu s minimální cestou při daných podmínkách.
Ohodnocený graf
Pokud hledáme třeba nejkratší cestu, nebo chceme spočítat časovou náročnost trasy, nepotřebujeme vědět, jak přesně daná silnice vede. Můžeme ji zjednodušit na úsečku. Vytvoříme tak graf. V grafu můžeme vybrat ze všech možností jen určitou část - kostru grafu. Kostra grafu nesmí obsahovat kruhovou cestu.
Hranu mezi dvěma vrcholy mohu ohodnotit jednak vzdáleností a jednak časem. Takto označený graf nazýváme ohodnocený graf. Cestu mezi jednotlivými uzly můžeme hledat podle různých podmínek. Pokud hledáme nejkratší cestu (vzdáleností nebo časově), vytvoříme minimální kostru grafu.
Cesta na kole je příjemná, ale když Lucka viděla, kolik kilometrů musí ujet, ještě procházka po ZOO a pak při zpáteční cestě na závěr ten kopec! Ani Iva a Katka si na cestu na kole netroufly. A tak se rozhodly, že raději pojedou autobusem. Martin tedy naplánoval cestu znova. Vzal jízdní řády a graf upravil.
Tahle cesta vyhovovala všem.
David nasedne na autobus v Deblíně, v Maršově se přidá Martin a Lucka
v Lažánkách. Společně dojedou do Veverské Bítýšky.
Katka pojede z Moravských Knínic,
v Chudčicích se k ní přidá Iva.
V Bítýšce počkají společně s Vaškem než přijede David, Martin a Lucka. Společně pak budou pokračovat dalším autobusem, Hanka přistoupí ve Hvozdci. Nejdéle na cestě bude Katka s Ivou, protože musí půl hodiny čekat na další spoj.
Zeleně je označená kostra grafu s minimální cestou.
Procvičování s Bobrem
Orientace ve schématu, v grafu
V těchto úlohách jsou předkládány modely, schémata, grafy, které zobrazují nějakou situaci, a žák se má V TOMTO MODELU VYZNAT, porozumět mu a zorientovat se, aby mohl úlohu vyřešit.
Copied from:Informatika s Bobříkem
Úkol
Nadpis a text mezi čarami zkopíruj do pracovního sešitu. Nezapomínej text upravit.
Do sešitu vypracuj úkoly z pracovního listu.