[Wiskunde] Hamilton Circuit

[damsco]

hey allemaal, ik moet voor wiskunde een PO maken over het Hamilton-circuit, maar het probleem is, dat ik er maar niet uitkom..er waren 6 vragen, de eerste 4 heb ik al gemaakt maar vraag 5 en 6 kom ik maar niet uit
owja, het kan natuurlijk ook dat iemand precies dezelfde PO ergens thuis heeft liggen, die zou ik ook wel graag willen hehe
please wie kan me helpen

5. Onderzoek of er een Hamilton-circuit bestaat voor het 4*4 schaakbord.

6. Beredeneer dat er geen Hamilton-circuit voor het 5*5 schaakbord bestaat.

danku danku

[Sortjuh]

Voor 5 en 6 zou je, denk ik, Daric's theorie kunnen gebruiken:

Als iedere vertex van een verbonden graaf met 3 of meer vertices verbonden is met tenminste de helft van de overgebleven vertices, dan heeft de graaf een Hamilton Circuit.

Ik weet 't niet zeker, maar je kunt 't altijd proberen.

De stelling van Dirac is niet echt van toepassing hier. Met een paard kan je maar 8 vakken aanvallen, en niet 12 (zoals vereist voor een 5x5-bord met 25 vertices).

Voor het 5x5-geval moet je even kijken naar de kleuren van de vakjes. Wat kan je beredeneren voor een gesloten circuit? Lukt dat op een 5x5-bord? Dan kan je ook direct vertellen of het wel of niet mogelijk is op een 1319x5893-schaakbord.

4x4 is misschien iets lastiger. Google eens op "knight's tour".