Ik heb een fout ontdekt in opgave 2 versie 2 (al zou dit kunnen gelden voor elke andere opgave) met betrekking tot bipartiet zijn van een graaf. Ik weet niet of u deze opgave zo bedoeld heeft of dat het komt door de recente wijzigingen die u heeft gemaakt aan de opgave.

Het is namelijk zo, dat voor elke graaf G die voldoet aan de voorwaarden van de opgave dat deze G altijd bipartiet is. 

Bewijs:

 - Stel dat G NIET bipartiet is
 - Dan moet er dus in G een cycle te vinden zijn zodanig dat deze een oneven aantal nodes heeft
 - Elke mogelijke cycle C in G moet minimaal 4 nodes bevatten vanwege uw richtingsbeperkingen op de diagonale windstreken.
 - Merk op dat de elke uitbreiding van C alleen in veelvouden van 2 kan gebeuren (aangezien men niet schuin mag en G eigenlijk een soort grid is)
 - Dit betekent dat het aantal nodes in C altijd even is
 - Contradictie !

Mijn eigenlijke vraag is of het nu nodig is om echt op bipartietheid te testen of dat een simpele "n 1" als uitvoer voldoende is (waar n een 0 of 1 is voor de indicatie van de a-cyclic test).

Met vriendelijke groet,

JM Vuong