Grafy a modelování

Grafy, grafy a grafy

Hned na začátku si vyjasněme, že grafy v informatice se liší od grafů funkcí v matematice i od grafů v tabulkových procesorech. Budeš tedy muset rozlišovat různé významy slova graf podle kontextu stejně, jako to děláš s ostatními souzvučnými slovy.

Proč nezvolit jiný pojem?

Nabízí se otázka, proč pracujeme s pojmem, který už studenti znají v jiném významu. Mohli bychom mluvit např. o sítích či schématech. Ovšem v okamžiku, kdy by studenti přišli do kontaktu se světem mimo školu, byli by opět zmatení a s ostatními lidmi by si nerozuměli. Co víc, měli by potíže i se snahou použít jiné studijní materiály, které se samozřejmě drží standardní terminologie. Z těchto důvodů jsme se rozhodli vystavit studenty dalšímu významu pojmu graf a umožnit jim samostatně ty významy rozlišovat.

Tím spíš je nutno sledovat, jestli právě zmatený student nepracuje s jiným významem grafu, občas se to stává.

Co má společného Kréta, vyhledávání na GoogleSpolečnost Google podpořila vznik této učebnice - děkujeme!, evoluce, hledání prvočinitelů, městská hromadná doprava, větné rozbory či origami? Všechny nějak souvisí s grafy.

Souvislosti

Pro úplnost:

• Z Kréty studenti znají labyrint, tedy bludiště, tedy graf.
• Relevanci stránky Google určije mimo jiné podle dalších stránek, které na ni odkazují, pracuje tedy s grafem odkazů mezi stránkami.
• Evoluční vývoj druhů pro přehlednost znázorňujeme pomocí stromů, tedy grafů.
• Jeden z postupů hledání prvočinitelů číslo postupně rozkládá na jednotlivé dělitele a ty dále dělí (dokud to jde). Abychom se v tom neztratili, zakreslujeme dílčí rozklady jako větvení stromu, na jehož listech potom najdeme prvočinitele.
• Plány městské hromadné dopravy jsou klasickým příkladem grafů.
• Při navrhování nového origami tvůrce nejprve hledá strukturu výsledného objektu, totiž jednotlivá větvení a jejich větvení — tedy strom.

Uvedený odstavec má nicméně podnítit zvědavost, není nutné hned tady prozradit, co je graf vlastně zač.

I když o nich zatím možná nemáš tušení, jsou grafy jednoduchým, užitečným a velmi mocným nástrojem pro řešení široké škály různých problémů. Právě proto se staly nedílnou součástí výbavy každého informatika. Uplatnění ale najdou skoro všude, kde záleží na vzájemných vztazích mezi nějakými objekty. Takže skoro všude.

Obsah

Doporučený průběh

Cílem této části učebnice je základní seznámení s grafy. Studenti by je měli umět rozpoznat v běžných situacích a usnadnit si tak např. odvozování jednoduchých závěrů o daném problému. Kromě toho samozřejmě grafy bohatě využijeme v dalších částech učebnice, zejména v části o stavových prostorech. V té se také budeme věnovat systematickému procházení grafů.

Na grafech studenty zároveň seznamujeme s modelováním. Modely k řešení problémů i školních úloh již samozřejmě dávno používají. Zpravidla si toho ovšem nejsou vědomi, stejně jako souvisejících úskalí.

Nejdřív studenti na připravených úlohách zjistí, že na intuitivní úrovni už s grafy pracují. Jejich existující znalosti následně strukturujeme. Abychom mohli zpracovávat velké grafy (a grafy v počítači), potřebujeme grafy zapsat pomocí posloupností znaků, nikoliv jako obrázky. To je tedy dalším krokem. Zároveň u toho opakujeme učivo o informaci.

S tímto základem je možné začít zkoumat nějaký konkrétní problém a odvodit např. obecný postup řešení. Nám se osvědčily eulerovské grafy (jednotažky), ale vybrat lze i jiné základní téma, např. stromy a jejich vlastnosti, kostry (a minimální kostry) atp.

Závěrečná kapitola o isomorfismu grafů je pro některé žáky zprvu obtížná, nakonec ale látku pochopí. Samotný isomorfismus grafů jako takový vlastně není tak zásadní (umožňuje to ale precizně popsat, v jakém smyslu v grafu „nezáleží na nakreslení“). Smyslem kapitoly je ukázat, že pojem „stejnosti“ může být složitější, než se na první pohled zdá, na čem závisí a že stojí za bližší prozkoumání. Rozeznávání v nějakém smyslu stejných, ekvivalentních či isomorfních struktur se v informatice objevuje v mnoha různých souvislostech.

Do grafů jsme zařadili i dvě doplňující kapitoly. Myšlenkové mapy jsou aplikací grafů a užitečným nástrojem, který by studenti měli znát (a pokud je znají, není problém kapitolu projít velmi rychle, nebo ji zcela přeskočit). Regulární grafy jsou příležitostí k systematickému zkoumání abstraktní struktury a hledání zákonitostí. Je to dobrá průprava, ale další kapitoly na tom přímo nezávisí.

Kapitoly

1. Úvod — metodické poznámky, plán hodiny
2. Zapisování grafů — metodické poznámky, plán hodiny
3. Jednotažky — metodické poznámky, plán hodiny
4. Projdi bludiště, zachráníš kozu (stavové prostory) — metodické poznámky, plán hodiny
5. Lesní požáry (simulace) — metodické poznámky, plán hodiny
6. Úlohy (textový dokument)

Hlavní otázky

1. Co je v informatice graf?
   1. Z čeho se grafy skládají?
   2. Jaké druhy grafů rozlišujeme?
   3. Které jsou základní a zajímavé vlastnosti grafů?
2. Co můžeme pomocí grafů reprezentovat?
3. Jaké můžeme s pomocí grafů řešit problémy?
4. Jak grafy kreslit, jak je zapisovat?

Další zdroje

• Úlohy s grafy od Lukáše Jirovského. Řadu dalších úloh s tímto zamřením najdeme v archivu Bobříka informatiky, ve všech kategoriích.

• Knihy
  • Jak to řešit,
  • Jak to vyřešit?,
  • Grafy a jejich aplikace,
  • Modelování a simulace komplexních systémů.
• Kurz Myšlení pomocí modelů od Michiganské univerzity.