Page 99 - vol1

igazán jó algoritmus. Léteznek ellenben szükséges illetve elégséges feltételt
megadó tételek. Ilyenek például a következők:

SZÜKSÉGES feltétel Hamilton-kör létezésére

Tétel: Ha egy gráfban k pontot elhagyva k-nál több komponens keletkezik,
akkor nem tartalmazhat Hamilton-kört.
ELÉGSÉGES feltétel Hamilton-kör létezésére

Dirac tétele: Ha egy n csúcsú egyszerű gráfban minden csúcs fokszáma
LEGALÁBB n/2, akkor a gráf tartalmaz Hamilton kört (és tehát Hamilton- utat is)

Gyakorlati szempontból ellenben ezek csak korlátozott mértékben
segítenek megrajzolni a Hamilton utakat.

Amit az okostelefonokon és tabletteken megvalósíthatunk
Az alkalmazás amit itt használtam, amolyan kakukktojásként jelent meg a
kereséseimben, ugyanis a Play Áruház keresőjébe beírtam, hogy One touch
Erase block. A megjelenő játékfelületen a gráfok csúcsai színes kis négyzetek, az
élei pedig színes vonalak, de a színeknek ezúttal nincsen semmi szerepük. A játék
célja az, hogy egy adott csúcsból kiindulva, az éleken haladva, menjünk át a gráf
minden csúcsán. Ez tulajdonképpen egy Hamilton út keresését jelenti. A játék
úgy van megszerkesztve, hogy amint egy csúcson áthaladunk, az lehull az
ábráról. Természetesen nem kell minden élen áthaladnunk, hiszen nem Euler
útról van szó, hanem minden csúcson pontosan egyszer kell áthaladnunk.
Amennyiben egy próbálkozásunk kudarcot vallott, a játék visszaáll az eredeti
helyzetbe, és újra lehet kezdeni. A játék tehát gyakorlatilag lehetővé teszi egy
gráfban egy Hamilton út megkeresését. Ezúttal is több pálya van, és
természetesen a nehézségi szintek is változnak, és főleg az jelenti a nehézséget,
hogy indulásból nem lehet tudni, hogy mely csúcsból induljunk el és, hogy mely
éleket nem kell használni a csúcsok bejárásánál. Éppen ezért is a játék egyben
kellemes és hasznos, tanulságos időtöltés.
Végezetül megjegyeznénk, hogy nem csupán ezen három témakör
tanítása során tudjuk sikerrel használni az okostelefonokat és tabletteket,
ugyanis a Play Áruházban a játékok között számos oktatóprogram létezik, csak
jól kell tudni keresgélni, és sok más jellegű programra akadunk. Ezek közül
megemlítjük például a determináns számoló programokat, a mátrixokkal
kapcsolatos programokat, egyenletrendszerek megoldására szolgáló

99