Page 98 - vol1

a megfelelő pontok mindkét gráfban vagy össze vannak kötve, illetve
mindkettőben nincsenek éllel összekötve.

Amit az okostelefonokon és tabletteken megvalósíthatunk

Az okostelefonon vagy a tabletten menjünk be a Play Áruházba és ott a keresőbe
írjuk be, hogy untangle ami kibogozást jelent. A keresés után sok találatunk van.
Ezek mind olyan alkalmazások (játékok) amelyeknél adott egy gráf,
amely általában nem síkgráf, vagyis az élei metszik egymást. A játék célja az,
hogy „kibogozzuk” ezt, vagyis úgy csúsztassuk el a gráf csúcsait, hogy egy
síkgráfot kapjunk, vagyis egy olyan gráfot, amiben nincs két egymást metsző él.
Több ilyen gráf is kapható, és ezek az eredetivel izomorf gráfok. Mi sem jobb
alkalmazás az egymással izomorf gráfoknak a gyakorlati megalkotására, mint
ezek az alkalmazások. És eközben szórakoztatóak és tanulságosak is egyben,
nem csupán a száraz elmélettel találkozunk. Az előbbi játékokban általában az
„összebogozódott élek” tehát azok amelyek metszik egymást, más színnel
(rendszerint pirossal) szerepelnek, azok amelyek nem metszik egymást, zölddel.
Miután egy élet olyan helyzetbe hoztunk, hogy nem metszik egymást, átvált a
színe zöldre. Így ez a színegyezmény is könnyebbé teszi a játékot.

A talált játékok között vannak amelyek síkban zajlanak le, de vannak
amelyek térben. Érdemes sorra kikisérletezgetni őket, hogy melyik nyeri el a
tetszésünket. A megjelenő alakzatok komplexitása egyre fokozódik, rajzokban
körülményes lenne ábrázolni, és a vele izomorf gráfot is megalkotni, ellenben
cselekvéssel, az újainkkal kell mozgatnunk a csúcsokat - miközben az élek
nyúlnak – mindaddig amíg olyan gráfot nem kapunk, amiben nincsenek egymást
metsző élek.

A Hamilton utak elméleti háttere

Akkor nevezünk egy utat Hamilton-útnak, ha az a gráf minden csúcsán
pontosan egyszer halad át.

Akkor nevezünk egy utat Hamilton-körnek, ha az a gráf minden csúcsán
pontosan egyszer halad át, és a kiindulási pont megegyezik az érkezési ponttal.

A Hamilton utak esetén is elvárnánk, hogy az Euler utak mintájára,
létezzenek az Euler két tételéhez hasonló tételek, ami a csúcsok
bejárhatóságáról szól. Nos, a Hamilton utak esetén sajnálatosan nem léteznek
ilyen tételek, vagyis Hamilton-körök illetve utak keresésére ma sem ismert

98