Briefträgerproblem

Das Briefträgerproblem (englisch Chinese Postman Problem oder Route Inspection Problem) ist ein Begriff aus der Graphentheorie. Hierbei bedient man sich des übertragenen Bildes eines Postboten, 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.

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

Modelliert wird das Problem mittels Graphen. Dabei werden Kreuzungen als Knoten und Straßen als Kanten modelliert. Den Kanten wird die Länge der entsprechenden Straße zugeordnet. Gefragt ist nun nach einem kürzesten Zyklus, der alle Kanten mindestens einmal durchläuft.

Die Lösung des Problems hängt vom entstehenden Graphen ab. In eulerschen Graphen entspricht die kürzeste Route einfach einer Eulertour. In Bäumen muss jede Kante genau zweimal durchlaufen werden. Allgemein lässt sich das Problem lösen, indem man zu den Knoten mit ungeradem Grad einen Distanzgraphen erstellt und dort eine kleinste perfekte Paarung sucht. Die Kanten der zugehörigen Pfade im Originalgraphen müssen dann entsprechend oft eingefügt werden, so dass der Graph eulersch wird. Es bleibt dann wieder das Finden einer Eulertour.