© h.hofstede (h.hofstede@hogeland.nl)

Wolf, Geit en Kool
       
Dit is een klassiek raadsel waarvan meerdere varianten bestaan.
Het oorspronkelijke probleem was het volgende:
Een boer is op weg naar de markt met een wolf, een geit en een kool bij zich.
Hij komt een rivier tegen die hij moet oversteken. Gelukkig ligt er een boot want hij kan niet zwemmen.
Helaas is er in de boot maar ruimte om één voorwerp (wolf, geit of kool) mee te nemen.

Maar hij kan de geit niet alleen met de wolf laten (dan eet de wolf de geit op) en ook de kool kan niet alleen met de geit gelaten worden (dan eet de geit de kool op).

Hoe moet de boer zijn drie voorwerpen aan de overkant krijgen??

       
Een eenvoudige grafen-oplossing.

Laten we een graaf gaan tekenen met als knooppunten welke van de drie voorwerpen zich bij de boer bevinden.
Noem de wolf W, de geit G en de kool K

Dan is bijvoorbeeld de knoop  WK toegestaan  (de wolf en de kool zijn bij de boer, de geit is alleen)
Maar W is niet toegestaan  (de wolf bij de boer, maar de geit dus alleen met de kool!)
       
Er zijn vijf toegestane knooppunten:  WGK, G, WG, WK en GK  (ga dat zelf maar na) die je hiernaast ziet.

Nu gaan we verbindingslijnen maken.
Stel dat we ons bevinden in situatie WG  (dus WG bij de boer, K alleen). Dan zijn er 3 opties voor de boer:

1. W meenemen. Dat geeft situatie WK
2. G meenemen. Dat geeft situatie GK
3. niets meenemen. Geeft situatie K  maar die kan niet.

Dus van WG lopen er verbindingslijnen naar WK en GK. 

       
Als je dat vanaf elk knooppunt doet geeft dat de graaf hiernaast  (merk nog op dat alle verbindingen ongericht zijn; immers als een vervoer de ene kant op kan dan kan het ook weer terug).

Nou, als we met WGK op de andere oever willen belanden, dan moeten we een  route van WGK naar WGK maken, en die route moet een oneven aantal verbindingslijnen hebben  (immers bij elke overgang gaan we van de ene naar de andere oever!).

       
Hieronder zie je dat dat in 7 stappen kan, op twee manieren.
       

       
Kannibalen en Missionarissen.
       
Drie kannibalen en drie missionarissen bevinden zich deze keer aan de zuidoever van een rivier. Er is een bootje waar 2 personen in kunnen.  Ze moeten weer allemaal naar de noordkant, en niemand kan zwemmen.
Maar zodra zich een situatie voordoet waarin de kannibalen ergens in de meerderheid zijn, dan eten ze de missionarissen op!

Oké,  eerst maar weer op zoek naar de knooppunten van de graaf......

(we gaan kannibalen K noemen, en missionarissen M).
 
We bekijken de toestanden waarin de boot niet op het water is. Dat kan bijvoorbeeld in een 4x4 rooster, zoals hiernaast.

Op de horizontale as staat het aantal missionarissen op de zuidoever, op de verticale as het aantal kannibalen op de zuidoever. Het rode vakje komt overeen met 3 missionarissen en 2 kannibalen op de zuidoever (en dus 0 missionarissen en 1 kannibaal op de noordoever).

   
Vervolgens maken we alle toestanden die niet toegestaan zijn (waarbij er missionarissen worden gegeten) zwart.  Zie de figuur hiernaast.

De startpositie (S) en de finishpositie (F) kleuren we rood.

Je ziet dat er 10 knooppunten voor onze graaf overblijven  (de nog witte vakjes).

Goed, tot zover de knooppunten, nu over naar de verbindingslijnen.

       
Er zijn 5 mogelijke bezettingen voor het bootje:   KK, MM, MK, K  of  M, dus ook in principe vanaf elk knooppunt vijf mogelijke buurknooppunten (maar daar kunnen zwarten bij zijn)
De knooppunten (witte vakjes) heb ik rood genummerd. Omdat het er vanaf hangt of je van noord naar zuid gaat of van zuid naar noord heb ik 10 knooppunten van de graaf op de zuidoever (bovenaan) en op de noordoever (onderaan) apart in de graaf onderaan gezet.  (zo'n graaf, met twee groepen knooppunten heet een bipartiete graaf en die zullen we later nog veel tegenkomen).
       

       
Dan is de vraag dus nu veranderd in:   "Maak een route in de graaf van S naar F".
Aan de graaf zie je direct dat de route 5-6 er zeker bij hoort, anders kun je nooit de linkerkant met de rechterkant verbinden.
Begin met die route en probeer S en F te bereiken.
Het gaat voor een groot deel vanzelf:
       

       
Tot hier had je geen keuze.  Nu wel.
Links kun je van 2 via 3 of via 5 naar S.  Rechts kun je via 8 of via 6 naar F
In totaal geeft dat dus 4 mogelijke oplossingen: 
       

       
Hier zie je het "vaarschema"  voor de oplossing  linksboven:
       

       

© h.hofstede (h.hofstede@hogeland.nl)