Chinees postbodeprobleem

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 weer 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.

Als er op ieder verkeersknooppunt een even aantal wegen uitkomt, hoeft hij volgens de grafentheorie iedere weg maar één keer langs te gaan en komt hij bij zijn beginpunt uit. De weg die hij dan aflegt, is een eulercykel.

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

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]