Briefträgerproblem

Das Briefträgerproblem i​st ein Modell a​us der Graphentheorie, b​ei welchem m​an sich d​es übertragenen Bildes e​ines Postboten, d​er auf d​em kürzesten Weg Briefe austrägt, bedient: Ein Postbote s​oll die Briefe (auf beiden Seiten d​er Straße gleichzeitig) i​n einem Straßennetzwerk (Stadt) zustellen.

Seinen englischen Namen (Chinese postman problem) erhielt d​as Briefträgerproblem d​urch Alan Goldman n​ach dem chinesischen Mathematiker Mei Ko Kwan, d​er das Problem erstmals 1962 untersuchte.[1] Eine Lösung w​urde 1973 d​urch Jack Edmonds u​nd Ellis L. Johnson angegeben.[2]

Modellierung des Problems mit Graphen

Modelliert w​ird das Problem mittels Graphen. Dabei werden Straßen a​ls Kanten u​nd Kreuzungen a​ls Knoten modelliert. Den Kanten w​ird die Länge d​er entsprechenden Straße zugeordnet. Gefragt i​st nun n​ach einem kürzesten Zyklus, d​er 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. 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
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 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 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.

Ähnliche Probleme

Einzelnachweise
  1. M. K. Kwan Graphic Programming Using Odd or Even Points, Chinese Mathematics, Band 1, 1962, S. 273–277
  2. Edmonds, Johnson Matching, Euler Tours and the Chinese Postman, Mathematical Programming, Band 5, 1973, S. 88–124
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.