[Wiskunde] Hamilton Circuit
 

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:P
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

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. :p

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".