Grafy - úvod
- Co a k čemu jsou modely.
- Co a k čemu jsou grafy (v informatice).
- Jakými pojmy o grafech mluvíme.
- Odhadovat co je v zadání podstatné pro řešení problému a co nikoliv.
- Modelovat pomocí grafů různé situace a řešit různé problémy.
Úloha: Batůžkáři
Z chaty na východní úpatí je to 2 km, na západní úpatí 3 km, na jižní úpatí ke stanici lanovky 5 km. Z východního úpatí na vrchol je to 4 km, ze západního 5 km. Na jižním se nastoupí na lanovku dlouhou 700 m a od lanovky se jde na vrchol už jen 500 m. Pěšky z jižního jsou to 2 km prudkým stoupáním. Z chaty se dá jít taky údolím k heliportu (4 km). Odtud se doletí buď 1 km od vrcholu, nebo přímo k dolní stanici lanovky.
Jak se batůžkáři Adam, Barbora a Marie dostanou z chaty na vrchol tak, aby při tom našlapali nejméně kilometrů?
Úloha: Strážný
V podzemním výrobním zařízení hlídá v noci strážný. Zařízení tvoří místnosti spojené různě dlouhými chodbami. Strážný musí pravidelně všechny chodby projít. Z vrátnice vede po jedné chodbě do šatny, skladu i kantýny. Mezi skladem a kantýnou je přímá chodba. Ze šatny vedou chodby do všech ostatních místností. Do dílny se lze dostat kromě šatny také ze skladu.
Najdete pro strážného takovou trasu, aby na ní prošel všechny chodby právě jednou? Lze to udělat tak, aby obchůzku skončil na stejném místě, kde ji začal? Existuje takových tras víc?
Úloha: Rodinka
Bořek má dvojčata, syna Adama a dceru Gábinu. Daniela má dceru Zuzanu a již odrostlejšího syna Jana. Hanka je ženou Bořka. Cecil je manželem Ilony. Hančin přísný otec je Cecil, Ilonin otec se jmenoval Karel. Karel byl zároveň dědečkem Daniely. Celá rodina žije v jednoduchém světě, kde se neopakují jména a nestřídají partneři.
V jakém vztahu jsou Adam a Daniela?
Odkaz (tvorba rodokmenu): https://www.familyecho.com/
Úloha: Sněhová kalamita
Sníh zaskočil silničáře a ti se snaží co nejdřív opět zprovoznit síť městských ulic. Město je tvořeno dvanácti čtvercovými bloky domů, vchody jsou vždy na rozích bloku. Bloky jsou uspořádány ve třech řadách a čtyřech sloupcích. Za zprovozněnou prohlásíme takovou síť, ve které se lze od každého vchodu (na rohu některého bloku) dostat ulicemi do libovolného jiného vchodu (třeba i oklikou).
Které úseky ulic (mezi dvěma křižovatkami) je třeba protáhnout, aby byla síť zprovozněna? Kolik úseků to je? Silničáři samozřejmě nechtějí protahovat nic navíc, naopak potřebují, aby byla síť co nejdříve zprovozněna. Existuje více řešení? Pokud ano, které z nich je nejlepší, proč?
(vždy musí protáhnout aspoň 19 úseků z 31)
Úloha: Výlet
Uspořádat výlet s kolektivem dospívajících není vždy jednoduché. Chtěli bychom co nejvyšší účast, jenže: Adéla nepojede, pokud pojede Hanka nebo Eva. Hanka a Eva rozhodně nepojedou zároveň. Naopak Běta a Cyril pojedou jedině spolu. Běta se ovšem nesnese s Danielou. Gábina se přátelí se všemi kromě Hanky.
Kolik nanejvýš lidí z popsané skupiny lze dostat na společný výlet? Kdo na výlet pojede?
Grafem v informatice rozumíme strukturu propojení dvojic nějakých objektů.
Také rozhodovací stromy jsou příkladem grafů:
Grafy nám umožňují získat lepší přehled než například slovní popis situace.
Umožňují nám abstrahovat od toho, co není důležité, a naopak se soustředit na to, co je pro naši úlohu či situaci určující.
Další výhodou je možnost systematického prozkoušení všech možností řešení — to by šlo podle slovního popisu dost těžko.
Grafy slouží k modelování situací, kde záleží na vzájemných vztazích.
Modely
Model je reprezentace skutečnosti, která vynechává, co není důležité, a naopak zachovává, co důležité je.
Smyslem modelu je zjednodušt jinak komplikovaný problém a soustředit se jen na to podstatné.
Model terénu je třeba mapa.
Množiny používáme k modelování skupin, přirozená čísla k modelování jejich velikosti a reálná čísla k modelování vzdáleností.
Z chemie a fyziky znáte různé modely atomu. Přitom už víte, že třeba ten model atomu není přesným popisem skutečného atomu, je jen popisem dostatečně přesným.
Jakékoliv naše představy o světě jsou vždy právě jen modely, protože o něm nedovedeme získat dostatek dostatečně přesných informací. Schopnost abstrakce (tedy poznat, co je důležité, a pominout to ostatní) je jedna z nejcennějších.
Vrcholy (uzly)
"Body" v grafu, to, co se spojuje hranami. Vrcholy představují objekty, jejichž vztahy modelujeme.
Hrany (spoje)
"Čáry" v grafu, kterými spojujeme vrcholy. Hrany představují vztahy mezi vrcholy. Hrana je definována vrcholy, které spojuje. Mluvíme proto o hraně A-B, Praha-Brno atp.
Graf
Graf je zachycením vztahů mezi objekty. Je tedy definován svými vrcholy (to jsou ty objekty) a hranami mezi těmito vrcholy (to jsou ty vztahy). Z předchozí věty mj. plyne, že je úplně jedno, jak je graf nakreslený, nebo jestli je vůbec nakreslený. Záleží jen na struktuře vztahů. Dva grafy obsahující stejné vrcholy a stejné hrany jsou stejné. Podobně platí 1 = 3⋅ ⅓ = 0,9.
Ohodnocení
Někdy potřebujeme k prvkům grafu přiřadit nějaké další informace. Silnice představované hranami mohou být různě dlouhé, hypertextové dokumenty představované vrcholy mají různé adresy apod. Potřebné hodnoty prostě připisujeme poblíž příslušné hrany či vrcholu. Ohodnocení je zpravidla číselné, ale ne nutně.
(Ne)orientovaný graf
Neorientovaný graf nerozlišuje směr hran. To jsou např. silnice mezi městy a přátelství na Facebooku. Orientovaný graf směr rozlišuje, na obrázku to většinou značíme šipkou. To jsou např. jednosměrky ve městě a skutečná náklonnost lidí. Má-li být v orientovaném grafu některý vztah symetrický, použijeme prostě hrany dvě, pro každý směr jednu.
(Ne)souvislý graf
Souvislý graf je "jeden kus", z každého vrcholu lze po hranách docestovat do libovolného jiného vrcholu. Naopak nesouvislý graf tuto vlastnost nesplňuje, takže obsahuje dvě nebo více tzv. komponent souvislosti: partiček přátel, co se spolu nebaví, fyzicky oddělených počítačových sítí apod.
Úplný graf
Graf, ve kterém je každý vrchol spojen hranou (tedy přímo) s každým jiným vrcholem.
Stupeň vrcholu
Počet hran s jedním koncem v daném vrcholu. Typická křižovatka má stupeň 4, křižovatka tvaru T má stupeň 3. Pokud je graf orientovaný, rozlišujeme vstupní a výstupní stupeň vrcholu.
Shrnutí:
- Model je zjednodušení reality, které vynechá její nepodstatné aspekty, čímž zpřehledňuje situaci. Příkladem modelu je planetární model atomu nebo plán městské hromadné dopravy.
- Každý model je ze své podstaty nepřesný. Pokud jsme ale model nezjednodušili příliš, není nepřesnost na škodu.
- Veškeré naše uvažování probíhá prostřednictvím modelů, na celou realitu ani nemáme mozkové kapacity.
- Graf je abstraktní struktura, která zachycuje vztahy mezi dvojicemi objektů.
- Mezi základní příklady patří modelování sítě silnic spojujících města či sociální sítě vzájemných přátelství. Vrcholy grafu budou představovat města (resp. lidi), hrany budou představovat silnice (resp. "přátelství").
- Grafy mohou usnadnit řešení problému tím, že jej přehledně znázorní.
- Další výhodou je možnost použití již známých postupů, není tak nutno řešit každý problém znova od začátku.
Cvičení
Cvičení 1
https://www.csfieldguide.org.nz/en/interactives/trainsylvania/
Najděte trasu z "Airport" do "Harbour Station".
Základní pojmy:
Vrchol: To, co propojujeme. Zpravidla objekty, jejichž vztahy potřebujeme přehledně zachytit.
Hrana: Propojení vrcholů. Hrany reprezentují nějaký vztah mezi tím, co reprezentují vrcholy.
Graf: Vrcholy propojené hranami. Grafy tedy využíváme tam, kde pracujeme se vztahy nějakých objektů. Tyto grafy se liší od grafů funkcí i od grafů v kancelářských aplikacích, nelze je zaměňovat.
Orientovaný graf: Hrany orientovaného grafu mají směr, obvykle znázorněný šipkou.
Ohodnocený graf: Graf s dalšími informacemi u vrcholů a nebo hran (názvy měst, délky cest …).
Proces modelování při řešení problémů:
Rozpoznat, co je pro řešení podstatné a co nikoliv (pojmy, vztahy, hodnoty…).
Zformulovat problémovou situaci v pojmech abstraktního modelu.
Vyřešit problém s pomocí modelu.
Interpretovat řešení.
Editor grafů
Cíl: Vyzkoušet si práci s editorem grafů
Otevřít nějaký editor grafů (např. online yEd, offline yEd, online LucidChart).
Samostatně nebo ve dvojicích se seznámit s jeho základními funkcemi a ovládáním.
Vytvořit v něm jeden z grafů k úlohám řešeným na papíře.
Vytvoří v něm graf reprezentující vlakovou síť (Trainsylvanya), tak aby se koleje nekřížily.
Ve vytvořených grafech znázorní nalezené řešení.
Na závěr žáci shrnou zkušenosti s použitím editoru: jaké přináší výhody, nevýhody, kdy se vyplatí použít, jaké další funkce by ocenili...