Briefträgerproblem

Das Chinese Postman Problem ist ein Begriff aus der Graphentheorie. Hierbei bedient man sich des übertragenen Bildes eines Postbotens, der auf dem kürzesten Weg Briefe austrägt: Ein Postbote soll die Briefe auf beiden Seiten der Straße in einem Straßennetzwerk (Stadt) zustellen.

Gelöst wird dieses Problem so, daß die Straßen als Kanten und die Kreuzungen als Knoten modelliert werden. Nun wird die minimale Strecke gesucht, so daß jede Kante mindestens zweimal durchlaufen wird (mehrfaches Durchlaufen der Knoten aber auch Kanten ist möglich).

Siehe auch: Eulerkreis-Problem