Bejárható-e egy 5*5-ös sakktábla lóugrással úgy, hogy nem kell a kiindulási pontba visszatérni, feltéve, hogy minden mezőre pontosan egyszer ugrunk. És ha vissza kell térni? Adja meg a feladat gráfmodelljét.

Próbáljuk ki, legyenek a sorok betűk A-E, az oszlopok meg számok:

A1-C2-E1-D3-E5-C4-A5-B3-C1-E2-D4-B5-A3-B1-D2-E4-C5-A4-B2-D1-E3-D5-B4-A2-C3 Azt hiszem sikerült elsőre papír nélkül :D

A gráfmodellt úgy tudod a legkönnyebben megadni, hogy rajzolsz egy 5x5-ös sakktáblát, és mindegyik mezőt összekötöd, akik lóugrással elérhetőek egymásról.

Ha nem kell visszaérni az elejére, azt már megadták.

Ha vissza kell érni az elejére, az nem oldható meg, és ez két módon is kijön; egyrészt ha minden mezőt érintünk, akkor a gráfban minden csúcshoz két él tartozik (egy "bemenő" és egy "kimenő" él"). A sarkokban lévő csúcsokhoz pontosan 2 él tartozik, tehát ezeket mind fel kell használnunk, a baj csak az, hogy ezek egy zárt kört alkotnak úgy, hogy ezekkel az élekkel csak 8 mező járható be. Tehát ezek miatt más mezőkre nem is lehet lépni, vagy ha lépünk, akkor valamelyis sarok kimarad a játékból. Másrészt ún. Hamilton-kört keresünk a gráfban, arra pedig ismerjük azt a tételt, hogy ha egy legalább háromcsúcsú gráfban akármennyi csúcsot elhagyunk, és az egymástól független gráfok (amik között nincs átjárás) többen lesznek, mint ahány csúcsot töröltünk, akkor a gráfban nincs Hamilton-kör (tehát ha például 5 csúcsot töröltünk, és legalább 6 független gráf képződőtt, akkor az eredetiben nincs Hamilton-kör). A lóugrás következtében mindig színt váltunk, tehát feketéről csak fehérre léphetünk vagy fordítva. Az biztos, hogy vagy 12 fehér és 13 fekete mező van, vagy fordítva, viszont ha a kevesebben lévőket mind eltöröljük a tábláról, akkor marad 13 a másik színből, amik között nincs átmenés, tehát 13 gráfra hullott szét a gráfunk, emiatt a gráfban nem lehet Hamilton-kör. (Természetesen máshogyan is lehet törölni, hogy több részre essen a gráf, mint ahányat töröltünk, de talán ez a legegyszerűbb törlési mód).