Das Briefträgerproblem (englisch chinese postman problem, route inspection 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 einmal durchlaufen wird (mehrfaches Durchlaufen der Knoten aber auch Kanten ist möglich) und der Briefträger wieder am Ausgangsort ankommt.

Seinen Namen erhielt das Briefträgerproblem durch den chinesischen Mathematiker Mei Ko Kwan, der das Problem erstmals 1962 untersuchte.

Siehe auch

• Eulerkreis-Problem
• Ungarische Methode