Základní pojmy teorie grafů a jejich možnosti ve využití na 1. stupni ZŠ Růžena Blažková 1. Připomeňte si, kde jste se setkali s pojmem „graf“ Grafy binárních relací – např. uzlový, kartézský Př. 1. Je dána množina M = . Znázorněte graficky (např. pomocí uzlového grafu) vztah „číslo x je násobkem čísla y“. Grafy funkcí - grafem funkce f ve zvolené souřadné soustavě Oxy v rovině rozumíme množinu všech bodů X o souřadnicích . Dvě přímky – osy volíme tak, aby byly navzájem kolmé a jejich průsečík O nazýváme počátek souřadné soustavy. Na prvním stupni ZŠ se setkáme s . Grafem přímé úměrnosti je přímka procházející počátkem souřadné soustavy, nebo část této přímky. V případě, že definičním oborem funkce je množina všech přirozených čísel, potom grafem funkce je množina izolovaných bodů, které leží v přímce. Př. 2. Za jednu tyčinku zaplatíme 9 Kč. Znázorněte graficky, kolik Kč zaplatíme za 2, 3, 4, 5, 6 tyčinek (pozor – nemůžeme koupit polovinu tyčinky ani jinou její část). Př. 3. Jonáš jede na kole průměrnou rychlostí 12 kilometrů za 1 hodinu. Znázorněte graficky, kolik kilometrů ujede za 2, 3, 4 hodiny. Setkáváme se i s nepřímou úměrností – grafem funkce nepřímá úměrnost je hyperbola. Př. 4. Znázorněte graficky, jak závisí šířka obdélníku na jeho délce při konstantním obsahu. S = a · b, b = S : a, volte např. S = 48 cm^2. Kdybychom chtěli znázornit závislost obsahu čtverce na délce jeho strany, potom se setkáváme s kvadratickou funkcí. Jejím grafem je parabola. Diagramy – setkáváme se s nimi ve statistice, ke znázorňování statistických údajů. Diagram poskytuje vizuálně více informací než např. tabulka. Pod pojmem diagram rozumíme schématické znázornění závislost dvou nebo více veličin. Typy diagramů, které se často používají: Diagram obrázkový Diagram sloupkový – histogram Diagram úsečkový Diagram spojnicový - polygon četností Diagram kruhový Všechny typy diagramů mohou být znázorněny i prostorově, např. pomocí kvádrů, válců. Příkladem mohou být diagramy znázorňované v televizi při sledování výsledků voleb. Př. 5. Vyhledejte příklady jednotlivých typů diagramů v denním tisku nebo v časopisech. Teorie grafů Teorie grafů patří mezi novější obory moderní matematiky, tvoří samostatnou část diskrétní matematiky. Má velké uplatnění v mnoha dalších oborech nejen matematiky, ale také fyziky, chemie, biologii, ekonomiky, výpočetní techniky aj. Je možné ji využívat i ve školské matematice od 1. stupně základní školy, kdy pomocí grafů můžeme řešit mnoho úloh běžné školské matematiky, a to zajímavým způsobem. Uveďme nejprve několik základních pojmů. Poznamenejme, že pro naše potřeby neuvádíme výstavbu teorie grafů s příslušnými definicemi, ale pojmy přibližujeme. Mějme libovolnou neprázdnou množinu U a množinu K všech jejích dvouprvkových podmnožin. Libovolnou podmnožinu množiny K označíme H. Uspořádanou dvojici nazýváme neorientovaný graf. Prvky množiny U nazýváme uzly, prvky množiny H nazýváme hrany. Tedy: Neorientovaným grafem nazýváme množinu, která obsahuje prvky dvojího druhu: první z nich jsou uzly, druhé z nich jsou hrany, které uzly spojují. Přitom předpokládáme, že každá hrana spojuje nejvýše dva uzly. Pokud hrana spojuje uzly A, B, říkáme že, hrana je s těmito vrcholy incidentní. Množina U může být konečná, nebo nekonečná, potom graf je konečný nebo nekonečný. Pro naše úvahy budeme používat grafy konečné. Úplný graf je takový graf, ve kterém jsou každé dva uzly spojené hranou. o o o o o Stupeň uzlu určuje počet hran, které s tímto uzlem incidují. Označuje se st x Pravidelný graf k-tého stupně je graf, jestliže st x = k (z každého uzlu vychází stejný počet hran). Na obrázku je pravidelný graf stupně 4. Důležitými pojmy jsou pojmy sled, tah a cesta, dále pak kružnice a strom. Sled: Máme graf s uzly x[0] x[1,] x[2] , … x[n]. Posloupnost uzlů a hran x[0], x[0] x[1, ]x[1, ]x[1] x[2], …… x[n-1]x[n], x[n] se nazývá sled začínající v uzlu x[0] a končící v uzlu x[n]. Počet hran ve sledu se nazývá délka sledu. Tah: tah je sled, ve kterém se neopakuje žádná hrana. Jestliže je počáteční uzel roven uzlu koncovému, pak se tah nazývá uzavřený ( x[0] = x[n]). V opačném případě se tah nazývá otevřený. Cesta je sled, ve kterém se neopakuje žádný uzel. Každá cesta je tahem, avšak každý tah nemusí být cestou. Jestliže mezi dvěma uzly grafu existuje sled, pak v daném grafu existuje alespoň jedna cesta. Graf, v němž mezi každými dvěma uzly existuje sled, se nazývá souvislý graf. Konečný souvislý pravidelný graf 2. stupně se nazývá kružnice. Počet uzlů kružnice se nazývá její délkou. Strom je souvislý graf, který neobsahuje žádnou kružnici. Grafy mohou být neorientované, nebo orientované. Hrana grafu je orientovaná, jestliže je dáno pravidlo, který uzel je počáteční a který koncový (je dána orientace hrany určená zpravidla šipkou). Orientovaný graf je graf, jehož všechny hrany jsou orientované. Grafy mohou být neohodnocené nebo ohodnocené. Ohodnocené mohou být jejich hrany nebo jejich uzly. Hranově ohodnocený graf je graf, ve kterém je jeho hranám přiřazeno některé reálné číslo. Uzlově ohodnocený graf je graf, ve které je jeho uzlům přiřazeno některé reálné číslo. Náměty k využití ve školské matematice Hranově ohodnocené grafy slouží k procvičování sčítání několika čísel, porovnávání čísel, hledání nejmenšího čísla apod. Např. Pan Hruška rozváží každý den pečivo z pekárny P do několika prodejen. Plánek míst prodejen je na obrázku a vzdálenosti míst, která jsou spojena cestou jsou: PA 7 km, AB 5 km, BE 6 km, AC 3 km, BD 6 km, DC 2 km, CE 5 km, PE 8 km, ED 4 km. Nakreslete graf a navrhněte, jak má jezdit, aby ujel co nejmenší počet kilometrů. E o o D o C P o o B A o Př. 6. Nakreslete obrázek grafu podle zadání a vypočítejte nejkratší vzdálenost tak, aby pan Hruška vyjel z pekárny, projel každé místo právě jednou a vrátil se do pekárny. Poznámka: pro vyšší ročníky můžeme volit větší čísla, případně použít automapu. V pátém ročníku lze využít i čísel desetinných. Stromy můžeme využít k řešení různých slovních úloh, ke klasifikaci pojmů, k vytváření genetických stromů, k řešení kombinatorických úloh apod. Stromem je např. každý řetězec, kdy žáci provádějí postupně s čísly operace a postupují od počátečního uzlu ke koncovému, nebo naopak. Mohou být znázorněny v poloze svislé, vodorovné, i jinak. Např. Myslím si číslo. Když ho vynásobím osmi, přičtu 6 a odečtu 20, dostanu 50. Které číslo si myslím? ? · 8 + 6 - 20 50 Slovní úloha: Kolik je všech žáků ve třídě, jestliže víme, že španělštinu studuje 15 žáků, francouzštinu 18 žáků, oba jazyky studuje 8 žáků, každý žák třídy studuje některý z těchto jazyků. Všichni žáci třídy studují angličtinu. Řešení pomocí stromu: 8 10 7 0 o o o o ano ne ano ne španělština o o 15 ano ne 18 o francouzština V horní části stromu znázorníme žáky, kteří studují oba jazyky – větev vlevo – je jich 8. Pak na žáky, kteří studují francouzštinu a nestudují španělštinu zbývá 10, na žáky, kteří studují španělštinu a nestudují francouzštinu zbývá 7. Celkem je ve třídě 25 žáků. Úlohy kombinatorické Kolik různých trojciferných čísel můžeme zapsat pomocí číslic 3, 5, 8 tak, aby se a) Číslice v zápisu čísla neopakovaly. b) Číslice se v zápisu čísla mohou opakovat. a) Řešení pomocí stromu: jednotky 8 5 8 3 5 3 o o o o o o desítky 5 o o 8 3 o o 8 3 o o 5 stovky 3 o 5 o 8 o o Čísla čteme po jednotlivých větvích stromu: 358, 385, 538, 583, 835, 853. Strom je možné nakreslit i vodorovně. b) V případě, že se číslice v zápisu čísla opakují, budou z každého uzlu vycházet tři větve, čísel bude 27. Př. 7. Nakreslete strom pro úlohu b) Stromy genetické: Část rodokmenu Lucemburků: JAN LUCEMBURSKÝ KAREL IV Přemysl Otakar Jan Jindřich Václav Lucemburský Lucemburský Prokop Jan Soběslav Jošt Václav Václav IV. Zikmund Jan Karel Jindřich Př. 8. Nakreslete genetický strom vaší rodiny. Stromy klasifikační Klasifikační stromy je vhodné použít k třídění - klasifikaci pojmů. Klasifikovat můžeme trojúhelníky, čtyřúhelníky, číselné obory, rovnice, vzájemné polohy útvarů (např. rovin, přímek v prostoru), sítě krychle, sítě osmistěnu, apod. Uvedeme příklad klasifikace geometrických zobrazení v rovině. translace rotace stejnolehlost podobná nestejnolehlá přímo nepřímo shodná shodná podobná neshodná nepodobná shodná neshodná zobrazení zobrazení zobrazení roviny na sebe Stromy kódovací Znáte Morseovu abecedu? Všechna písmena a číslice můžeme znázornit pomocí kódovacího stromu. Část stromu znázorníme: ●●● S o ●●▬ Uo o R●▬● o W ●▬ ▬ ●● I o ●▬ A o o N▬● o M ▬ ▬ ● E o o T ▬ o Př. 8. Doplňte kódovací strom Morseovy abecedy. Stromy rozhodovací Rozhodovací stromy můžeme využít k řešení bludišť. Jedotažky Pokuste se nakreslit obrázky jedním tahem, aniž byste zvedli tužku od papíru. 1 2 3 4 Proč je možné některé obrázky jedním tahem nakreslit a jiné ne? Tento problém řešil již v roce 1736 Leonard Euler, když řešil úlohu o sedmi mostech města Královce (Koniksberg, Kaliningrad). Městem teče řeka Pergel, v této řece jsou dva ostrovy a jsou propojeny mezi sebou a pevninou celkem sedmi mosty. Euler řešil úlohu, zda je možné vyjít z jednoho místa, projít po každém mostě právě jednou a skončit procházku ve výchozím bodě. Tato úloha nemá řešení. Úloha „nakreslit obrázek (graf) jedním tahem“ je úlohou, ve které máme najít v grafu tah, který obsahuje všechny hrany tohoto grafu. K řešení úloh tohoto typu je vhodné uvést, co je tzv. eulerovský tah. Eulerovský tah je tah, který obsahuje všechny hrany daného grafu. Jestliže máme dán konečný souvislý graf, pak v tomto grafu existuje: a) Uzavřený eulerovský tah právě tehdy, když všechny uzly jsou sudého stupně. Tah začíná i končí v jednom uzlu, který je možné volit libovolně. b) Otevřený eulerovský tah právě tehdy, když jsou v grafu právě dva uzly lichého stupně. Tah začíná v jednom uzlu stupně lichého a končí v druhém uzlu stupně lichého. K tomu, abychom zjistili, zda je možné nakreslit obrázek jedním tahem stačí, abychom zjistili stupně jednotlivých uzlů. První a čtvrtý obrázek obsahují právě dva uzly lichého stupně, je možné je nakreslit jedním tahem. Druhý obrázek obsahuje 4 uzly stupně 5, není možné jej nakreslit jedním tahem. Ve třetím obrázku jsou všechny uzly stupně sudého, je možné nakreslit jej jedním tahem. Př. 9. Hledejte další příklady, kdy můžete využít teorie grafů v učivu matematiky 1. stupně ZŠ. Závěr: Obrázek je za tisíc slov.