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