Bakalářská práce LUCIE FRÖMMELOVÁ Brno 2024 PEDAGOGICKÁ FAKULTA Teorie grafů a její využití Vedoucí práce: RNDr. Břetislav Fajmon, Ph.D. Katedra matematiky Matematika se zaměřením na vzdělávání TEORIE GRAFŮ A JEJÍ VYUŽITÍ 2 Bibliografický záznam Autor: Lucie Frömmelová Pedagogická fakulta, Masarykova univerzita Katedra matematiky Název práce: Teorie grafů a její využití Studijní program: PdF B-MA3S Matematika se zaměřením na vzdělávání Studijní obor: PdF BMA3Shp Matematika se zaměřením na vzdělávání PdF BVZ3Svp Výchova ke zdraví se zaměřením na vzdělávání Vedoucí práce: RNDr. Břetislav Fajmon, Ph.D. Rok: 2024 Počet stran: 90 Klíčová slova: teorie grafů, hrana, vrchol, sousední vrchol, hamiltonovský graf, obarvení vrcholů Bibliographic record Author: Lucie Frömmelová Faculty of Education, Masaryk University Department of Mathematics Title of Thesis: Graph theory and applications Degree Programme: PdF B-MA3S Mathematics for Education Field of Study: PdF BMA3Shp Mathematics for Education PdF BVZ3Svp Health Education Supervisor: RNDr. Břetislav Fajmon, Ph.D. Year: 2024 Number of Pages: 90 Keywords: graph theory, edge, vertex, adjacent vertex, hamiltonian graph, vertex coloring TEORIE GRAFŮ A JEJÍ VYUŽITÍ 3 Anotace Bakalářská práce se zaměřuje na teorii grafů, konkrétně jejím využitím na druhém stupni základní školy. Cílem práce je připravit a zrealizovat výuku včetně jejího zhodnocení. Teoretická část je věnována definicím základních pojmů teorie grafů a ilustračním příkladům. V empirické části je navržena výuka s příklady pro žáky a jejich řešením, poté následuje zhodnocení provedení vyučování. Vzhledem ke zpětné vazbě z pohledu žáků a mého jsou v závěru práce vloženy komentáře pro posilnění realizace výuky. Abstract The bachelor thesis focuses on graph theory, particularly its use in lower secondary school. The thesis aims to prepare and carry out a lesson, including its evaluation. The theoretical part is dedicated to definitions of basic terms from graph theory and illustrative examples. In the empirical part, a lesson with examples for students and their solutions is devised, followed by an evaluation of the implementation of the lesson. Due to the feedback from the students and my perspective, comments are inserted at the end of the thesis to improve the implementation of the lesson. TEORIE GRAFŮ A JEJÍ VYUŽITÍ 5 Poděkování Ráda bych poděkovala panu RNDr. Břetislavovi Fajmonovi, Ph.D. za odborné vedení, pomoc a cenné rady při zpracování mé bakalářské práce. Též bych chtěla poděkovat paní Mgr. Jaroslavě Tesařové za příjemnou spolupráci při realizaci empirické části práce. Čestné prohlášení Prohlašuji, že jsem bakalářskou práci vypracovala samostatně, s využitím pouze citovaných pramenů, dalších informací a zdrojů v souladu s Disciplinárním řádem pro studenty Pedagogické fakulty Masarykovy univerzity a se zákonem č. 121/2000 Sb., o právu autorském, o právech souvisejících s právem autorským a o změně některých zákonů (autorský zákon), ve znění pozdějších předpisů. V Brně 16. dubna 2024 ....................................... Lucie Frömmelová OBSAH 7 Obsah Seznam obrázků 9 Seznam tabulek 11 Úvod 12 1 Teoretická část 13 1.1 Co je to graf......................................................................................................................... 13 1.2 Stupeň vrcholu a izomorfismus grafů ...................................................................... 16 1.3 Grafová souvislost, komponenty grafu .................................................................... 17 1.4 Hamiltonovský graf ......................................................................................................... 21 1.5 Stromy a kostry................................................................................................................. 22 1.6 Rovinný graf ....................................................................................................................... 28 1.7 Obarvení vrcholů grafu.................................................................................................. 30 2 Empirická část 35 2.1 Popis výzkumu .................................................................................................................. 35 2.2 První výukový blok.......................................................................................................... 35 2.2.1 Příprava na výuku.................................................................................................. 35 2.2.2 Sebereflexe................................................................................................................ 46 2.2.3 Analýza dotazníku.................................................................................................. 48 2.3 Druhý výukový blok........................................................................................................ 51 2.3.1 Příprava na výuku.................................................................................................. 51 2.3.2 Sebereflexe................................................................................................................ 65 2.3.3 Analýza dotazníku.................................................................................................. 67 Závěr 71 Použité zdroje 73 Příloha A: Pracovní list – první výukový blok 75 Příloha B: Pracovní list – druhý výukový blok 79 Příloha C: Vzorek sesbíraných dotazníků 85 SEZNAM OBRÁZKŮŮ 9 Seznam obrázků Obr. 1 Grafická reprezentace diskrétního neorientovaného grafu......................................13 Obr. 2 Grafické znázornění hran .......................................................................................................14 Obr. 3 Násobná hrana............................................................................................................................14 Obr. 4 Smyčka...........................................................................................................................................14 Obr. 5 Kaliningrad...................................................................................................................................15 Obr. 6 Naznačený začátek pokusu procházení ...........................................................................15 Obr. 7 Graf G1 ............................................................................................................................................16 Obr. 8 Graf G2 ............................................................................................................................................16 Obr. 9 Izomorfismus f............................................................................................................................16 Obr. 10 Graf H1 .........................................................................................................................................17 Obr. 11 Graf H2 .........................................................................................................................................17 Obr. 12 Izomorfismus l..........................................................................................................................17 Obr. 13 Ukázka řešení, kdy počet hran je roven 4......................................................................19 Obr. 14 Graf K5..........................................................................................................................................19 Obr. 15 Grafické znázornění nesouvislého grafu........................................................................19 Obr. 16 Grafické znázornění komponenty.....................................................................................20 Obr. 17 Řešení 7. příkladu se dvěma komponentami ...............................................................20 Obr. 18 Grafické znázornění hamiltonovské hádanky..............................................................21 Obr. 19 Ukázka hamiltonovské cesty ..............................................................................................22 Obr. 20 Ukázka stromu .........................................................................................................................22 Obr. 21 Grafické řešení 8. příkladu ..................................................................................................23 Obr. 22 Grafické řešení 9. příkladu a) .............................................................................................24 Obr. 23 Grafické řešení 9. příkladu b).............................................................................................24 Obr. 24 Zadání 10. příkladu.................................................................................................................25 Obr. 25 Řešení 10. příkladu ................................................................................................................25 Obr. 26 Zadání 11. příkladu.................................................................................................................26 Obr. 27 Řešení 11. příkladu.................................................................................................................26 Obr. 28 Nejkratší hamiltonovská kružnice....................................................................................27 Obr. 29 Důkaz protipříkladem...........................................................................................................28 Obr. 30 Zadání 12. příkladu.................................................................................................................28 Obr. 31 Řešení 12. příkladu.................................................................................................................29 Obr. 32 Úloha o 3 domech a 3 studních..........................................................................................29 Obr. 33 Řešení úlohy zvané narozeninová oslava......................................................................31 Obr. 34 Problém politické mapy – zadání......................................................................................32 Obr. 35 Problém politické mapy – řešení.......................................................................................32 Obr. 36 Důkaz Brooksovy věty...........................................................................................................33 Obr. 37 Řešení 16. příkladu Režiséři ...............................................................................................34 Obr. 38 Rovinné zobrazení grafu z 16. příkladu..........................................................................34 Obr. 39 Nákres na tabuli.......................................................................................................................37 Obr. 40 Zadání mapa A..........................................................................................................................37 Obr. 41 Vybarvení mapa A...................................................................................................................38 Obr. 42 Zadání – sousední vrcholy ...................................................................................................38 Obr. 43 Řešení mapy A ..........................................................................................................................39 Obr. 44 Zadání mapa ČR .......................................................................................................................40 SEZNAM OBRÁZKŮ 10 Obr. 45 Vybarvení mapa ČR................................................................................................................40 Obr. 46 Řešení mapa ČR .......................................................................................................................41 Obr. 47 Graf seznamovací hra ............................................................................................................42 Obr. 48 Graf harmonogram prohlídek............................................................................................43 Obr. 49 Graf ZOO ....................................................................................................................................44 Obr. 50 Graf rezervační problém ......................................................................................................45 Obr. 51 Hodnotící škála dotazník......................................................................................................45 Obr. 52 Střední Evropa .........................................................................................................................45 Obr. 53 Zadání úlohy – cesta v grafu................................................................................................52 Obr. 54 Řešení úlohy – cesta v grafu a)...........................................................................................53 Obr. 55 Řešení úlohy – cesta v grafu b) ..........................................................................................53 Obr. 56 Řešení úlohy – cesta v grafu c)...........................................................................................53 Obr. 57 Řešení úlohy – cesta v grafu d) ..........................................................................................53 Obr. 58 B – Plán tábora .........................................................................................................................54 Obr. 59 Graf tábora.................................................................................................................................55 Obr. 60 Tábor – hamiltonovská kružnice a) .................................................................................55 Obr. 61 Tábor – hamiltonovská kružnice b).................................................................................55 Obr. 62 Tábor– hamiltonovská kružnice c)..................................................................................55 Obr. 63 Tábor – hamiltonovská kružnice d).................................................................................55 Obr. 64 Tábor – hamiltonovská kružnice e) .................................................................................55 Obr. 65 Mapa Velkých Němčic............................................................................................................56 Obr. 66 Řešení – mapa Velkých Němčic .........................................................................................57 Obr. 67 Graf stezek .................................................................................................................................58 Obr. 68 Řešení – graf turistická trasa a).........................................................................................58 Obr. 69 Řešení – graf turistická trasa b).........................................................................................58 Obr. 70 Řešení – graf turistická trasa c).........................................................................................59 Obr. 71 Řešení – graf turistická trasa d) ........................................................................................59 Obr. 72 Oceněný graf – stezky............................................................................................................60 Obr. 73 Mapové značky.........................................................................................................................61 Obr. 74 Zadání domečku ......................................................................................................................61 Obr. 75 Řešení domečku.......................................................................................................................62 Obr. 76 Zadání malé bludiště..............................................................................................................62 Obr. 77 Graf malého bludiště .............................................................................................................63 Obr. 78 Graf malého bludiště..............................................................................................................63 Obr. 79 Zadání velké bludiště.............................................................................................................63 Obr. 80 Graf velkého bludiště.............................................................................................................64 Obr. 81 Graf – cesta velkým bludištěm...........................................................................................64 Obr. 82 Škála hodnot dotazník...........................................................................................................64 Obr. 83 Graf zpětná vazba a)...............................................................................................................65 Obr. 84 Graf zpětná vazba b) ..............................................................................................................65 SEZNAM TABULEKŮ 11 Seznam tabulek Tabulka 1 Trasy a jejich délka............................................................................................................60 Seznam grafů Graf 1 Poutavost první výuky.............................................................................................................48 Graf 2 Obtížnost první výuky..............................................................................................................48 Graf 3 Tvoření a popis grafu ...............................................................................................................49 Graf 4 Vybarvení politické mapy.......................................................................................................50 Graf 5 Nejlepší úloha bloku .................................................................................................................50 Graf 6 Poutavost druhé výuky............................................................................................................67 Graf 7 Obtížnost druhé výuky ............................................................................................................67 Graf 8 Specifika hamiltonovské kružnice.......................................................................................68 Graf 9 Vyznačení hamiltonovské kružnice....................................................................................69 Graf 10 Vlastní graf s hamiltonovskou kružnicí..........................................................................69 Graf 11 Nejnáročnější úloha bloku...................................................................................................70 TEORETICKÁ ČÁST 12 Úvod Bakalářská práce se zabývá matematickou disciplínou zvanou teorie grafů. Cílem práce je připravit a realizovat výuku vybraných kapitol z teorie grafů pro žáky na základní škole. Následně rozebrat zpětnou vazbu od žáků a též sepsat vlastní hodnocení. Na závěr dle získaných dat uvést doporučení pro případnou realizaci. Práce je rozdělena na dvě části, teoretickou a empirickou. V první části jsou na základě odborné literatury sepsány základní pojmy a jejich vymezení. Teoretická část je rozdělena do sedmi kratších kapitol. Nejprve je zpracováno, jak na graf nahlížíme, poté následují témata: stupeň vrcholu a izomorfismus grafů, grafová souvislost, komponenty grafu, hamiltonovský graf, stromy a kostry, rovinný graf a na závěr obarvení vrcholů grafu. Veškeré definice a většina matematických vět jsou převzaty z knihy A Course in Combinatorics, kterou napsali Jacobus Hendricus van Lint a Richard Michael Wilson. V kapitolách se nachází nejen definice, nýbrž i příklady s řešením, mnohdy doplněné o grafické znázornění vytvořené s pomocí softwaru AutoCAD od firmy Autodesk. Záměrem teoretické části je seznámit čtenáře se základy z teorie grafů, které jsou podstatné pro porozumění a práci s příklady pro žáky základní školy. V empirické části se nachází popis výzkumu a dva výukové bloky obsahující přípravu na výuku, sebereflexi a analýzu dotazníku. První výukový blok je zaměřen na téma obarvení vrcholů grafu, v přípravě na výuku se vyskytují základní informace týkající se zvolené třídy, časové dotace či použitých pomůcek. Následují mnou vytvořené příklady pro žáky včetně řešení, navržený časový plán a komentáře k průběhu výuky. Příprava na výuku druhého bloku, jenž se věnuje hamiltonovskému grafu, je strukturována obdobně. Oba výukové bloky obsahují obrázky vytvořené v již zmíněném softwaru AutoCAD či pomocí Apple Pencil v aplikaci Goodnotes. Za každým výukovým blokem jsou rozebrány odpovědi žáků, získané cestou dotazníků a má vlastní zpětná vazba ohledně uskutečnění výuky. Konec práce je věnován diskusi výsledků a komentářům pro učitele za účelem zkvalitnění možného provedení výuky. TEORETICKÁ ČÁST 13 1 Teoretická část 1.1 Co je to graf Základní objekt teorie grafů je graf. Běžně se v matematice hovoří o grafu v souvislosti s funkční závislostí. Pomocí grafů můžeme zaznamenávat spotřebu elektrické energie v závislosti na časovém období a jiné. Například ve statistice pracujeme s grafy, používáme různé typy diagramů, ať už sloupcový či kruhový. Na středních školách žáci pracují s grafy funkcí kupříkladu s parabolou1. V teorii diskrétních grafů nahlížíme na grafy ovšem z jiného hlediska. Grafy jsou utvořeny dvěma množinami, množinou vrcholů a množinou hran. Hrana pokaždé spojuje dva vrcholy. 1. Definice: Graf G je uspořádaná dvojice (V, H), kde V je neprázdná konečná množina vrcholů a H je konečná množina hran. 2. Definice: Hrana h {v1, v2} je neorientovaná, v1, v2 ∈ V. Graficky znázorněte následující graf zadaný množinou vrcholů a množinou hran: H = {{x, z}, {y, w}, {z, w}, {x, y}}, V = {x, y, z, w}. Řešení: Graf lze znázornit pomocí bodů představujících vrcholy a křivek znázorňujících hrany. Obr. 1 Grafická reprezentace diskrétního neorientovaného grafu2 1 PŘÍHONSKÁ, Jana. Kombinatorické problémy: aplikace a metody řešení, s. 57. 2 Vlastní zpracování. Pokud není nadále uveden zdroj u obrázku, jedná se o vlastní tvorbu v programu AutoCAD či pomocí Apple Pencil v aplikaci Goodnotes. TEORETICKÁ ČÁST 14 Hrany se většinou znázorňují úsečkami, ale lze je znázornit i oblouky a jinými křivkami – nezáleží přitom na tvaru křivky, jen na tom, které dva vrcholy hrana spojuje. Graf odpovídající základní definici vylučuje násobné hrany, nemůžou být dvě různé hrany mezi dvěma vrcholy a smyčky. Následující struktury nepovažujeme za grafy: Obr. 3 Násobná hrana Obr. 4 Smyčka Kaliningrad Tento příklad je znám již z 18. století a přišel s ním Leonhard Euler, muž, jenž je považován za jednoho z průkopníků teorie grafů. V té době se řešil problém města Kónigsbergu (česky Královec, dnes Kaliningrad). Městem protéká řeka Pregel a tvoří ostrovy, které jsou vzájemně a s pevninou propojeny 7 mosty3. Úloha spočívá v otázce: „Je možná procházka taková, že každý ze 7 mostů přejde člověk právě jednou a vrátí se do téhož místa?“ 3 CIENCIALA, Luděk a Lucie CIENCIALOVÁ. Teorie grafů a grafové algoritmy, s 1–2. Obr. 2 Grafické znázornění hran TEORETICKÁ ČÁST 15 Obr. 5 Kaliningrad4 Řešení: Odpověď zní ne, nejedná se o graf ve smyslu naší uvedené definice. Lze si povšimnout, že úlohu nelze nakreslit jedním tahem. Taková procházka by existovala, kdyby žádný vrchol neměl lichý stupeň, viz následující kapitola. Bez podmínky vrátit se do stejného místa by vycházka existovala, kdyby maximálně dva vrcholy byly stupně lichého. Obr. 6 Naznačený začátek pokusu procházení 5 3. Definice: Vrchol v ∈ V je incidentní s hranou {w, x}, jestliže v ∈ {w, x}. Z definice vyplývá, že vrchol v je s hranou incidentní, pokud je jedním z jejich koncových vrcholů. 4 VAN LINT, Jacobus Hendricus a Richard Michael WILSON. A Course in Combinatorics, s. 6. 5 Tamtéž, s. 6. TEORETICKÁ ČÁST 16 1.2 Stupeň vrcholu a izomorfismus grafů 4. Definice: Stupeň (deg(v)) vrcholu v ∈ V je počet hran, se kterými je vrchol incidentní. 5. Definice: Nechť jsou zadány grafy G1, G2: G1 = (V1, E1), G2 = (V2, E2). Bijekce f: V1 → V2 se nazývá grafový izomorfismus, jestliže ∀ v1, v2 ∈ V: {v1, v2} ∈ H1 ⇔ {f (v1), f (v2)} ∈ H2. Bijekce zobrazení f, které zachovává vrcholy, se nazývá izomorfismus právě tehdy, když zachovává hrany. Nechť jsou zadány grafy G1, G2 (viz obrázky 7, 8). Nalezněte takové zobrazení f, které lze nazvat grafovým izomorfismem. Obr. 7 Graf G1 Obr. 8 Graf G2 Řešení: Je snadné nalézt bijekci mezi vrcholy, ovšem aby se jednalo o grafový izomorfismus, musí být též „zachovány hrany“. Nezáleží na tom, jak se vrcholy či hrany zakreslí, jen na tom, které vrcholy jsou spojeny hranami. Z řešení, ukázaném na obrázku 9 izomorfismus f, je vidno, že počet hran je zachován, stejně jako „vztahy“ mezi vrcholy hranami reprezentované. Izomorfismus grafů tedy pouze „přeznačí“ vrcholy. Obr. 9 Izomorfismus f TEORETICKÁ ČÁST 17 Najdi izomorfismus l grafů mezi graficky znázorněnými grafy H1, H2. Obr. 10 Graf6 H1 Obr. 11 Graf7 H2 Řešení: Při hledání izomorfismu pomyslně hýbeme vrcholy či natahujeme hrany tak, abychom dostali daný graf. V této konkrétní úloze stačí v grafu H1 posunout vrchol 6 dolů níže, než jsou vrcholy 3, 4 a získáme graf H2. Lze si povšimnout, že vrchol 6, který byl stupně tři, se zobrazil na vrchol D, který má též stupeň tři. Obr. 12 Izomorfismus l 1. Věta: Platí, že deg (v) = deg (f (v)) pro izomorfismus f. 2. Věta: Nechť G = (V, H) ⇒ ∑ deg(𝑣) = 2|𝐻|𝑣𝜖𝑉 , neboli součet všech stupňů vrcholů se rovná dvojnásobku počtu hran. (Důkaz plyne ze skutečnosti, že hrana vždy spojuje dva vrcholy.) 1.3 Grafová souvislost, komponenty grafu V úvodu této práce byl zmíněn příklad Kaliningradu, ve kterém vrcholy představovaly místa ve městě a hrany cesty po mostech mezi nimi. Obdobně vrcholy mohou znázorňovat různá města a hrany silnice, které je spojují. Když budeme projíždět autem dvěma městy, zvolenou trasu mezi městem 6 Tamtéž, s. 3. 7 Tamtéž, s. 3. TEORETICKÁ ČÁST 18 A a B nazýváme cesta. V následujících řádcích budou definovány pojmy týkající se podobné záležitosti, jelikož bude zkoumán „pohyb“ grafem8. 6. Definice: Sled (x0, x1, x2, …, xk) je posloupnost vrcholů xi ∈ V, jestliže {xi, xi + 1} ∈ H pro i = 0, 1, …, k − 1. Ve sledu se mohou některé hrany, tudíž i vrcholy, opakovat. Jelikož posuzujeme graf, který má pouze jednoduché hrany, pro zjednodušení zápisu nemusíme psát hrany, vrcholy postačí9. 7. Definice: Nechť G = (V, H). Cesta je posloupnost (x0, x1, x2, …, xk) vrcholů xi ∈ V, že {xi, xi + 1} ∈ H pro i = 0, 1, …, k − 1 a žádný vrchol se v posloupnosti nevyskytuje více než jednou. 8. Definice: Kružnice je taková posloupnost vrcholů (x0, x1, x2, …, xk), že (x0, x1, x2, …, xk − 1) je cesta a navíc xk = x0 a současně {xk − 1, xk} ∈ H. 9. Definice: Graf (V, H) se nazývá úplný, jestliže jsou v něm každé dva vrcholy spojeny hranou. Značí se Kn, kde n je počet vrcholů. 3. Věta: Pro úplný graf platí: 𝐾 𝑛 = (𝑉, 𝐻), kde |V| = n, |H| = ( 𝑛 2 ). 10. Definice: Graf (V, H) se nazývá souvislý, jestliže každé dva různé vrcholy lze spojit nějakou cestou. Nechť je zadán graf G, který |V| = 5. (Počet vrcholů je roven 5.) Jaký musí mít počet hran, aby byl souvislý? Jaký musí mít počet hran, aby byl úplný? Řešení: Aby graf G byl souvislý, |𝐻|≥4. Ve výsledku není žádný vrchol volně, bez incidentní hrany. 8 CIENCIALA, Luděk a Lucie CIENCIALOVÁ, pozn. 3, s. 18. 9 Tamtéž, s. 18. TEORETICKÁ ČÁST 19 Obr. 13 Ukázka řešení, kdy počet hran je roven 4 Při kreslení úplného grafu je vhodné si nejprve nakreslit vrcholy a poté postupně z každého vrcholu přikreslit hrany ke všem zbylým. Nechť je zadán graf G, jehož počet vrcholů je roven 10. (|V| = 10). Platí, že graf není souvislý ⇒ |H| ≤ 36. Určete, kdy nastane rovnost. Řešení: Řešení příkladu sestává z úplného grafu K9, jenž má 36 hran a samotného vrcholu, z něhož žádná hrana nevychází. Řešení se skládá ze 2 komponent, viz následující definice. Obr. 15 Grafické znázornění nesouvislého grafu Obr. 14 Graf K5 TEORETICKÁ ČÁST 20 11. Definice: Nechť G = (V, H). (V0, H0) je podgraf grafu (V, H), jestliže platí a) V0 ⊆ V b) H0 ⊆ H c) ∀ h ∈ H0: h spojuje vrcholy z V0. 12. Definice: Komponenta grafu je jeho maximální souvislý podgraf vzhledem k počtu vrcholů. Když je graf souvislý, počet komponent je jedna. Obr. 16 Grafické znázornění komponenty Graficky znázorněte graf G, jehož počet vrcholů je 7 a skládá se ze dvou komponent, přičemž jedna komponenta je graf K2. Řešení: Ze zadání je známo, že graf má 7 vrcholů, které lze hned nakreslit. Poté je příhodné načrtnout jednu hranu mezi dvěma vrcholy, čímž vznikne graf K2 a zbylé vrcholy spojit mezi sebou. Obr. 17 Řešení 7. příkladu se dvěma komponentami TEORETICKÁ ČÁST 21 1.4 Hamiltonovský graf Problémy spojené s hamiltonovskými kružnicemi pochází z 18. století, kdy byla oblíbená a známá takzvaná úloha jezdce, jenž má za úkol projít prázdnou šachovnici tak, aby na každé pole vstoupil právě jednou a při posledním tahu se vrátil na počátek. Tuto úlohu již řešil L. Euler a zabývali se jí i další matematici jako Alexandra Théophil Vandermond, Peter Guthrie Tait či Thomas Penyngton Kirkman, který se jako první pokusil o určitá zobecnění10. Hamiltonovský graf nese svůj název podle irského matematika W. R. Hamiltona, který v polovině 19. století zveřejnil hádanku, jenž spočívala v nalezení uzavřené trasy procházející dvaceti městy, která jsou rozestavěny ve vrcholech pravidelného dvanáctistěnu, aniž bychom některým vrcholem prošli vícekrát11 (na obrázku 18 je vidno rovinné zakreslení grafu). Na základě jeho práce vznikla hra nesoucí název The Icosian Game, kterou lze z pozdějších verzí znát i pod jménem Cesta kolem světa. Cílem hry bylo napnout provázek kolem všech kolíků tak, aby tvořil kružnici12. 13. Definice: Hamiltonovská cesta je cesta obsahující všechny vrcholy grafu. 14. Definice: Hamiltonovský graf je graf, který obsahuje hamiltonovskou kružnici, jenž prochází všemi vrcholy grafu. 10 ŠIŠMA, Pavel. Vznik a vývoj teorie grafů, s. 92–93. 11 DEMEL, Jiří. Grafy a jejich aplikace, s. 187. 12 ŠIŠMA, Pavel, pozn. 10, s. 93. 13 VAN LINT, Jacobus Hendricus a Richard Michael WILSON, pozn. 4, s. 8. Obr. 18 Grafické znázornění hamiltonovské hádanky13 TEORETICKÁ ČÁST 22 Hamiltonovský graf tkví v průchodu všech vrcholů grafu právě jednou a navrácení se do vrcholu startovního. Z čehož vyplývá, že není zapotřebí použít všechny hrany. Jako typická úloha se udává problém obchodního cestujícího, který má navštívit všechna města v dané oblasti (právě jednou) a vrátit se zpět, tak aby jeho cesta byla nejkratší možná. Úloha ve zjednodušené verzi nepracuje s podmínkou týkající se délky cesty, pracuje se s předpokladem, že vzdálenost mezi městy je jednotková14, neboli délky všech hran jsou stejné. 1.5 Stromy a kostry S grafem typu strom se setkají žáci již na základní škole kupříkladu tehdy, když kreslí svoje rodokmeny. Následně15 i na střední škole či gymnáziu v hodině chemie při psaní molekul uhlovodíku CnH2n − 2. 15. Definice: (V, H) je strom, jestliže a) je souvislý b) neobsahuje kružnice. 14 CIENCIALA, Luděk a Lucie CIENCIALOVÁ, pozn. 3, s. 86. 15 Tamtéž, s. 26. Obr. 19 Ukázka hamiltonovské cesty Obr. 20 Ukázka stromu TEORETICKÁ ČÁST 23 4. Věta: Strom na n vrcholech má (n − 1) hran. 5. Věta: Pro n vrcholů ∃ nn − 2 různých stromů. Nechť je zadán souvislý graf bez kružnic, jehož počet vrcholů n = 4. Kolik existuje odlišných stromů a kolik existuje stromů, které jsou neizomorfní? Řešení: Řešení je vidno z výše zmíněné věty. Existuje 16 (44 − 2) stromů odlišných třeba jen označením. Dva stromy budou navzájem neizomorfní. V prvním stromě se nachází dva vrcholy stupně dva a ve druhém jeden vrchol stupně tři. Obr. 21 Grafické řešení 8. příkladu16 Nechť je zadán souvislý graf bez kružnic, jehož počet vrcholů n = 5. Kolik existuje odlišných stromů a kolik existuje stromů, které jsou neizomorfní? Řešení: Obdobný příklad lišící se pouze větším počtem vrcholů. Postup řešení je stejný. Existuje 125 stromů odlišných třeba jen označením. Výsledek plyne z již zmíněné matematické věty, pro 5 vrcholů existuje 55 − 2 různých stromů. Tři stromy jsou navzájem neizomorfní. První strom, kde se nachází jeden vrchol stupně 4 16 VAN LINT, Jacobus Hendricus a Richard Michael WILSON, pozn. 4, s. 12. TEORETICKÁ ČÁST 24 má 5 izomorfních grafů. Jelikož je pět variant na jeden prostřední vrchol stupně čtyři. Na obrázku 22 lze vidět izomorfní grafy, které obsahují jeden vrchol stupně 4. Druhý strom, kde se nachází tři vrcholy stupně dva, má 60 izomorfních grafů, jež lze spočítat pomocí permutace 5! 2 . Poslední typ stromu, kde je jeden vrchol stupně tři a jeden vrchol stupně dva, má též 60 izomornfích grafů. Při výběru vrcholu stupně tři existuje pět možností, poté na vrchol schupně dva je možno zvolit ze čtyř možností, na závěr na vrchol stupně jedna, jenž navazuje na vrchol stupně dva jsou tři možnosti. Počet grafů je tudíž: 5 · 4 · 3 = 60. Kompletně je 125 izomorfních grafů (60 + 60 + 5), což souhlasí s vypočtem výše. Obr. 23 Grafické řešení 9. příkladu b) Na obrázku 23 lze vidět, že řešení obsahuje 3 navzájem neizomorfní stromy. Druhý typ neizomorfního stromu má tři vrcholy stupně dva. Poslední typ má jeden vrchol stupně tři a jeden vrchol stupně dva. 16. Definice: Kostra (VK, HK) souvislého grafu (V, H) je takový podgraf grafu (V, H), který a) obsahuje všechny vrcholy (VK = V) b) je souvislý c) neobsahuje kružnice. Obr. 22 Grafické řešení 9. příkladu a) TEORETICKÁ ČÁST 25 Kostra souvislého grafu na n-vrcholech má (n − 1) hran. Hledání koster sebou nese praktické využití. Užitečné je hledat kostru v komunikačních sítích, dopravních sítích a dalších užitích17. Nechť je graficky znázorněn souvislý graf G. Zaznačte kostru souvislého grafu. Obr. 24 Zadání 10. příkladu Řešení: Vytváříme souvislý graf, aniž bychom vytvořili kružnici. Cílem je zajistit, aby mezi každými dvěma vrcholy existovala aspoň jedna cesta. Začneme ve vrcholu 1 a přidáváme hrany cest, které vrchol 1 spojují se všemi dalšími vrcholy. Řešení je znázorněno na obrázku 25, kdy všechny možné dvojice vrcholů jsou spojeny nějakou cestou, ta je v tomto konkrétním případě součástí jedné velké cesty. Viz pořadí vrcholů navštívených na cestě: 1, 2, 3, 4, 5, 10, 8, 6, 9, 7. Výsledná kostra je tvořena hranami vyznačenými modře. Algoritmus hledání minimální kostry grafu Úloha zní: „Elektrikář vede elektřinu. Každá cesta má svoji cenu, za kterou se prokope. Najdi cestu za minimální možnou cenu.“ 17 CIENCIALA, Luděk a Lucie CIENCIALOVÁ, pozn. 3, s. 30. Obr. 25 Řešení 10. příkladu TEORETICKÁ ČÁST 26 Jedná se o takzvaný oceněný či vážený graf. Hledáme kostru souvislého grafu. Při řešení úlohy postupujeme od nejnižších hodnot a nesmíme vytvořit kružnici. Konkrétní zadání úlohy týkající se hledání minimální kotra grafu: „Je graficky znázorněn oceněný graf G. Zaznačte minimální kostru grafu.“ Obr. 26 Zadání 11. příkladu 17. Definice: Nechť je graf G = (V, H). f: H → R, cenová funkce, která každé hraně přiřazuje cenu. Řešení: Je zapotřebí přidávat postupně hrany s nejnižší cenou, které jsou napojeny na vznikající strukturu a současně nevytvořit kružnici. Výsledek je znázorněn oranžovými hranami. Obr. 27 Řešení 11. příkladu TEORETICKÁ ČÁST 27 Lze najít nejkratší hamiltonovskou kružnici za pomoci hladového algoritmu? Řešení: Pátrání po nejkratší hamiltonovské kružnici připomíná Algoritmus hledání minimální kostry grafu, kdy se hledalo nejlevnější možné vedení elektřiny, jinými slovy hledala se minimální kostra grafu. Dle pana docenta Fuchse je hledán podgraf, v kterém jsou propojeny všechny vrcholy a současně neobsahuje kružnici.18 Hladový algoritmus probíhá krok za krokem, v každém kroku se odehrává výběr místně optimální volby bez záruky nalezení kompletně optimálního řešení na konci.19 Jelikož hladový algoritmus využíváme k nalezení minimální kostry, v některých případech je možné, že nalezená kostra bude využitelná pro úkol nalézt hamiltonovskou kružnici – tehdy, když minimální kostra bude současně cestou, dodatečně přidáme k cestě poslední hranu, která z cesty utvoří kružnici. Při řešení úlohy je nutné dodržet podmínku, že cesta povede všemi vrcholy a každým vrcholem právě jednou, tudíž jeden vrchol nesmí být incidentní se třemi hranami. Obr. 28 Nejkratší hamiltonovská kružnice Na obrázku výše je zvýrazněna červená hamiltonovská kružnice, jejíž hrany mezi vrcholy byly vybrány pomocí hladového algoritmu. Cesta začala ve vrcholu a, poté byly postupně přidány hrany s nejnižší hodnotou, na závěr za účelem vytvoření 18 FUCHS, Eduard. Práce z teorie grafů, s. 174. 19 PAIVA, Henrique Mohallem; Priscila Falcão dos SANTOS; Marcos Ricardo Omena de Albuquerque MÁXIMO a Lucas NIEMEYER. Efficient Lecturer Peer-Assessment Attribution Using Graph Theory and a Novel Greedy Algorithm, s. 14742–14750. TEORETICKÁ ČÁST 28 hamiltonovské kružnice byla dodána hrana mezi vrcholy a, f. Červená hamiltonovská kružnice je v grafu nejkratší. Nejkratší hamiltonovskou kružnici nelze za pomoci hladového algoritmu pokaždé nalézt. Tvrzení je dokázáno protipříkladem viz obrázek 29. Obr. 29 Důkaz protipříkladem Červená hamiltonovská kružnice je vybrána pomocí hladového algoritmu se startovním vrcholem e. Postupným vybíráním nejmenších hodnot cesta dorazí k vrcholu c, kde je za účelem získání hamiltonovské kružnice nucena využít hranu mezi vrcholy e, c. Tato cesta není nejkratší, což lze konstatovat na základě vytvoření modré cesty. Závěrem lze říci, že podmínky hamiltonovské kružnice a hladového algoritmu dohromady nefungují. 1.6 Rovinný graf 18. Definice: Rovinný graf je takový graf, ke kterému existuje rovinná reprezentace, rovinné nakreslení. Rovinný graf lze nakreslit do roviny tak, aby se žádné dvě hrany nekřížily, a hrany se neprotínají jinde než ve vrcholech. Je graf znázorněný na obrázku rovinný? Obr. 30 Zadání 12. příkladu TEORETICKÁ ČÁST 29 Řešení: Na první pohled se hrany kříží v bodě mimo vrchol. Můžeme ho však překreslit? Existuje jeho rovinné nakreslení? Odpověď zní ano, když vrchol b přesuneme, viz graficky znázorněné řešení. Obr. 31 Řešení 12. příkladu 6. Věta: (Kuratowského) Graf je rovinný právě tehdy, jestliže neobsahuje podgraf, který by byl grafem K5 nebo K3, 3 nebo grafem získaným z některého z těchto grafů postupným půlením hran20. Slavná úloha o 3 domech a 3 studních Tři obyvatelé tří domů mohou využívat všech tří studní, tudíž každý z nich by chtěl, aby od jejich domu vedly cesty, po kterých by se ke všem třem studním dostali. Zároveň ani jeden soused nechce, aby se jejich cesty protínaly se sousedovými21. Řešení: Úloha lze vyřešit právě tehdy, když existuje rovinná reprezentace tohoto grafu22. Hledáme systém nekřižujících se cest. U dvou domů úloha vychází, u tří již nemá řešení. 20 ZELINKA, Bohdan. Rovinné grafy, s. 49–50. 21 Tamtéž, s. 43–44. 22 Tamtéž, s. 44. Obr. 32 Úloha o 3 domech a 3 studních TEORETICKÁ ČÁST 30 Z obrázku 32 je zřejmé, že jeden ze sousedů bude muset buď navštěvovat pouze dvě studny nebo chodit po cestě, jenž protíná sousedovu. Graf týkající se dané úlohy je typu K3, 3. 1.7 Obarvení vrcholů grafu Praktické využití barvení vrcholů grafu spočívá kupříkladu v řešení takzvaného skladovacího problému. Zmíněný problém nastává z důvodu skladování různých druhů zboží, jež nemohou být skladovány dohromady. Abychom minimalizovali náklady, je třeba určit nejmenší počet oddělených skladovacích prostor tak, aby zboží bylo uloženo společně pouze tehdy, když je to v pořádku. Další příklad praktického užití lze spatřit při tvoření zasedacího pořádku ať už na oslavě či svatbě23. 19. Definice: Obarvení vrcholů grafu je takové ohodnocení vrcholů barvami z množiny B, že žádné dva sousední vrcholy nejsou ohodnoceny stejnou barvou. Každému vrcholu se přiřadí barva. R-barevný graf je takový graf, že existuje jeho obarvení R barvami. 20. Definice: Chromatické číslo grafu určuje minimální možný počet barev potřebný na jeho obarvení. Chromatické číslo grafu G značíme jako χ(G). Narozeninová oslava Zveme kamarády, z nichž někteří se znají. Na oslavu je zváno celkem 8 lidí. Cílem je posadit hosty tak, aby se lidé u stolu neznali. V zadání jsou osoby značeny jejich iniciálami: a… zná: d, f, g b… zná: c, d, h c… zná: b, e d… zná: a, b, f 23 CIENCIALA, Luděk a Lucie CIENCIALOVÁ, pozn. 3, s. 62. e… zná: c, f f… zná: a, d, e g… zná: d h… zná: b TEORETICKÁ ČÁST 31 Řešení: Vrcholy budou představovat osoby a hrany známost mezi nimi. Řídíme se tím, aby žádné dva sousední vrcholy nebyly ohodnoceny stejnou barvou. Pro přehlednost barvy jsou značeny čísly. Lze postřehnout, že kvůli lidem a, d, f je zapotřebí použít 3 barvy, tudíž budeme potřebovat 3 stoly na oslavu. Obr. 33 Řešení úlohy zvané narozeninová oslava V roce 1852 položil student University College v Londýně Francis Guthrie otázku, jež dnes známe jako problém čtyř barev, Augustu de Morganovi. F. Guthrie se svým bratrem, který se později stal profesorem matematiky v Kapském Městě, si všimli, že v některých případech jsou nutné k obarvení mapy čtyři barvy tak, aby každé dvě sousední země měly odlišnou barvu. Zároveň nenašli případ, kdy čtyři barvy nestačí. Důkaz se jim však sestrojit nepodařilo. Augustus de Morgan požádal o pomoc Hamiltona, který mu však nepomohl, a tak byl problém šířen dál, až se stal součástí matematického folklóru. Problém byl kladně vyřešen až v roce 1976, na jejímž řešení se podíleli Kenneth Appel a Wolfgang Haken z univerzity v Illinois. Důkaz byl proveden na počítači a trval téměř 1200 hodin strojového času a muselo se při něm rozlišovat skoro 2000 odlišných případů24. 24 ŠIŠMA, Pavel, pozn. 10, s. 94–95. TEORETICKÁ ČÁST 32 Problém politické mapy Kolik barev potřebujeme na vybarvení politické mapy, aby sousední státy nebyly vybarveny stejnou barvou? Mapa zadána obrázkem. Obr. 34 Problém politické mapy – zadání Řešení: Vrcholy grafu v dané úloze znázorňují státy a hrany společné hranice. Postupně přiřazujeme barvy. Státy, které mají společnou hranici, musí nést odlišné obarvení. Daný příklad je rovinný. Z obrázku je zřejmé, že na vybarvení politické mapy potřebujeme čtyři barvy. Obr. 35 Problém politické mapy – řešení Jaké je chromatické číslo pro obarvení rovinného grafu? 7. Věta: U rovinného grafu χ(G) ≤ 4. TEORETICKÁ ČÁST 33 8. Věta: (Brooksova) Nechť d ≥ 3 a G je graf, ve kterém mají všechny vrcholy stupeň ≤ d a Kd + 1 není podgrafem G. Potom platí, že χ(G) ≤ d. (d značí maximální stupeň vrcholů) Důkaz: Danou větu lze dokázat sporem. Lze uvažovat, že tato věta není pravdivá, a poté najít protipříklad, čímž dospějeme ke sporu. Nechť G je protipříkladem a zároveň platí, že vrchol x ∈ G. Sousední množina vrcholu x je Γ(x) = {x1, …, xl}, l ≤ d. Jelikož G je protipříkladem, graf H, který získáme odstraněním vrcholu x a hran incidentních s x, má d-obarvení, s barvami 1, 2, …, d. Pokud jedna z těchto barev není použita v obarvení Γ(x), můžeme přiřadit tuto barvu k x a získat tak d-obarvení grafu G. Z toho plyne, že l = d a každé d-obarvení H musí použít všechny barvy z množiny Γ(x). Předpokládejme, že xi má barvu i pro i = 1, 2, …, d. Nyní uvažujme xi a xj a indukovaný podgraf Hij grafu H s barvami i a j. Pokud by xi a xj byly v různých souvislých komponentách Hij, mohli bychom prohodit barvy v jedné z těchto komponent, poté by xi a xj měly stejnou barvu, což je nemožné. Takže xi a xj jsou ve stejné komponentě (řekněme Cij) Hij. Je předpokládáno, že vrcholy xi a xj z Γ(x) nejsou spojeny hranou. Potom existují dvě cesty Cij a Cik v grafu H, které obsahují xi a mají různé barvy na koncích. Zkoumáním sousedů xi na Cij a Cik a využitím faktu, že vrcholy mají maximálně d − 2 barev, dochází ke sporu. Tedy jsme došli k protikladu, což znamená, že předpoklady o existenci protipříkladu jsou nesprávné. To znamená, že věta platí25. Obr. 36 Důkaz Brooksovy věty26 25 VAN LINT, Jacobus Hendricus a Richard Michael WILSON, pozn. 4, s. 24–27. 26 Tamtéž, s. 26. TEORETICKÁ ČÁST 34 Režiséři V divadle je k dispozici šest herců. Divadelní představení obsahuje osm rolí. Je možné představení zahrát, když jsou některé postavy v daných momentech současně na jevišti? Postava 1 je současně na jevišti s postavami: 3, 6, 7, 8. Postava 2 je současně na jevišti s postavami: 3, 4, 8. Postava 3 je současně na jevišti s postavami: 8, 4, 6. Postava 4 je současně na jevišti s postavami: 8, 6, 5, 7. Postava 5 je současně na jevišti s postavami: 7, 6. Postup: Jestliže jsou ve scénáři současně na jevišti postavy ⇒ existuje mezi nimi hrana. Barvy představují herce a čísla vrcholů role. Řešení: Pro dané zadání lze najít řešení, stačí 4 herci. Při jednom z možných řešení se obarví první vrchol (1) barvou modrou. Jeho sousední tři vrcholy (7, 8, 3) musí být označeni jinou barvou – žlutá, červená, zelená. Zmíněné tři vrcholy mají ještě jeden společný vrchol (4), kterému můžeme přiřadit již jednou použitou modrou barvu. Vrchol (4) má další dva sousední body. Jelikož je vrchol (5) spojen s vrcholem (7) nelze přiřadit žluté obarvení. Zbývají na výběr dvě barvy, zvolíme červenou. Sousedé vrcholu (6) mají červenou, modrou i zelenou barvu, tudíž musí být žlutý. Zbývající vrchol (2) musí být obarven žlutou. Obr. 37 Řešení 16. příkladu Režiséři Obr. 38 Rovinné zobrazení grafu z 16. příkladu Je graf rovinný? Ano, je, viz obrázek 38. EMPIRICKÁ ČÁST 35 2 Empirická část 2.1 Popis výzkumu Vzhledem ke stanoveným cílům je druhá polovina práce věnována příkladům z teorie grafů pro žáky na druhém stupni základní školy, konkrétně 7. třídy. Záměrem práce je realizovat výuku teorie grafů na základní škole, obohatit výuku žáků a zjistit do jaké míry žáci na výuku reagovali. Posléze navrhnout vodítka pro možnou realizaci v sedmém ročníku. Na základě výše popsané teorie jsem sestavila pracovní listy s vlastními úlohami týkající se vybraných kapitol z teorie grafů. V praktické části se nachází příprava na výuku dvou výukových bloků, kde jsou slovní úlohy popsány včetně řešení. Úlohy byly realizovány ve dvou výukových blocích. Za každým výukovým blokem je sepsána má sebereflexe týkající se realizace těchto výukových bloků. Je zde pospána má zkušenost s aplikováním úloh přímo ve třídě. Provedení výuky je reflektováno z hlediska dodržení časového rozpisu, naplnění cílů či obtížnosti úloh. Následně je sepsána analýza dotazníků, které na konci každého bloku žáci vyplnili. V dotaznících jsou žáci tázáni na jejich názory, též se zde vyskytují testovací úlohy za účelem ověření naplnění konkrétních cílů výuky. 2.2 První výukový blok 2.2.1 Příprava na výuku Téma: Obarvení vrcholů grafu Třída: 7. třída Místo: Velké Němčice Délka vyučovací jednotky: 90 minut (2 × 45 minut) Cíle: Žák popíše, z kolika hran a vrcholů se graf skládá. Žák převede zadání úlohy na problém počtu barev obarvení grafu. Žák vytvoří graf dle mapy znázorňující oblasti (státy, kraje apod.) a jejich společné hranice. Žák aplikuje pravidla obarvení vrcholů grafu za účelem vyřešení daných úloh. EMPIRICKÁ ČÁST 36 Pomůcky: vytištěné papíry s úlohami, křídy/fixy na tabuli, psací potřeby (pero, pastelky či fixy) Pro úsporu času a plynulý průběh hodiny je doporučeno využít notebook či jiné výpočetní zařízení s dataprojektorem. Napojení na RVP ZV: V rámcovém vzdělávacím programu pro základní vzdělávání se nachází vzdělávací oblast Matematika a její aplikace, která předává vědomosti a dovednosti zužitkovatelné v reálném životě, a zprostředkovává tak matematickou gramotnost. Tato oblast je rozdělena na čtyři tematické okruhy. První okruh s názvem Čísla a početní operace pro žáky na prvním stupni, na který na druhém stupni navazuje a dále ho prohlubuje tematický okruh Číslo a proměnná. Druhý okruh se jmenuje Závislosti, vztahy a práce s daty, poté následuje Geometrie v rovině a v prostoru a poslední okruh zní Nestandardní aplikační úlohy a problémy, jejichž řešení může být do určité míry nezávislé na znalostech a dovednostech školské matematiky, ale při kterém žáci musí logicky přemýšlet. 27 Jelikož žáci ve vyučování zpracovávají mapy smyšlené i reálné, řeší slovní úlohy za pomoci grafů a aplikují dané principy, lze tuto výuku zařadit právě do okruhu Nestandartních aplikačních úloh a problémů. Úvod: 5 min Nejdříve se vyučující představí před třídou a krátce popíše plán společné výuky, poté rozdá čisté papíry a následuje vyrábění si jmenovek. Za účelem žádaného chodu výuky je zapotřebí žákům sdělit, že přínos společně stráveného času spočívá v rozšíření jejich znalostí a povzbuzení zájmu o matematiku. Je důležité žáky ujistit, že se jejich činnost v hodině nebude známkovat. Ceněná je především aktivní účast. Během výuky je v pořádku požádat o pomoc či klást jakékoli otázky týkající se tématu. Není zapotřebí se stydět zeptat, odpověď na vznesený dotaz může pomoci nejen žákovi/žákyni, který/á otázku položil/a. Pokud si chce vzít žák/žákyně slovo, je nutné se přihlásit, ať nevznikne ve vyučování hluk, který by mohl ostatní rušit. 27 MŠMT. Rámcový vzdělávací program pro základní vzdělávání, s. 31. EMPIRICKÁ ČÁST 37 Seznámení se s teorií grafů: 10 min Vyučující žákům sdělí: „Teorie grafů je obor matematiky, jež zkoumá grafy skládající se z vrcholů a hran.” Nakreslí obrázek na tabuli a barevně zvýrazní vrchol a hranu, grafické znázornění doplní slovním komentářem. Obr. 39 Nákres na tabuli Vyučující poprosí žáky, ať zkusí na tabuli nakreslit vlastní grafy skládající se z vrcholů a hran, načež se u konkrétních grafů doptá, z kolika hran a vrcholů se skládají. Následuje rozdání pracovních listů, jež jsou k nahlédnutí na konci práce v přílohách, a stručné seznámení s jejich strukturou. Práce s pracovními listy 1. Úloha: 5 min Vybarvi mapu znázorněnou na obrázku A, takovým způsobem, že státy, jež mají společnou hranici, nebudou obarveny stejnou barvou. Přitom se snaž použít, co nejméně barev. Kolik bude potřeba nejméně barev na vybarvení mapy? Obr. 40 Zadání mapa A Učitel/ka požádá žáka/žákyni o přečtení zadání. Následně nechá žákům čas pro vyřešení úlohy. Žáci barví mapu bez znalosti teorie grafů. EMPIRICKÁ ČÁST 38 Vlastní zpracování: Obr. 41 Vybarvení mapa A Na obrázku je znázorněno jedno z možných barevných řešení mapy. Žáci mohou použít libovolné barvy a začít u kteréhokoli státu. Nejméně jsou potřeba tři barvy. V tuto chvíli je třídě sděleno: „Tento úkol lze řešit pomocí teorie grafů. Jedná se o takzvané obarvení vrcholů grafu.“ Poté vyučující uvede pravidlo, jež se při obarvení vrcholů grafu aplikuje: „Když barvíme vrcholy grafů, barvíme je tak, že žádné dva sousední vrcholy nemají stejnou barvu.“ 2. Úloha: 15 min (včetně navrácení k první úloze) Zakroužkuj sousední vrcholy vrcholu A, vrcholu N a vrcholu P? Obr. 42 Zadání – sousední vrcholy Po dokončení druhé úlohy v pracovním listě se učitel/ka vrací k první úloze a promítá mapu na tabuli. Učitel/ka ukáže žákům možnost místo vybarvení celých ploch států obarvit vrcholy. Žákům se položí otázka: „Kdo ví, čím nahradíme každý stát?“ Učitel/ka žákům pomáhá, snaží se je na správnou odpověď navést: „Co vidíte na obrázku, kde budou vrcholy zakresleny?” Pokud žáci stále nereagují, je položená EMPIRICKÁ ČÁST 39 pomocná otázka: „Vrcholem nebo hranou?” Poté učitel/ka požádá žáka/žákyni o nakreslení vrcholů do mapy na tabuli. Následuje otázka: „Mezi kterými vrcholy při řešení kreslíme hranu?“ Očekávaná odpověď: „Jejichž státy mají část hranice společnou.“ Opět učitel/ka v případě potřeby pomůže doptáváním se a poprosí dobrovolníka o nákres na tabuli. Žáci si graf nakreslí do svých pracovních listů. Učitel/ka seznamuje žáky se strategií obarvování grafů a zadává pokyny. „Obarvěte si jeden libovolný vrchol červenou barvou. Máme všichni jeden vrchol obarvený?“ Sama obarví jeden vrchol na tabuli. „Obarvěte jinou barvou ty vrcholy, které sousedí s vrcholem, který jsme již obarvili. Pozor, vrcholy nesmí navzájem sousedit. Zvolme si modrou.“ U tabule zabarví vrcholy budˇ učitel/ka nebo dobrovolník. „Pokud existují vrcholy, které sousedí s vrcholy obou předchozích barev současně, obarvíme je třetí barvou například zelenou. Jestliže zatím neexistují takové vrcholy, lze použít znovu první barvu (červenou) na vrcholy, jež jsou připojené k pouze modrým vrcholům a nesousedí spolu navzájem.” Učitel/ka předvede na tabuli. V tomto algoritmu lze nadále pokračovat, učitel/ka spolu s žáky dokončí příklad. Vlastní zpracování: Řešení úlohy pomocí teorie grafů. Obr. 43 Řešení mapy A Po skončení společné práce mají žáci zadanou třetí úlohu v pracovním listě. EMPIRICKÁ ČÁST 40 3. Úloha: 10 min Uplatni teorii grafů a zjisti, kolik bude potřeba nejméně barev na vybarvení České republiky takovým způsobem, že kraje, jež mají společnou hranici, nebudou obarveny stejnou barvu. (Graf můžeš kreslit přímo do mapky.) Obr. 44 Zadání mapa ČR Uloha je zadana k samostatnemu resení. Pri resení lze vrcholy nakreslit uvnitr jednotlivych uzemí a hrany mezi vrcholy, jejichz uzemí mají spolecnou cast hranice. Jelikoz zaci resí ulohu tykající se obarvení vrcholu grafu poprve samostatne, je zapotrebí pozorovat, jak si s ukolem vedou a resení koordinovat. Abychom pomohli studentům, kterým se tolik nedaří, lze pro ně úlohu rozfázovat. Učitel/ka kontroluje postup žáků. Žákům, kteří neví, jak začít s řešením, vyučující poradí, doptává se: „Čím nahradíme každý kraj?“ Ostatní žáci pokračují svým tempem. Vlastní zpracování: Obr. 45 Vybarvení mapa ČR Nejméně jsou potřeba čtyři barvy. Na obrázku je znázorněno jedno z možných barevných řešení. EMPIRICKÁ ČÁST 41 Když je většina žáků hotova, na tabuli se promítne mapa a dobrovolník jde namalovat na tabuli své řešení. Žáci sdílí svá řešení, sdělují, čím se jejich liší a vyučující podává zpětnou vazbu na jejich práci. Vyučující poví žákům o širším využití barvení vrcholů grafu. „Nalezneme ho při řešení úloh, týkající se zasedacího pořádku či skladovacího problému. Kupříkladu skladování nebezpečných látek, plánování procesů, kdy některé akce nesmí probíhat současně, vytváření rozvrhů a další. Obr. 46 Řešení mapa ČR Následující čtyři úlohy nechá vyučující nejprve k samostatnému řešení či řešení ve dvojicích. Úlohy lze následně rozfázovat: čas k samostatnému řešení, společné sdílení grafů, doba k obarvení grafů a ukázka výsledku s případnou diskusí. Když žáci tvoří graf či barví vrcholy, vyučující nabízí individuální pomoc. 4. Úloha: 10 min Seznamovací hra Na tábor jede Marie, Klára, Richard, Hana, Tomáš, Jan, Lukáš, Eliška a Bára. Je zapotřebí, aby se všichni děti spolu seznámili, tudíž u stolu mohou sedět pouze osoby, které se neznají. Kolik budeme potřebovat stolů? Budou stačit čtyři stoly, jež máme k dispozici? Vrcholy budou představovat osoby a hrany jejich známost. a) Zobraz kamarády a jejich známost do grafu: Marie zná: Hanu, Lukáše, Báru Hana zná: Marii, Tomáše, Lukáše EMPIRICKÁ ČÁST 42 Tomáš zná: Hanu, Lukáše, Jana Jan zná: Tomáše, Richarda, Báru, Kláru, Elišku Eliška zná: Jana, Kláru Klára zná: Elišku, Jana, Báru Bára zná: Kláru, Jana, Lukáše, Marii Lukáš zná: Marii, Hanu, Tomáše, Richarda, Báru Nápověda: Vrcholy budou představovat osoby a hrany jejich známost. b) Obarvi vrcholy a zjisti kolik bude potřeba nejméně stolů. Vlastní zpracování: Na seznamovací aktivitu nám budou stačit 3 stoly. Obr. 47 Graf seznamovací hra 5. Úloha: 5 min Harmonogram prohlídek Jedna z památek, na kterou se děti z tábora mohou jít podívat, je hrad. Na hradě jsou naplánované a zarezervované prohlídky, avšak onemocněli jim někteří průvodci a manažer řeší, zda je se zbývajícími zaměstnanci možné prohlídky v daných časech uskutečnit. Pomoz manažerovi a určit kolik průvodců je zapotřebí. Harmonogram: 8:00 – 9:00 8:30 – 9:30 9:00 – 10:00 9:15 – 10:15 9:45 – 10:45 EMPIRICKÁ ČÁST 43 Vlastní zpracování Při řešení úlohy vrcholy představují prohlídky a hrany značí, že prohlídky probíhají současně. Cíl je zjistit, jaké je minimum průvodců, což ukáže počet barev. Obr. 48 Graf harmonogram prohlídek 6. Úloha: 10 min ZOO Byla postavena nová zoo. Přivezli první zvířata a je nutné je rozmístit do výběhů. Kolik výběhů minimálně potřebujeme, když u každého zvířete je nutno splnit určité podmínky? Lev = všechny ostatní zvířata sežere, potřebuje teplo Zebra = potřebuje teplo Kojot = sežere páva a klokánka, potřebuje teplo Páv = potřebuje teplo Lachtan = potřebuje zimu Tuleň = potřebuje zimu Klokánek = potřebuje teplo Emu = potřebuje teplo Kozoroh = potřebuje teplo Vlastní zpracování: Vrcholy nyní demonstrují zvířata a hrany ukazují, které zvířata nemohou být spolu ve výběhu. Počet barev nám prozradí, kolik je nezbytných výběhů. EMPIRICKÁ ČÁST 44 Obr. 49 Graf ZOO 7. Úloha: 10 min Rezervační problém Komplex má 6 dvoulůžkových chatek, na které v měsíci červenec přijal tyto rezervace: 1. 7. – 7. 7. 1. 7. – 3. 7. 2. 7. – 5. 7. 6. 7. – 10. 7. 8. 7. – 12. 7. 11. 7. – 7. 7. 9. 7. – 19. 7. 21. 7. – 25. 7. 23. 7. – 28. 7. 24. 7. – 30. 7. Každá rezervace je na jednu dvoulůžkovou chatku (2 postele). Kolik chatek je nezbytných, abychom splnili přijaté rezervace? Bude vyhovovat kapacita chatek se dvěma lůžky, kterou komplex disponuje, na schválené rezervace? Vlastní zpracování Rezervace jsou zobrazeny pomocí vrcholů. Ty, které se překrývají, mají mezi sebou hranu. Počet pokojů je vyřešen pomocí počtu barev. EMPIRICKÁ ČÁST 45 Obr. 50 Graf rezervační problém Zakončení: 10 min Vzhledem k mé bakalářské práci je na závěr výuky žákům rozdán dotazník s následujícím zněním. 1. Jak ti připadal dnešní program? Obr. 51 Hodnotící škála dotazník 2. Nakresli libovolný graf a popiš z kolika vrcholů a hran se skládá: 3. Proveď obarvení vrcholů grafu a zjisti, kolik bude potřeba nejméně barev, aby žádné státy, jež mají společnou hranici, neměly stejnou barvu. (Přímo do mapy zakresli vrcholy a hrany.) Obr. 52 Střední Evropa EMPIRICKÁ ČÁST 46 4. Na které slovní úloze se ti nejlépe pracovalo? Uveď alespoň jeden důvod proč. 5. Vzkazy či připomínky ohledně dnešního programu zanechej zde: Ukázka vyplněných dotazníků se nachází na konci práce v přílohách. 2.2.2 Sebereflexe Po bezproblémovém začátku výuky se žáci zběžně seznámili s grafy a přihlásilo se pár dobrovolníků, kteří nakreslili několik grafů na tabuli. Ostatní byli tázáni, z kolika vrcholů a hran se grafy skládají. Následovala první úloha z pracovního listu, řešení příkladu bez použití teorie grafů. Někteří žáci úloze hned porozuměli, ostatní bylo potřeba upozornit, aby státy za účelem použití nejméně barev barvili postupně nikoli nahodile, obarvit jeden stát, poté jeho sousedy a pokračovat dále. Druhou úlohu se dařilo žákům ihned vyřešit, nebylo nutné jim radit. Nenechali se nachytat umístěním vrcholů na papíře. Žáci sami došli k závěru, že mezi sousedními vrcholy musí existovat hrana, aniž bych jim tuto podmínku předem sdělila. Poté jsme se vrátili k první úloze a postupovala jsem ve vysvětlování obarvení vrcholů dle přípravy. Představila jsem žákům vhodný postup na prvních státech a pro dobarvení mapy jsem se žáků doptávala, jaké barvy by volili a z jakého důvodu. Následovala samostatná třetí úloha, při které jsem žáky obcházela a nabízela potřebným pomoc. Tuto úlohu se některým dařilo plnit výrazně lépe než jiným. Žáci si nejprve vytvářeli graf sami, poté šel jeden z rychlejších žáků nakreslit svůj graf do promítnuté mapy na tabuli. Následně žáci společně opravili chyby, jež na tabuli byly a ti, kterým se tolik nedařilo, si opravili své grafy dle tabule. Potom přišlo na řadu barvení. Při obcházení jsem si všimla opakující se chyby, kdy žáci zbytečně barvili karlovarský a středočeský kraj jinou barvou, na chybu jsem poté všechny upozornila. Jeden ze žáků se sám přihlásil a zeptal se, jak naložit s Prahou, která se nachází uvnitř středočeského kraje. Během sdílení svých řešení u tabule, jsme společně dospěli k závěru, že je při barvení nezbytné dát přednost společným sousedům míst, která již byla obarvena. EMPIRICKÁ ČÁST 47 Zde skončila první polovina výukového bloku, již nyní jsem se nacházela v časovém deficitu. Úvodní část, vyrábění jmenovek, první úloha, vše trvalo déle, než jsem předpokládala. Ve čtvrté úloze žáci řešili zasedací pořádek. Žáci dostali chvilku na zamyšlenou, a pak jsem se zeptala, co budou v grafu představovat vrcholy a hrany. Protože všem žákům nebylo jasné, jak úlohu pomocí grafu řešit, ukázali jsme si na tabuli, jak zakreslit Marii a její kamarády. Žáci následně sami úlohu vyřešili. Několik žáků si výsledek barvení vrcholů s počtem stolů spojilo, avšak ne všichni, proto jsme si na konci úlohy na tabuli vypsali, kdo bude u kterého stolu sedět. Poslední realizovanou úlohou byl harmonogram prohlídek. Domnívala jsem se, že úloha bude pro žáky přiměřeně složitá, jelikož je výsledný graf pouze z pěti vrcholů a šesti hran. Žáci neviděli spojitost mezi zadáním a využitím grafu. Chybně jsem se domnívala, že jednodušší graf znamená lehčí úlohu. Úlohy ZOO a rezervační problém se z časových důvodu nepodařilo zrealizovat. Časový harmonogram byl příliš ambiciózní. Žáci potřebovali nejen k řešení, nýbrž i sdílení svých řešení více času. Předpokládám, že další důvod nedodržení časového rozvrhu by mohl souviset s nedostatkem mých zkušeností, poněvadž jsem výuku ve třídě vedla poprvé, s delší praxí bych dokázala lépe hospodařit s časem. Délka bloku s pauzou byla přiměřená. Čas byl dostačující, aby se žáci s tématem grafů a základními pravidly obarvování vrcholů seznámili. Delší setrvání na jednom tématu by bylo příliš únavné. Žáci po výuce ocenili, že jejich další předmět byl cizí jazyk, nikoli matematika. Aby si žáci používání grafů k řešení slovních úloh více osvojili, bylo by nutné řešit s žáky více obdobných úloh, kde by měli možnost si pravidla zopakovat a trénovat. Navzdory náročné výuce vyžadující aktivní přístup žáků a plnou pozornost, se žáci vyjadřovali pozitivně ohledně společně stráveného času. Kladně hodnotili, že se naučili novou strategii, jak mohou řešit slovní úlohy, konktrétně se odkazovali na úlohu Seznamovací hra. Doporučení využít dataprojektor se osvědčilo. Daná výuka lze provést i bez tohoto zařízení, učitel může kreslit grafy na tabuli včetně načrtnutých map. Použití EMPIRICKÁ ČÁST 48 dataprojektoru umožní šetřit čas, jehož je omezené množství a též promítání stejného grafu vícekrát na jednom snímku v prezentaci, tudíž může více žáků předkládat svá řešení zároveň. 2.2.3 Analýza dotazníku V první otázce je zkoumán postoj žáků stran náročnosti a spokojenosti s výukou. Žáci svůj názor značili do škály. Většina žáků, čtrnáct ze šestnácti, se přikláněla k postojům, že první výukový blok je zábavný, velmi zábavný či naprosto zábavný. Jeden žák neodpověděl a jeden žák se vyjádřil neutrálně. Graf 1 Poutavost první výuky Polovina třídy se vyjádřila neutrálně ohledně náročnosti výuky, sedm žáků se přiklánělo k názoru, že je výuka jednoduchá, velmi jednoduchá nebo naprosto jednoduchá. Pro jednoho žáka byla výuka složitá. Graf 2 Obtížnost první výuky Ve druhé otázce žáci kreslili libovolný graf, u kterého popisovali z kolika vrcholů a hran se skládá. Všichni zvládli libovolný graf nakreslit. V dotaznících se objevovaly EMPIRICKÁ ČÁST 49 grafy se třemi až sedmi vrcholy. Nejčastější graf se skládal ze třech vrcholů a třech hran, jež vzhledem připomíná geometrický útvar trojúhelník. Z odpovědí žáků bylo vidno, že žáci čerpali inspiraci z již nabytých poznatků a volili radši jednodušší grafy. V této úloze odpověděli dva žáci chybně, jednalo se buď o početní chybu týkající se uvedení počtu vrcholů grafu, nebo tento údaj chyběl. Graf 3 Tvoření a popis grafu Třetí úloha spočívala v řešení obarvení států střední Evropy za pomoci obarvování vrcholů grafu. Zde žáci nebyli tak úspěšní jako v předchozí otázce. Pouze dva jednotlivci odpověděli zcela správně. Pro evaluaci řešení dané úlohy je třeba si příklad rozfázovat a hodnotit fáze odděleně. Úskalím úlohy bylo pro žáky tvoření grafu. Ve většině případů byl zvolen správný postup, vrcholy ležely uvnitř států a hrany mezi vrcholy značily společnou hranici. Častou chybou byla absence jedné či dvou hran, mnohdy chyběla hrana mezi Švýcarskem a Rakouskem. Nejspíš bylo příčinou Lichtenštejnsko, jehož velikost a pozice žáky zmátla. Při obarvování grafů žáci korektně barvili sousední vrcholy jinou barvou, avšak pouze sedm žáků přišlo na nejmenší počet barev. Žáci dodrželi vhodné pořadí obarvování států pouze zčásti, nedali přednost společným sousedům již obarvených států. Dva žáci z celé třídy patrně neporozuměli obarvení mapy a měli stejnou barvou státy ležící vedle sebe. EMPIRICKÁ ČÁST 50 Graf 4 Vybarvení politické mapy V další otázce žáci odpovídali, na které slovní úloze se jim nejlépe pracovalo a svoji odpověď zdůvodňovali. Většina napsala úlohy s mapami. Kladně hodnotili, že mohou značit grafy přímo do map. Třetina z žáků, kteří napsali úlohy s mapami, zmiňovala konkrétně první mapu, která byla podle nich lehčí, protože graf mapy obsahoval menší počet vrcholů. Druhá třetina odpovědí obsahovala mapu České republiky, na které si žáci cenili, že ji již znají a přišla jim zábavnější. Čtyři žáci vzhledem k záživnosti úlohy uvedli úlohu s názvem Seznamovací hra, kde pracovali se zasedacím pořádkem. Graf 5 Nejlepší úloha bloku Na závěr žáci mohli zanechat vzkaz. Objevily se zde pozitivní ohlasy, doporučení ohledně mého vyučování a přání zařadit teorii grafů do běžné výuky. Na základě pozorování z výuky a analýzy dotazníku se domnívám, že cíl: „Žák popíše, z kolika hran a vrcholů se graf skládá,“ byl naplněn. Ze sesbíraných odpovědí usuzuji, že se u většiny žáků cíl: „Žák vytvoří graf dle mapy znázorňující EMPIRICKÁ ČÁST 51 oblasti (státy, kraje apod.) a jejich společné hranice,“ nepodařilo zcela naplnit. Žáci mylně zakreslili do grafů hranu navíc nebo jim některé chyběly. Pro lepší výsledky by žáci potřebovali více úloh k procvičení, kde by se objevily i komplikovanější situace, aby se s nimi naučili pracovat a více času při vyplňování dotazníku, aby se vyhnuli omylům z nepozornosti. V testovací úloze žáci řešili úlohu pomocí obarvení vrcholů grafu, proto považuji cíl: „Žák převede zadání úlohy na problém počtu barev obarvení grafu,“ za dosažený. Navzdory chybným grafům žáci obarvili vrcholy většinou korektně, avšak nedocílili nejmenšího počtu barev, proto pokládám cíl: „Žák aplikuje pravidla obarvení vrcholů grafu za účelem vyřešení daných úloh,“ pouze do určité míry za splněný. 2.3 Druhý výukový blok 2.3.1 Příprava na výuku Téma: Hamiltonovský graf, oceněný graf Třída: 7. třída Místo: Velké Němčice Délka vyučovací jednotky: 90 minut (2 × 45 minut) Cíle: Žák vysvětlí pojem hamiltonovská kružnice. Žák nakreslí vlastní příklad grafu, ve kterém nalezne hamiltonovskou kružnici. Pomůcky: vytištěné pracovní listy, křídy/fixy na tabuli, psací potřeby (pero, pastelky/fixy), notebook/stolní počítač, dataprojektor, kalkulačka Napojení na RVP ZV: V rámci vzdělávací oblasti Matematika a její aplikace nacházející se v Rámcovém vzdělávacím programu pro základní vzdělávání je možno výuku zařadit do tematického okruhu Nestandardní aplikační úlohy a problémy. Žáci plánují trasy, řeší běžné problémy, nad kterými je nutno logicky uvažovat. Též je možno výuku začlenit do tematického okruhu Geometrie v rovině a v prostoru. Výuka se zabývá tématem z diskrétní matematiky a pokládá si otázku: „Které dva vrcholy jsou spojeny cestou?“ Zároveň odpověď nezávisí na délce hrany, zaobírá se symetrickou relací mezi vrcholy. V této výuce je rozvíjen algoritmus spojený s geometrickou představivostí. EMPIRICKÁ ČÁST 52 Úvod: 10 min Učitel/ka sdělí plán druhého výukového bloku žákům a požádá žáka/žákyni o rozdání pracovních listů, jež stručně okomentuje. Jeden/jedna z žáků přečte zadání první úlohy nahlas. Učitel/ka se utvrdí, že žáci zadání rozumí, eventuálně instrukce objasní. 1. Úloha: 10 min Zvýrazni cestu po hranách grafu s následujícími specifiky: a)obsahuje všechny vrcholy grafu b)všemi vrcholy projdu pouze jednou c) vrátím se do vrcholu, kde jsem začal/a. Obr. 53 Zadání úlohy – cesta v grafu Žáci se sami zamýšlí nad úlohou a přichází s vlastním řešením, která pak sdílí se zbytkem třídy na tabuli. Poté učitel/ka žákům poví o hamiltonovském grafu, a ještě jednou poprosí o přečtení, co musí splňovat. Vlastní zpracování: V práci jsou uvedena čtyři ilustrativní řešení, počet řešení je více. Množství řešení ovlivní, zda je v zadání startovní vrchol určen či je libovolný. Cesta po hranách grafu je barevně zvýrazněna a hrany jsou očíslovány. EMPIRICKÁ ČÁST 53 Obr. 54 Řešení úlohy – cesta v grafu a) Obr. 55 Řešení úlohy – cesta v grafu b) Obr. 56 Řešení úlohy – cesta v grafu c) Obr. 57 Řešení úlohy – cesta v grafu d) EMPIRICKÁ ČÁST 54 2. Úloha: 15 min Paní učitelka musí každý večer navštívit všechny chatky a zkontrolovat, zda jsou děti v posteli. Naplánuj paní učitelce její trasu tak, aby vyšla ze své chatky a do okolních chatek se podívala pouze jednou, poté se vrátí do své. Obr. 58 B – Plán tábora a) Vytvořit graf dle obrázku B. b) Najdi cestu paní učitelce. Pro rychlíky: Zkus najít více cest (hamiltonovských kružnic). Vyučující nechává žáky tvořit graf dle obrázku. Ujišťuje se, že žáci rozumí zadání, chaty zobrazují vrcholy a cesty hranami. Když mají žáci zkontrolovaný a korektní graf, hledají hamiltonovské kružnice. Specifika dané kružnice mají žáci sepsané v první úloze, ke které se mohou vrátit. Rychlíci jsou pobízeni ke hledání různých cest s využitím rozlišných barev pro přehlednost. EMPIRICKÁ ČÁST 55 Vlastní zpracování Nakreslený graf dle obrázku. Obr. 59 Graf tábora Pět demonstrovaných řešení průchodu grafem. Ke každému průchodu existuje průchod po hranách v opačném směru, takzvaně se sestupným číslováním hran. Obr. 60 Tábor – hamiltonovská kružnice a) Obr. 61 Tábor – hamiltonovská kružnice b) Obr. 62 Tábor– hamiltonovská kružnice c) Obr. 63 Tábor – hamiltonovská kružnice d) Obr. 64 Tábor – hamiltonovská kružnice e) EMPIRICKÁ ČÁST 56 3. Úloha: 10 min Děti jedou na tábor, tudíž musí podat přihlášky. Dobrovolník ze třídy Tomáš se rozhodne, že rozdá přihlášky všem spolužákům domů. Tomáš vyjde ze svého domu a navštíví své spolužáky, načež se vrátí domů, aniž by šel kolem domů svých spolužáků víckrát. Jak by mohla vypadat jeho cesta? Obr. 65 Mapa Velkých Němčic Tuto úlohu žáci provádí přímo v mapě, ve které je třeba se zorientovat. Žáci mají obdobná pravidla, jak v předchozích úlohách, avšak nyní mohou využít i část ulice nikoli celou jako v případě hran grafu. Motivací příkladu je mapa obce, ve které žáci chodí do školy. EMPIRICKÁ ČÁST 57 Vlastní zpracování: Obr. 66 Řešení – mapa Velkých Němčic 4. Úloha: 20 min Z tábora vedou čtyři stezky: do kaple, na hrad, do restaurace a do kostela. Turista, jenž se vydá nejprve do kaple, může poté pokračovat v cestě buď na hrad, nebo se podívat na pomník. Nemusí se rozmýšlet dlouho, protože z hradu se dá dojít i k pomníku. Pokud má člověk žízeň, vede od pomníku cesta ke studánce s pitnou vodou. Ke studánce však lze jít i později od kostela. Ke kostelu vede cesta jak od pomníku, tak od hradu EMPIRICKÁ ČÁST 58 a můžeme od něj dojít do restaurace, která leží nedaleko hradu. Turisti s velkým hladem se mohou vydat do restaurace již z hradu po krátké cestičce. a) Vytvoř graf dle slovního zadání. b) Zvýrazni cestu, pro kterou platí specifika z 1. Úlohy. (hamiltonovská kružnice) c) Zkus najít více hamiltonovských kružnic. Existuje hamiltonovská kružnice, která obsahuje hranu z tábora do kostela? Nyní žáci procvičují práci s textem, tvoří graf dle slovního zadání. Je potřeba žáky upozornit, aby vrcholy kreslili na papír dál od sebe, aby se v grafu později vyznali. Vlastní zpracování a) Nakreslený graf dle slovní úlohy. Obr. 67 Graf stezek b) Následující obrázky znázorňující různé průchody grafem. Obr. 68 Řešení – graf turistická trasa a) Obr. 69 Řešení – graf turistická trasa b) EMPIRICKÁ ČÁST 59 Obr. 70 Řešení – graf turistická trasa c) c) Ano, existuje hamiltonovská kružnice, která obsahuje hranu z tábora do kostela. Obr. 71 Řešení – graf turistická trasa d) EMPIRICKÁ ČÁST 60 d) Jak se situace změní, když chceme, co nejkratší hamiltonovskou kružnici? Tabulka 1 Trasy a jejich délka Trasa: Počet kilometrů: Tábor – kaple 2 km Tábor – hrad 1,8 km Tábor – restaurace 1,1 km Tábor – kostel 2,5 km Kaple – hrad 1,5 km Kaple – pomník 1,65 km Hrad – pomník 1,6 km Hrad – restaurace 0,5 km Hrad – kostel 2,1 km Restaurace – kostel 1,7 km Kostel – studánka 1,3 km Studánka – pomník 1,3 km Pomník – kostel 2 km Vlastní zpracování: Na základě složitosti příkladu viz 12. Příklad:, nelze po žácích vyžadovat nalezení nejkratší hamiltonovské kružnice. Příklad je doporučeno uchopit jako motivační, kdy žáci sdílí své kružnice a jejich délky. Zjišťují, komu se podařilo z objevených kružnic nalézt tu nejkratší. Obr. 72 Oceněný graf – stezky EMPIRICKÁ ČÁST 61 e) Pro zvídavé: Znáš mapové značky míst popsaných ve 4. Úloze? Propoj čárou název místa se symbolem. Pomník Restaurace Kaple Hrad Kostel Obr. 73 Mapové značky28 Příklady pro rychlíky: 15 min Na konci pracovního listu se vyskytují motivační příklady pro rychlíky. Žáci, jimž výuka nečinila potíže, jsou se zadanou prací hotoví, se mohou seznámit s další oblastí teorie grafů. Objevují se zde příklady týkající se nalezení cesty bludištěm a namalování domečku jedním tahem. Nejprve je známá úloha typu jednotažka, zahrnuta v pracovních listech za účelem rozšíření povědomí, co vše do teorie grafů spadá. Namaluj domeček jedním tahem. 28 TRASA, spol. s r.o., obchodní organizace KČT. Turistické mapy Obr. 74 Zadání domečku EMPIRICKÁ ČÁST 62 Vlastní zpracování Obr. 75 Řešení domečku Číselné označení hran znamená pořadí procházení. Domeček lze nakreslit jedním tahem, jelikož je graf souvislý a pouze dva vrcholy jsou stupně lichého, stupeň vrcholu grafu viz 4. Definice:. Tento příklad odkazuje na takzvaný eulerovský graf. Dle Jaroslava Nešetřila je graf G eulerovský, právě tehdy, když je souvislý a současně všechny stupně grafu G jsou sudé. 29 Najdi cestu bludištěm a dostaň se k bubákovi. Již malé děti hledají cesty bludištěm, nyní však lze na úlohu pohlížet z jiného úhlu a pokusit se ji vyřešit pomocí teorie grafů. Pan/paní učitel/ka sdělí žákům, jak souvisí bludiště s teorií grafů. Ukáže žákům, kam umístit v bludišti vrcholy, nakreslí vrcholy na křižovatky cest, na vstup a výstup. Objasní, které vrcholy je možno spojit hranou: „Jestliže se jedná o nejbližší možné křižovatky takové, že z jedné křižovatky lze bludištěm projít na druhou křižovatku nebo východ.“ Upozorní, že vrchol lze umístit 29 NEŠETŘIL, Jaroslav. Teorie grafů, s. 56. Obr. 76 Zadání malé bludiště EMPIRICKÁ ČÁST 63 i na konec slepé cesty. Pokud se podaří spojit oba konce souvislou posloupností hran, tak známe cestu z jednoho konce bludiště na druhý. Vlastní zpracování Najdi cestu bludištěm Obr. 79 Zadání velké bludiště Obr. 77 Graf malého bludiště Obr. 78 Graf malého bludiště EMPIRICKÁ ČÁST 64 Vlastní zpracování Obr. 80 Graf velkého bludiště Obr. 81 Graf – cesta velkým bludištěm Zakončení: 10 min V rámci mé bakalářské práce žáci vyplňují na konci výuky dotazník: 1. Jak ti připadal dnešní program? Obr. 82 Škála hodnot dotazník 2. Která specifika splňuje hamiltonovská kružnice? EMPIRICKÁ ČÁST 65 3. V kterém grafu nalezneme hamiltonovskou kružnici. Zakroužkuj správnou variantu a zvýrazni hamiltonovskou kružnici v grafu. a) Obr. 83 Graf zpětná vazba a) b) Obr. 84 Graf zpětná vazba b) 4. Nakresli vlastní hamiltonovský graf a barevně zvýrazni hamiltonovskou kružnici. 5. Která úloha pro tebe byla nejnáročnější? Uveď alespoň jeden důvod proč. 6. Vzkazy či připomínky ohledně dnešního programu zanechej zde. 2.3.2 Sebereflexe Na začátku druhého výukového bloku si žáci rozdali své jmenovky, a poté jsem žáky seznámila, čemu se budeme v nadcházejících dvou vyučovacích hodinách věnovat. Nejprve jsme si zopakovali, jak mohou grafy vypadat. Několik dobrovolníků namalovalo libovolné grafy na tabuli. Poté jsme se přesunuli k první úloze. Jeden ze žáků přečetl zadání nahlas, a poté žáci sami přicházeli s řešením. První úloha nečinila žákům potíže, rychlejší žáci našli různá řešení, která pak sdíleli na tabuli na promítnutý graf. Domnívala jsem se, že druhá úloha je vhodně zvolená, jelikož k vytvoření grafu žákům pomůže obrázek s rozmístěnými chatkami. Překvapilo mě, že žákům činilo potíže vytvořit graf. Usuzuji, že příčinou potíží byly cesty mezi chatkami, jelikož jsou na obrázku zakroucené a některé se kříží. Bylo zapotřebí obcházet žáky a opakující se chyby vysvětlit u tabule. Například žáci často využili u hran, které se křížily, jen polovinu jedné hrany. Poněvadž se žáci drželi obrázku jako předlohy, bylo snazší EMPIRICKÁ ČÁST 66 najít chybu jak vyučujícím, tak i pro samotné žáky. V této úloze se více projevily rozdíly mezi žáky a úloha pro rychlíky spočívající v nalezení více hamiltonovských kružnic přišla vhod. Žáci si opět ukázali před tabulí svá rozdílná řešení. Protože úvodní část hodiny se kvůli stručnému opakování protáhla a žáci se střídali u tabule, aby ukázali všechny odlišná řešení, jež nalezli, tak již následovala přestávka. Při řešení třetí úlohy žáci pracovali s mapkou, zkoušeli si pomocí různých barev mapku procházet. Najít řešení, netrvalo žákům moc dlouho. Komplikovanější úsek úlohy byl ve spodní části mapy týkající se vrcholů na ulici Dolní a U Potoka. Když se žákům, kteří vyžadovali poradit, se spodní částí pomohlo, tak zbylou procházku našli za chvilku. Čtvrtá úloha byla pro žáky dle mého pozorování náročná. Na vyřešení jsem je navedla představením první věty a jejího zakreslení. Žáci museli dávat pozor, jak zadání přesně zní. Při obcházení žáků je pro učitele přínosné mít u sebe vlastní řešení, ve kterém jsou u vrcholů napsané jejich stupně. Uspíšilo by to pomoc vytvořit graf. Navzdory upozornění, aby žáci kreslili vrcholy dál od sebe, aby byl graf přehledný, jich mnoho kreslilo graf malý s nedostatkem místa na popisky. Pro příště je zapotřebí upozornění více zdůraznit a nejlépe ho doplnit ukázkou na tabuli. Najít cestu v již vytvořeném grafu zvládli žáci dobře. Někteří hledali i více cest, o které se podělili se spolužáky. Hledání nejkratší cesty jsem pojala se žáky trochu jako hru, všichni si sečetli své cesty na kalkulačkách a hlásili své výpočty a čekali, kdo bude mít nejméně. Časový harmonogram se dařilo dodržet lépe než v prvním výukovém bloku. Tentokrát bylo připraveno méně úloh, které se podařilo všechny se žáky vyřešit. Na konci pracovních listů se nacházely úlohy navíc pro rychlíky, které si bystřejší žáci během výuky vyplnili a někteří si je dobrovolně splnili o přestávce. EMPIRICKÁ ČÁST 67 2.3.3 Analýza dotazníku Nejprve žáci odpovídali, zda se jim výukový blok zdál zábavný či nudný, jednoduchý či složitý. Dva žáci se vyjádřili ohledně záživnosti výuky neutrálně, zbytek třídy se přiklonil k postoji, že byla výuka zábavná, z toho šest žáků s tímto postojem souhlasí velmi a tři žáci naprosto. Graf 6 Poutavost druhé výuky Pro dvanáct žáků byla výuka jednoduchá (včetně velmi a naprosto jednoduchá), jeden žák se vyjádřil nestranně a pro dva žáky byl výukový blok složitý. Graf 7 Obtížnost druhé výuky Dále žáci odpovídali, kterými specifiky se vyznačuje hamiltonovská kružnice. Kromě jednoho člověka všichni aspoň jedno specifikum uvedli. Více jak jedna třetina žáků správně sepsala všechny tři kritéria. Zbytku třídy chybělo jedno či dvě kritéria. Nedostatky odpovědí zřejmě neplynuly z nevědomosti či neporozumění grafů, EMPIRICKÁ ČÁST 68 ale ze snahy odpovědět vlastními slovy, tudíž se přesná specifika z odpovědí vytrácela. Zda žáci rozumí, která specifika hamiltonovská kružnice nese je vidno i z následujících dvou otázek. Graf 8 Specifika hamiltonovské kružnice Odpovědí žáků si cením, jelikož žáci mohli jít lehčí cestou a jen specifika opsat z pracovních listů. Takhle se nad úlohou zamysleli a použili vlastní slova k popsání předtím neznámého pojmu. V odpovědích zazněli například výrazy: „Objet všechny vrcholy, nemůžeme se vracet do vrcholů, musím se vrátit odkud jsem přišel, spojit všechny vrcholy, nevracet se a dojít zpátky na start.“ Jeden příklad byl vyřešen nakreslením grafu, v kterém lze najít hamiltonovskou kružnici. Z této odpovědi usuzuji, že je třeba upravit zadání, aby bylo více explicitní. Příklad upraveného zadání: „Vyjmenuj, která specifika splňuje hamiltonovská kružnice.“ Ve třetí otázce žáci kroužkovali, ve kterém grafu z nabídnutých nalezneme hamiltonovskou kružnici a tu zvýraznili. Všichni žáci správně určili graf, osm žáků kružnici nevyznačilo, sedm ano. Čtyři ze sedmi vyznačených kružnic byly korektní. Vzhledem k odpovědím v předchozí otázce a současně nakresleným vlastním grafům v otázce následující, se domnívám, že si žáci nedočetli zadání, a proto kružnici EMPIRICKÁ ČÁST 69 nevyznačili. Často se objevovaly dotazníky s kreativními grafy včetně zvýrazněných kružnic ve čtvrté otázce, a přesto ve třetí otázce kružnice zvýrazněny nebyly. Graf 9 Vyznačení hamiltonovské kružnice V následující úloze žáci vymýšleli vlastní grafy se zvýrazněnou hamiltonovskou kružnicí, což dvanáct žáků zvládlo, v jednom grafu hamiltonovská kružnice nebyla zvýrazněna a dva grafy byly chybné, v nich kružnici nelze nalézt. Graf 10 Vlastní graf s hamiltonovskou kružnicí V páté otázce žáci odpovídali, která úloha pro ně byla nejnáročnější. Pro šest z patnácti žáků byla nejnáročnější úloha čtvrtá týkající se tvoření grafu dle slovního popisu s následným hledáním hamiltonovské kružnice. Dle žáků obtížnost úlohy spočívala v náročné práci s textem a složitém grafu, v kterém bylo po sléze komplikované se vyznat. Dále se v odpovědích objevovala druhá úloha, která byla EMPIRICKÁ ČÁST 70 podle žáků komplikovaná velkým množstvím cest. Zmíněna byla i první úloha, která byla obtížná, poněvadž byla nová a pro žáky prvním seznámením s hamiltonovským grafem. Graf 11 Nejnáročnější úloha bloku Ve vzkazech od žáků se objevilo kladné hodnocení a porovnání s minulým výukovým blokem. Šest lidí ocenilo více druhý než první výukový blok. Jeden člověk ohodnotil první výukový blok lépe. Na základě analýzy dotazníků soudím, že většina žáků vysvětlí hamiltonovskou kružnici, a proto tento cíl hodnotím za splněný. Cíl: „Žák nakreslí vlastní příklad grafu, ve kterém nalezne hamiltonovskou kružnici,“ byl též do značné míry naplněn. ZÁVĚR 71 Závěr Vzhledem k cíli bakalářské práce byla sepsána příprava na výuku zabývající se tématem teorie grafů určená pro žáky na druhém stupni základní školy. Učení žáků proběhlo ve dvou výukových blocích, jež se týkaly obarvení vrcholů grafů a hamiltonovského grafu. Zpětná vazba od žáků byla sesbírána formou dotazníku. Cíle prvního výukového bloku se podařilo do určité míry naplnit všechny, některé více než jiné. Při tvorbě grafů dle map byla zjištěna potřeba většího množství obdobných příkladů obtížnější úrovně. Žáci postupují při tvorbě grafu korektně, avšak v komplikovanějších částech mapy si neví rady. Obarvení vrcholů grafu činilo žákům potíže. Základy obarvování si žáci osvojili, avšak dospět k nejmenšímu počtu barev se většině nepodařilo. Pomohlo by procvičování s větším důrazem na postupné barvení, především upřednostňování společných sousedů a používání barev, jež už jednou použili. Pokud by učitel plánoval daný výukový blok provést, domnívám se, že by bylo přínosné nechat žáky, aby si graf zpětně prošli a zkusili si chyby najít sami. Všechny připravené příklady prvního výukového bloku nebyly s žáky z časových důvodů provedeny. Pro budoucí realizaci bych doporučila buď dopředu snížit počet úloh s ohledem na dodržení cílů výuky, nebo snížit náročnost výsledných grafů. Vzhledem k mé zkušenosti navrhuji čtyři až pět úloh na jeden výukový blok a mít připravené úlohy či části úloh pro rychlíky. Ve druhém výukovém bloku byly cíle výuky naplněny. Žáci vysvětlili hamiltonovskou kružnici a nakreslili vlastní příklad grafu, který tuto kružnici obsahuje. S ohledem na výsledky dotazníku a mou reflexi navrhuji prohození pořadí druhé a třetí úlohy. Třetí úlohu řešili žáci za pomocí mapy bez grafu a hledání bylo jednodušší, jelikož mohli využít i části ulic. Jednalo se o modifikovanou úlohu hamiltonovské kružnice. Druhá úloha se ukázala pro žáky složitější, poněvadž žáci byli povinni využívat v grafu již celé hrany a některé se křížily. Oba výukové bloky byly vykonány v rámci jednoho týdne, což se ukázalo během stručného opakování v druhém bloku jako příznivé. Žáci měli do jisté míry znalosti z minule uchovány v paměti. Zároveň je nutno dodat, že výzkum má jistá omezení. Vzorkem výzkumu byla jedna třída, pro relevantnější výsledky by byla nutná větší velikost vzorku. Též by bylo ZÁVĚR 72 přínosné provést výuku ve starších ročnících a porovnat výsledky mladších a starších žáků. První část práce je teoretická, obsahuje souhrn základních definic. Čtenář se kupříkladu dozví, jak na graf nahlížíme, co znamená komponenta grafu či grafová souvislost. Přirozeně je zde kapitola i o hamiltonovském grafu a obarvování vrcholů grafů. Předložená teorie může posloužit ke studiu učitelům, kteří by zamýšleli vyučování na téma teorie grafů s žáky provést. Celková odezva na výuku byla od žáků příznivá, jak ve vzkazech nacházejících se v dotaznících či osobně po hodině. Jejich běžné učení bylo zpestřeno o novou matematickou disciplínu a žáci si rozšířili své matematické znalosti. POUŽITÉ ZDROJE 73 Použité zdroje CIENCIALA, Luděk a Lucie CIENCIALOVÁ. Teorie grafů a grafové algoritmy. Opava: Ústav informatiky, Výzkumný ústav Centra excelence IT4Innovations, Filozofickopřírodovědecká fakulta v Opavě, Slezská univerzita v Opavě, 2014. ISBN 978-80-7510-060-3. DEMEL, Jiří. Grafy a jejich aplikace. Praha: Academia, 2002. ISBN 80-200-0990-6. FUCHS, Eduard. Práce z teorie grafů. In: TŘEŠŇÁK, Zdeněk; Petra ŠARMANOVÁ a Bedřich PŮŽA. Otakar Borůvka. Brno: Nadace Universitas Masarykiana, 1996, s. 173–175, ISBN 80-902004-0-0. Dostupné z Czech Digital Mathematics Library: https://dml.cz/handle/10338.dmlcz/401300. [citováno 2023-07-04]. MŠMT. Rámcový vzdělávací program pro základní vzdělávání. Online. Ministerstvo školství, mládeže a tělovýchovy, 2023. Dostupné z: https://www.edu.cz/rvp-ramcove- vzdelavaci-programy/ramcovy-vzdelavacici-program-pro-zakladni-vzdelavani-rvpzv/. [citováno 2024-02-20]. NEŠETŘIL, Jaroslav. Teorie grafů. 1. vyd. Praha: SNTL – Státní nakladatelství technické literatury, 1979. PAIVA, Henrique Mohallem; Priscila Falcão dos SANTOS; Marcos Ricardo Omena de Albuquerque MÁXIMO a Lucas NIEMEYER. Efficient Lecturer Peer-Assessment Attribution Using Graph Theory and a Novel Greedy Algorithm. Online. IEEE Access, vol. 12, January 2024, s. 14742–14750. Dostupné z: https://doi.org/10.1109/ACCESS.2024.3358613. [citováno 2024-03-01]. PŘÍHONSKÁ, Jana. Kombinatorické problémy: aplikace a metody řešení. Kombinovaná studia pro učitele. Liberec: Technická univerzita v Liberci, 2014. ISBN 978-80-7494-017-0. POUŽITÉ ZDROJE 74 ŠIŠMA, Pavel. Vznik a vývoj teorie grafů. Pokroky matematiky, fyziky a astronomie. Praha: Jednota českých matematiků a fyziků, roč. 43 (1998), č. 2, s. 89–99. ISSN 0032-2423. TRASA, spol. s r.o., obchodní organizace KČT [Klub českých turistů]. Turistické mapy. Online. Dostupné z: http://www.trasa.cz/#xl_uvod. [citováno 2023-11-01]. VAN LINT, Jacobus Hendricus a Richard Michael WILSON. A Course in Combinatorics. Cambridge University Press, 2001. ISBN 0521006015. ZELINKA, Bohdan. Rovinné grafy. Online. Škola mladých matematiků, 41. Praha: Mladá fronta, 1977. Dostupné z Czech Digital Mathematics Library: https://dml.cz/handle/10338.dmlcz/403901. [citováno 2023-07-06]. PŘÍLOHA A: PRACOVNÍ LIST – PRVNÍ VÝUKOVÝ BLOK 75 Příloha A: Pracovní list – první výukový blok PŘÍLOHA A: PRACOVNÍ LIST – PRVNÍ VÝUKOVÝ BLOK 76 PŘÍLOHA A: PRACOVNÍ LIST – PRVNÍ VÝUKOVÝ BLOK 77 PŘÍLOHA A: PRACOVNÍ LIST – PRVNÍ VÝUKOVÝ BLOK 78 PŘÍLOHA B: PRACOVNÍ LIST – DRUHÝ VÝUKOVÝ BLOK 79 Příloha B: Pracovní list – druhý výukový blok PŘÍLOHA B: PRACOVNÍ LIST – DRUHÝ VÝUKOVÝ BLOK 80 PŘÍLOHA B: PRACOVNÍ LIST – DRUHÝ VÝUKOVÝ BLOK 81 PŘÍLOHA B: PRACOVNÍ LIST – DRUHÝ VÝUKOVÝ BLOK 82 PŘÍLOHA B: PRACOVNÍ LIST – DRUHÝ VÝUKOVÝ BLOK 83 PŘÍLOHA B: PRACOVNÍ LIST – DRUHÝ VÝUKOVÝ BLOK 84 PŘÍLOHA C: VZOREK SESBÍRANÝCH DOTAZNÍKŮ 85 Příloha C: Vzorek sesbíraných dotazníků PŘÍLOHA C: VZOREK SESBÍRANÝCH DOTAZNÍKŮ 86 PŘÍLOHA C: VZOREK SESBÍRANÝCH DOTAZNÍKŮ 87 PŘÍLOHA C: VZOREK SESBÍRANÝCH DOTAZNÍKŮ 88