Chinesisches Briefträgerproblem

Das Problem, daß ein Briefträger jede Straße seines Zustellbereiches mindestens einmal durchläuft, zum Ausgangspunkt zurückkehrt und insgesamt einen möglichst kurzen Weg durchlaufen will, läßt sich graphentheoretisch wie folgt formulieren: Es sei G=(V,E,f) ein bewerteter Graph mit für alle Kanten Gesucht wird eine Kantenfolge F mit minimaler Gesamtlänge

Die Bezeichnung des Problems erinnert an den chinesischen Mathematiker KUAN, der sich als erster mit dem Problem beschäftigt hat. Zur Lösung sind zwei Fälle zu unterscheiden:

1. G ist ein EULERscher Graph - dann ist jede geschlossene EULERsche Linie optimal - und
2. G besitzt keine geschlossene EULERsche Linie.

Einen effektiven Algorithmus zur Lösung des Problems haben EDMONDS und JOHNSON angegeben (s. [5.44]).