Grafy: vrcholy a hrany

Žáci modelují situaci grafem s vrcholy a hranami, převedou stejná data mezi dvěma zápisy, opraví chybu v modelu a porovnají, který je pro problém užitečnější.

Průvodce tématem Grafy: vrcholy a hrany v předmětu Informatika pro I. ročník: co mají žáci zvládnout, na co navázat a kde nejčastěji chybují. K tomu příprava na hodinu, pracovní list nebo písemka, které ScioBot připraví na jedno kliknutí přesně pro tento ročník.

Připravit hodinu Všechny formáty

Klikněte a tvořte

Získejte přípravu zdarma

Vyberte formát. Jedním kliknutím otevřete tvorbu na téma Grafy: vrcholy a hrany (I. ročník) — ScioBot ho připraví za vás.

Připravit hodinu

Další formáty na jedno kliknutí

Téma i ročník jsou už vyplněné. Nic nepíšete — rovnou tvoříte.

Žáci v I. ročníku gymnázia podle G-INF-01-007 modelují situaci grafem: vrcholy zastupují entity (místa, lidi, počítače), hrany vztahy mezi nimi. Rozlišují neorientovaný a orientovaný graf a umí k hraně přiřadit ohodnocení (vzdálenost, čas, kapacita), aniž by z modelu dělali mapu reality. Graf je schéma — zjednodušení, které ponechá jen to, co je k otázce potřeba.

Podle G-INF-01-004 stejná data přepisují mezi dvěma zápisy (obrázek grafu a seznam sousedů nebo seznam hran), hledají chybu v modelu (chybějící vrchol, špatný směr hrany, duplicita) a opraví ji. Porovnají dva grafy téže situace a zdůvodní, který je pro daný problém užitečnější (kratší cesta, dostupnost, závislost).

Cílem není teorie grafů do šířky, ale jistota v pojmech vrchol–hrana–orientace–ohodnocení a v tom, že dva zápisy stejných dat musí odpovídat a že model se hodnotí podle užitečnosti pro konkrétní otázku.

Předpoklady

Klíčové pojmy

Vrchol
Prvek grafu, který zastupuje jednu entitu situace (zastávka, žák, soubor, úloha). V modelu má jméno; jeho poloha na papíře na význam nemá.
Hrana
Spojení dvou vrcholů, které vyjadřuje vztah (sousedství, závislost, přenos). Bez hrany vztah v modelu neexistuje, i kdyby v realitě byl.
Neorientovaný a orientovaný graf
U neorientované hrany platí vztah oběma směry; u orientované má hrana šipku a směr je součástí dat. Zaměnit směr znamená jiný model.
Ohodnocený graf
K hraně (někdy k vrcholu) je přiřazeno číslo nebo údaj — délka, čas, cena. Ohodnocení se čte jen tehdy, když ho otázka potřebuje.
Dva zápisy týchž dat
Stejný graf lze zapsat kresbou a seznamem hran nebo seznamem sousedů. Převod musí zachovat vrcholy, hrany, směry i ohodnocení.
Chyba v modelu
Chybějící nebo přebývající vrchol, špatný směr, zdvojená hrana, špatné ohodnocení. Oprava spočívá v úpravě modelu, ne v „překreslení hezčeji“.
Užitečnost modelu
Dva správné grafy téže situace se liší tím, co vynechají. Lepší je ten, který kratčeji a bez šumu odpovídá na položenou otázku (G-INF-01-004).

Časté miskoncepce

  • Častá chyba

    Žák kreslí „mapu“: vrcholy posouvá podle skutečné polohy a tvrdí, že delší čára na papíře znamená delší cestu.

    Jak na to

    Dejte stejný seznam hran a nechte nakreslit dvakrát — jednou „hezky“, jednou jinak uspořádané. Srovnejte seznamy sousedů: musí být stejné. Délka je jen v ohodnocení hrany, ne v čáře.

  • Častá chyba

    U orientovaného grafu žák kreslí čáru bez šipky nebo šipku oběma směry a říká, že „je to jedno, stejně se tam dá jet“.

    Jak na to

    Vezměte konkrétní dvojici (jednosměrka, závislost úloh A→B). Nechte zapsat seznam orientovaných hran a ukázat, která otázka („lze z A do B?“) po smazání šipky změní odpověď.

  • Častá chyba

    Žák do seznamu sousedů vypíše jen „kdo s kým sousedí“ bez rozlišení směru, takže z A je B i z B je A, i když v obrázku byla šipka jen jedním směrem.

    Jak na to

    Vedle obrázku vyplňte tabulku „z / do“. U jedné šipky A→B musí být B u A, ale A u B ne. Nechte žáka opravit vlastní seznam podle šipek, ne podle dojmu.

  • Častá chyba

    Žák prohlásí hustší graf za „lepší model“, protože má víc čar, i když otázka je jen o dosažitelnosti dvou vrcholů.

    Jak na to

    Položte tutéž otázku ke dvěma modelům (úplný a redukovaný). Nechte zapsat, který kratčeji dá odpověď a které hrany otázka vůbec nepoužila. Užitečnost = shoda s otázkou, ne počet hran.

Jak učit

2–3 hodiny

  1. Evokace: krátká situace (spoje mezi městy nebo závislosti úkolů) — žáci sami navrhnou, co zakroužkují a co spojí, aniž by slyšeli slovo graf.
  2. Jádro: zavedení vrchol–hrana–orientace–ohodnocení; převod kresba ↔ seznam hran/sousedů; společná oprava záměrné chyby ve směru nebo v chybějícím vrcholu.
  3. Reflexe: dva grafy téže situace — žáci napíší jednou větou, který je k dané otázce užitečnější a kterou hranu by smazali.

Nápady na aktivity

  • Dvojice dostane text (linky MHD / závislosti odevzdání úkolů). Jeden kreslí graf, druhý píše seznam hran; vymění si zápisy a hledají neshodu (chybějící směr, zdvojená hrana).
  • Skupiny dostanou stejná data a dvě otázky (nejkratší ohodnocená cesta vs. pouhá dostupnost). Každá skupina upraví model vynecháním zbytečných hran a obhájí, proč je jejich graf k otázce užitečnější.

Hodnocení

Žák z textu sestrojí graf s popsanými vrcholy a hranami, totéž zapíše seznamem sousedů nebo hran a opraví zadanou chybu (špatný směr nebo chybějící vrchol).

Ke dvěma modelům téže situace žák uvede, který je k dané otázce užitečnější, a jednou větou zdůvodní vynechání konkrétní hrany (G-INF-01-004, G-INF-01-007).

Související témata

Zdroje

Co pro vás ScioBot připraví k tématu Grafy: vrcholy a hrany

Interaktivní aktivity, které žáci spustí na tabletu či tabuli, tisknutelné kartičky a hry pro celou třídu – každý formát na téma Grafy: vrcholy a hrany jedním klikem.

Základní materiály

Interaktivní aktivity 14

K tisku a rozstříhání 8

Hry pro celou třídu 4

Očekávané výstupy

  • G-INF-01-004 žák převede data z jednoho modelu do jiného; najde chyby daného modelu a odstraní je; porovná různé modely s ohledem na užitečnost pro řešení daného problému
  • G-INF-01-007 modelování – model jako zjednodušení reality, schéma, diagram, pojmová a myšlenková mapa; graf, vrcholy, hrany, orientovaný graf, ohodnocený graf, kritická cesta

Učíte Grafy: vrcholy a hrany trochu jinak?

Popište ScioBotu vlastními slovy, co s žáky chcete zvládnout a kolik máte času. Materiál přizpůsobí vašemu ŠVP, třídě i žákům se speciálními vzdělávacími potřebami.

Napsat ScioBotu

Související témata