Chinese Postbodeprobleem

• Informatica
• Middelbare school
• havo, vwo
• Leerjaar 4

Chinese Postbodeprobleem

Leerdoelen

Na deze les weet je de strategie hoe je het moeilijke probleem van de Chinese postbode kunt oplossen. 

Je weet wat er bedoelt wordt met Euleriaans en simi-Euleriaans.

Euleriaans of niet?

Euleriaans

De afbeelding hiernaast is volledig Euleriaans, want we kunnen op ieder punt beginnen en eindigen

Semi-Euleriaans

De afbeelding hiernaast is semi-Euleraans. Als je het goed getekend hebt, dan ging je er op 1 punt in en kwam je er elders uit.

Het Chinese Postbodeprobleem

Een postbode moet brieven bezorgen in een bepaalde stad. Hij moet daarbij vertrekken vanuit het postkantoor, alle straten doorlopen om vervolgens weer in het postkantoor te eindigen. Daarbij is het de bedoeling om de totaal afgelegde afstand minimaal te houden. 

Ook strooiwagens in de winter kennen dit probleem, nu niet minimale afstand, maar zo min mogelijk tijd.

7 bruggenprobleem van Königsberg (Kalingrad)

Het probleem van de Chinese postbode

Stappenplan:

1. Noteer alle oneven kruispunten.(B, C, G, H, J, K)

2. Maak combinaties van de oneven punten en bepaal de afstanden

Stappenplan:

2. Maak combinaties van de oneven punten en bepaal de afstanden.

BC(7) + GH(3) + JK(2) = 12

BH(2) + CG(3) + JK(2) = 7

BJ(3) + GK(2) + CH(6) = 11

BG(5) + JH(1) + CK(5) = 11

BK(5) + HJ(1) + CG(3) = 9

Stappenplan:

3. 

BC(7) + GH(3) + JK(2) = 12

BH(2) + CG(3) + JK(2) = 7

BJ(3) + GK(2) + CH(6) = 11

BG(5) + JH(1) + CK(5) = 11

BK(5) + HJ(1) + CG(3) = 9

Als je alle mogelijke combinaties hebt opgeteld, dan kijk je welke het kleinst is. Hier is dat de combinatie van BH + CG + JK dubbel lopen = 7 extra

Oefenen

Welke punten zijn oneven?

Welke combinaties
kun je maken?