Adott egy 8x6 négyzetből álló téglalap. A bal felsőből hogyan lehet eljutni a jobb alsóba? Részletek lent.

Keszitsuk el a kovetkezo grafot: minden mezo egy pont a grafban es ket pont akkor van osszekotve, ha a megfelelo mezok szomszedosak, vagyis egy lepesben az egyikbol a masikba at lehet jutni.

Ezen a grafon keresunk egy olyan Hamilton utat, ami a bal felso sarokbol indul es a jobb alsoba erkezik.

Egeszitsuk ki a grafot meg egy ponttal, ami a bal felso sarkot es a jobb also sarkot reprezentalo csuccsal van osszekotve.

Nyilvan ebben a grafban egy Hamilton kor megfelel az eredeti grafban egy olyan Hamilton uttal amilyet a feladat megkovetel.

Az a kerdes tehat, hogy az uj graf Hamiltoni-e.

A graf elsorozata:

2,2,2,2,2,3,...(20db 3-as) ...3, 4, ... (24db 4-es)...,4

Azt grafelmeletbol tudjuk, hogy az (a1,..., an) elsoroza pontosan akkor Hamiltoni, ha minden k<n/2 eseten ak <k+1 eseten a(n-k)> n-k-1.

Ez nyilvanvaloan nem igaz, mindjart k=1 eseten a1=2, viszont a46=4 nem nagyobb 45-nel. Vagyis a kiegeszitett grafban nincs Hamilton kor, vagyis az eredetiben nem lehet olyan Hamilton ut ami a bal felso sarokban kezdodik es a jobb alsoban er veget.

Ennél kicsit egyszerűbb, ha sakktáblaszerűen kiszínezzük az ábrát.

A bal felső legyen fekete mező mondjuk. A jobb alsó szintén fekete.

A lépések során mindig fekete-fehér-fekete-fehér stb. Sorrendben jönnek a mezők.

Mivel az első és utolsó mező is fekete, ezért összesen PÁRATLAN számú mezőn mentünk át.

Mivel 6*8 páros, ezért egy mezőnek ki kell maradnia.

Nem el sorozat, hanem fokszam sorozat, es fokszam sorozatot forditva irtam fel, bocs. Figyelmetlen vagyok, keso van.

A megoldas logikaja viszont ugyanaz:

A graf fokszam sorozata:

4, ... (24db 4-es)...,4, 3,...(20db 3-as) ...3,2,2,2,2,2

Azt grafelmeletbol tudjuk, hogy az (a1,..., an) fokszam soroza pontosan akkor Hamiltoni, ha minden k<n/2 eseten ak <k+1 eseten a(n-k)> n-k-1.

Ez nyilvanvaloan nem igaz, mindjart k=1 eseten a1=4, viszont a44=2 nem nagyobb 45-nel. Vagyis a kiegeszitett grafban nincs Hamilton kor, vagyis az eredetiben nem lehet olyan Hamilton ut ami a bal felso sarokban kezdodik es a jobb alsoban er veget.

Szamolj utana, tartok tole, hogy valami apro elszamolas meg lehet, de a lenyeg az amit irtam.

Végtelensok megoldás van. Például: Végigmész a sorokon szépen egymás után, majd miután az összes mezőn jártál és a bal alsóban végzed, átmész a jobb alsóba. Ugyanez eljátszaható úgy is, hogy az oszlopokon haladsz végig, vagy csigavonalban kívülről befelé, vagy haladhatsz össze-vissza. Miután az összes mezőt bejártad, szépen átmész a jobb alsó sarokba (lefelé, amíg lehet; majd jobbra, amíg lehet), és kész vagy.

A korábbi megoldók azt nem vették figyelembe, hogy a feladatban NINCS megkövetelve, hogy egy mezőn csak egyszer lehetne áthaladni. Ha ez is elő lenne írva, akkor valóban nem lenne megoldás, és a korábbi sakktáblaszínezős bizonyítás éppúgy jó, mint az Euler-tételes (2-nél több páratlan fokszámú csúcsa van a gráfnak).