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 
ein bewerteter Graph mit 
für alle Kanten 
Gesucht wird eine Kantenfolge 
mit minimaler Gesamtlänge
 |
(5.337) |
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. 
ist ein EULERscher Graph - dann ist jede geschlossene
EULERsche Linie optimal - und
2.
besitzt keine geschlossene EULERsche Linie.
Einen effektiven Algorithmus zur Lösung des Problems haben EDMONDS und
JOHNSON angegeben (s. Lit.5.37).
