Grafy

Kapitola věnující se grafům je poměrně obsáhlá a tak záleží, kolik času jste grafům ochotni věnovat. Pěkné úlohy se dají ukázat už na ohodnocených grafech. Pokud byste chtěli grafům věnovat více prostoru nebo je třeba i programovat, určitě proberte i orientované grafy, které na webu nepokrýváme.

V takovém případě je vhodné zavést preciznější značení hran, než je zde na webu, protože stávající notace začne být brzy matoucí.

Modelový příklad vyučovací hodiny

Ukázková hodina se omezí pouze na neohodnocené a ohodnocené neorientované grafy a cestu v grafu.

Cíl hodiny: Žák dovede popsat, co je to graf v informatice

• Úvod (5 minut)
  • otázka: Co je to graf?
  • ukázka grafů matematických funkcí a statistických grafů
• Grafy v informatice (25 minut)
  • motivace: šíře využití
  • vhodné je zopakovat pojem množiny
  • graf jako množina vrcholů a hran
  • zadání příkladů na překreslování grafů na základě těchto dvou množin a naopak
    • alespoň jeden příklad pro každý směr udělejte společně
  • aplikace grafu na příkladu bludiště nebo mapy
  • pojem cesty v grafu a nejkratší cesty v grafu
• Ohodnocené grafy (10)
  • motivace: např. různá prostupnost terénu na mapě mezi dvěma jinak stejně vzdálenými body (vrcholy)
  • ohodnocený graf – ohodnocení hran
  • pojem cesty a nejkratší cesty v ohodnoceném grafy
  • demonstrace rozdílné cesty na stejném příkladu jako u neohodnoceného grafu
• Závěr (5 minut)