Chinese Postman Problem

Das Briefträgerproblem 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 gleichzeitig) in einem Straßennetzwerk (Stadt) zustellen.

Seinen englischen Namen (Chinese postman problem) erhielt das Briefträgerproblem durch den chinesischen Mathematiker Mei Ko Kwan, der das Problem erstmals 1962 untersuchte.

Modellierung des Problems mit Graphen

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

Lösung des Problems

Die Lösung des Problems hängt vom entstehenden Graphen ab. In eulerschen Graphen (zusammenhängender Graph mit geraden Knotengraden) entspricht die kürzeste Route einer jede Kante genau einmal durchlaufenden Eulertour. In Bäumen muss jede Kante genau zweimal durchlaufen werden. Allgemein lässt sich das Problem lösen, in dem man den Graphen kostenminimal durch Einfügen weiterer Kanten eulersch macht und das Problem damit auf das Finden einer Eulertour zurückführt. Ist ein zusammenhängender Graph nicht Eulersch, besitz er eine gerade Anzahl von r Knoten mit ungeradem Knotengrad. Verbindet man jeweils zwei Knoten ungeraden Knotengrades durch einen zusätzlichen Weg werden die ungeraden Knotengrade gerade, während die geraden Knotengrade gerade bleiben. Um den Graph eulersch zu machen müssen also insgesamt $\frac{r}{2}$ zusätzliche Wege in den Graphen eingefügt werden.

Zur kostenminimalen Erweiterung des Graphen wird zu den Knoten mit ungeradem Grad ein vollständiger Graph erstellt. Als Kantengewichte wählt man jeweils die Distanz des kürzesten Weges (beispielsweise mit Tripelalgorithmus ermittelt) zwischen den beiden entsprechenden Knoten im ursprünglichen Graphen. In diesem vollständigen Graphen wird dann eine kostenminimale perfekte Paarung mit $\frac{r}{2}$ Matchingkanten gesucht. Für jede Matchingkante werden dann im ursprünglichen Graphen die Kanten des entsprechende kürzeste Weg zwischen den beiden Knoten dupliziert. Auf diesen Kanten muss der Briefträger also genau zweimal entlanglaufen. Jede Eulertour in dem so erweiterten Graphen ist dann eine optimale Lösung des Briefträgerproblems.

Beispiel

Graphenmodell einer Stadt mit 14 Straßen und 9 Kreuzungen. Die vier Knoten (1,3,6 und 9) mit ungeradem Knotengrad sind rot markiert

Der Vollständige Graph K₄ der Knoten mit ungeraden Knotengrad und mit Kantengewichten der kürzesten Wege zwischen diesen. Die kostenminimale Paarung ist fett markiert.

Zusätzlich eingefügte Kanten sind rot. Alle Knotengrade sind jetzt gerade.

Es sei eine Stadt mit vierzehn Straßen und neun Kreuzungen 1, …, 9 gegeben. Der entsprechende Graph (siehe erste Abbildung) hat vier Knoten (1,3,6 und 9) mit ungeraden Knotengrad und ist damit nicht eulersch. Gesucht ist jetzt eine kostenminimale Eulersche Erweiterung des Graphen, um eine Eulertour angeben zu können. Würde man beispielsweise die beiden Kanten {1,3} und {6,9} verdoppeln, würde der entstehende Graph eulersch, da dann alle Knoten geraden Grad hätten. Die entsprechende Eulertour wäre aber für den Briefträger nicht unbedingt die kürzeste Tour. Zur Ermittlung der kürzesten Erweiterung wird aus den Knoten mit ungeraden Knotengrad der vollständige Graph K₄ erstellt (zweite Abbildung). Als Kantengewicht wird jeweils die Länge des kürzesten Weges zwischen jeweils zwei Knoten abgetragen. Das minimale Matching besteht in diesem Fall aus den Kanten {1,6} und {3,9} mit Gesamtlänge 4 + 2 = 6. Die entsprechenden Kanten der kürzesten Wege von 1 nach 6 und von 3 nach 9 werden dann im Ursprungsgraph zusätzlich eingetragen (dritte Abbildung). Eine Eulertour und damit minimale Briefträgerrundtour wäre beispielsweise die Knotenfolge (1,2,3,4,9,3,1,8,7,3,9,7,6,9,5,6,7,8,1). Die Straßen, die den zusätzlich eingefügten roten Kanten entsprechen, werden dabei vom Briefträger doppelt abgefahren.

Siehe auch

• Eulerkreisproblem
• Hamiltonkreisproblem
• Problem des Handlungsreisenden