Bingó - gráfok

13.      fogás

   BINGÓ    -   GRÁFOK

 A fogalmakat megtanító óra végére vagy a következő  óra elejére

1. A témához tartozó 12 fogalmat, kulcsszót a táblára felír a tanár.
2. A gyerekek a 3x3-as táblázatot rajzolnak, s  véletlenszerűen a 12-ből 9 fogalmat beírnak
3. A tanár a fogalmak DEFINÍCIÓját találomra kiválasztott sorrendben olvassa fel.
4. A diákok figyelik a lapjukon levő kifejezéseket, s áthúzzák azt, amelyiknek a definícióját hallották. Aki 3 egymás mellettit egy sorban vagy oszlopban vagy átlósan áthúzott, kiáltson fel, hogy „Bingó!”.
5. Jutalom érte egy beadható szorgalmi – jutalmazható – példa.
6. Akinek bingója van, olvassa fel a kulcssavakat, s mondja a jelentésüket! A többiek elmondhatják a véleményüket, hogy helyesen mondta-e a definíciókat a társuk.
7. Eztán folytassák  a fogalmak felolvasását – keresését a teljes kitöltésig.

Fogalmak: 

Euler séta	él	fokszám	út
Egyszerű gráf	összefüggő gráf	Izomorf gráfok	hurokél
Fa gráf	n - pontú  teljes gráf	Fokszám	gráf

Definíciók sorban :

- Hurokél: Az (x ; x ) alakú éleket, azaz melyek kezdő- és végpontja egybeesik.

- Fa gráf:  összefüggő, kör nélküli gráf.

 -  Összefüggő gráf gráf, amelynek tetszőleges két pontja közt találunk utat.

- Fokszámok : Egy csúcsra illeszkedő élek száma.

-Euler-séta  : a gráf éleinek olyan bejárása, amely minden élen pontosan egyszer halad át.
- Gráf : Véges sok adott pont közül egyeseket vonallal összekötünk.

- Egyszerű gráf  : gráf, amelyben nincs benne sem hurok, sem többszörös él.

-Út : Élek olyan egymáshoz csatlakozó sorozata, melyben sem él, sem pont nem fordulhat elő egynél többször.

 -Él : csúcsokat összekötő, (nem feltétlenül egyenes) vonal.

- Egyszerű gráf : Azok a gráfok, amelyekben nincsen hurokél és nincsen párhuzamos él.

- n pontú teljes gráf:   Ha egy gráfnak n pontja van [n pozitív egész szám], és mindegyik pontból pontosan egy él vezet a többi ponthoz.

 - Izomorf gráfok: Két, vagy több  gráf,amelyben az élek ugyanazokat a kapcsolatokat jelölik.

Ízelítő a jutalomfeladatokból  : 

Poirot nyomoz…

Egy vacsorán pisztolylövés dördült. Az ebédlőben 12-en voltak és mindenki pontosan hat másikat ismert. A rendőrök azt kérik, hogy egy ember jelölje meg egy listán az ismerőseit. Miután az első ember által megjelöltek is megjelölik ismerőseiket, egy név jelöletlen maradt. Lehetséges ez?

Segítség

Hány embert ismerhet az, akit nem jelöltek meg?

Megoldás

Rajzolással gyanússá válik, hogy lehetetlenség. A bizonyításhoz érdemes feltenni, hogy lehetséges.
Ekkor van egy ember, akit nem jelöltek meg heten, tehát ő a 12 fős társaságból hét embert nem ismer. Ekkor viszont mindössze négy embert ismerhet (saját magán kívül), ám a feladat feltételei szerint neki is hat ismerőse van. Ezek szerint a feltevéseink, hogy lehetséges esetről szól a beszámoló, ellentmondásra vezettek, azaz nem lehetett igaz. Ezzel bebizonyítottuk, hogy nem lehetséges a feladatban leírt eset.

Utazó ügynök probléma

Feladat: egy titkosügynöknek egy listán lévő összes várost be kell járnia, s miután küldetését teljesítette, vissza kell térnie a kiindulási városba.

Az utaknak költsége van. Probléma: olcsó körút, rövid körút. Tervezzük meg ezeket.

Egy lehetséges megoldás, ha felsoroljuk az összes lehetséges esetet, s kiszámoljuk a legrövidebbet, legolcsóbbat. "n" darab város esetén ez azonban n! (n faktoriális). Ha "n" nő, akkor n! nagyon gyorsan nő! Pl. 50 város esetén ez az érték olyan nagy, hogy gyakorlatilag megoldhatatlan. Ez egy tipikus mesterséges intelligencia probléma.
Általában jó megoldást szoktunk keresni, nem optimálisat.

A gráfelmélet himnusza     1. Állott hét híd a Pregel folyóján, akkortájt ez nem csekélység volt ám; Königsbergben büszke sok tanácsos, ennyi híddal hogy ékes a város.     2. Alkonyatkor kavarog a népség, és fejükben hánytorog a kétség: hogy' lehetne jó utat találni, minden hídon egyszer általjárni.     3. Mind a hét híd egyszer essen útba, séta végén otthon lenni újra; de a jó út valahol hibázik, egy híd mindig fölös vagy hiányzik.     Refrén: Euleri gráf: minden foka páros, és a tétel mindörökre áll most; gráfokról ez állítás a világnak ősforrás.     4. Él egy ember, gondoljunk csak rája, itt minálunk, nincs tudásban párja; úgy érti a számolást és mérést, hogy elébe kell tárni a kérdést.     5. Euler mester fejét búsan rázza: "Oly talány ez, nincsen megoldása; nincs oly út, mint uraságtok kérik, amely minden hidat egyszer érint.     Refrén: Euleri gráf: ...     6. Érckemény a tudományos tétel, mit sem kezdhet ellene a kétely; árad a víz, szilárd a híd rajta, még erősb a tudomány hatalma."     7. Háború jött a Pregel folyóra, minden hídját ízzé-porrá szórta; nemzedékek hosszú során fénylik Euler és a folyó neve végig.     Refrén: Euleri gráf: ...     8. Euler híre nem ér addig véget, míg csak élni fog a gráfelmélet; s egyik évre amint jön a másik, az elmélet mind jobban virágzik.     9. Jó kollégák, töltsük meg a kelyhet, Áldomásra mind emeljük feljebb: nekünk a gráfelmélet oly drága, hadd teremjen sok-sok szép virága!