Chinees postbodeprobleem

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Voorbeeld

Het Chinese postbodeprobleem is een veelgebruikte metafoor om een bekende probleemstelling in de grafentheorie duidelijk te maken. Een postbode moet brieven bezorgen in een bepaalde stad. Hij moet daarbij vertrekken vanuit het postkantoor, alle straten doorlopen om vervolgens terug in het postkantoor te eindigen. Daarbij is het de bedoeling om de totaal afgelegde afstand minimaal te houden. Vertaald naar de grafentheorie komt dit hierop neer: zoek de kortst mogelijke route in een ongerichte graaf, die vertrekt en eindigt in dezelfde knoop, en die alle verbindingen in de graaf bevat (met andere woorden, zoek de kortste Euler-cykel).

Dit probleem lijkt sterk op het handelsreizigersprobleem. Het handelsreizigersprobleem is echter NP-moeilijk, terwijl het Chinese postbodeprobleem in polynomiale tijd opgelost kan worden.

De naam Chinese postman problem werd bedacht door Alan Goldman van het National Institute of Standards and Technology en verwijst naar het feit dat de Chinese wiskundige Mei Ko Kwan er in 1962 voor het eerst over publiceerde.[1]

Bronnen, noten en/of referenties