Briefträgerproblem - LinkFang.de





Briefträgerproblem


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 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

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. 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 [math]r \gt 0[/math] Knoten mit ungeradem Knotengrad. Da in jedem Graphen Knoten mit ungeradem Grad nur in gerader Anzahl auftreten, ist [math]r[/math] 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 [math]\frac{r}{2}[/math] 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 [math]\frac{r}{2}[/math] 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

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 ungeradem Knotengrad der vollständige Graph [math]K_4[/math] 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 [math]4+2=6[/math]. 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

Weblinks

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

Kategorien: Keine Kategorien vorhanden!

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Briefträgerproblem (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.