Briefträgerproblem
Das Briefträgerproblem ist ein Modell aus der Graphentheorie und kombinatorischen Optimierung, bei welchem man sich des übertragenen Bildes eines Postboten, der auf dem kürzesten Weg Briefe austrägt, bedient: 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 Alan Goldman nach dem chinesischen Mathematiker Mei Ko Kwan, der das Problem erstmals 1962 untersuchte.[1] Eine Lösung wurde 1973 durch Jack Edmonds und Ellis L. Johnson angegeben.[2]
Modellierung des Problems mit Graphen
[Bearbeiten | Quelltext bearbeiten]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
[Bearbeiten | Quelltext bearbeiten]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. Allgemein lässt sich das Problem lösen, indem 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, besitzt er Knoten mit ungeradem Knotengrad. Da in jedem Graphen Knoten mit ungeradem Grad nur in gerader Anzahl auftreten, ist gerade. 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 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 dem Matrixmultiplikations- oder dem Tripelalgorithmus ermittelt) zwischen den beiden entsprechenden Knoten im ursprünglichen Graphen. In diesem vollständigen Graphen wird dann eine kostenminimale perfekte Paarung mit Matchingkanten gesucht. Für jede Matchingkante werden dann im ursprünglichen Graphen die Kanten des entsprechenden kürzesten Weges zwischen den beiden Knoten dupliziert. Auf diesen Kanten des Ursprungsgraphen 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
[Bearbeiten | Quelltext bearbeiten]
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 ungeradem 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 ungeradem Knotengrad der vollständige Graph 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 . 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.
