Grafy - připomenutí
► Jaké reprezentace grafů v počítači znáte?
Grafy - pripomenutí
► Jaké reprezentace grafů v počítači znáte?
► Jaké způsoby procházení grafu znáte?
► Jaké jsou jejich vlastnosti?
► Jaké mají využití (kromě prostého průchodu grafem)?
Grafy - použití
Máme tři nádoby velikostí 10 I, 7 I a 4 I. Sed m i litrová a čtyřlitrová nádoba jsou na počátku plné a desetilitrová nádoba je prázdná. Chceme přelíváním docílit toho, aby v sedmilitrové nebo ve čtyřlitrové nádobě byly presne 2 litry. Nemáme však jiný způsob měření objemu a nechceme nic odhadovat, přelívání z nádoby A do nádoby B tedy může probíhat jen tak, že buď se vyprázdní nádoba A nebo se zcela naplní nádoba B. Je rovněž zakázáno vodou plýtvat a vylívat ji mimo nádoby.
► Převeďte toto zadání na grafový problém.
► Nalezněte algoritmus vhodný k vyřešení tohoto problému.
Grafy - hledání modrých cyklů
Mějme orientovaný graf G = (V, E) s množinou modrých vrcholů M C V. Cyklus v grafu nazveme úplně modrý, je-li každý jeho vrchol modrý.
► Navrhněte algoritmus, který najde a vypíše alespoň jeden úplně modrý cyklus nebo odpoví, že takový cyklus v grafu neexistuje.
rafy - hledání modrých cyklů
Mějme orientovaný graf G = (\/, E) s množinou modrých vrcholů M C V. Cyklus v grafu nazveme úplně modrý, je-li každý jeho vrchol modrý.
► Navrhněte algoritmus, který najde a vypíše alespoň jeden úplně modrý cyklus nebo odpoví, že takový cyklus v grafu neexistuje.
► Varianta: Máme rovněž zadán počáteční vrchol s. Chceme úplně modrý vrchol dosažitelný z s.
Grafy - hledání modrých cyklů
Mějme orientovaný graf G = (\/, E) s množinou modrých vrcholů M C V. Cyklus v grafu nazveme úplně modrý, je-li každý jeho vrchol modrý.
► Navrhněte algoritmus, který najde a vypíše alespoň jeden úplně modrý cyklus nebo odpoví, že takový cyklus v grafu neexistuje.
► Varianta: Máme rovněž zadán počáteční vrchol s. Chceme úplně modrý vrchol dosažitelný z s.
Cyklus v grafu nazveme trochu modrý, pokud obsahuje alespoň jeden modrý vrchol.
► Navrhněte algoritmus, který najde a vypíše alespoň jeden trochu modrý cyklus nebo odpoví, že takový cyklus v grafu neexistuje.
Grafy - jednosměrky
V nejmenovaném městě byly nařízením radnice změněny všechny ulice na jednosměrné. Opozice proti tomuto rozhodnutí protestuje a požaduje po starostovi důkaz toho, že stále existuje způsob, jak se legálně z libovolné křižovatky dostat na libovolnou jinou křižovatku. Volby však budou brzo a času je málo (akorát tak na spuštění algoritmu s lineární složitostí). Formulujte uvedené zadání jako grafový problém a ukažte, že je tento problém skutečně řešitelný v lineárním čase.