imported>Schotterebene: Formatierung

2026-04-17T12:27:14Z

Formatierung

Neue Seite

Das '''Briefträgerproblem''' ist ein Modell aus der [[Graphentheorie]] und [[Kombinatorische Optimierung|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 [[Mathematik]]er [[Guan Meigu|Mei Ko Kwan]], der das Problem erstmals [[1962]] untersuchte.<ref>M. K. Kwan ''Graphic Programming Using Odd or Even Points'', Chinese Mathematics, Band 1, 1962, S. 273–277</ref> Eine Lösung wurde 1973 durch [[Jack Edmonds]] und [[Ellis L. Johnson]] angegeben.<ref>Edmonds, Johnson ''Matching, Euler Tours and the Chinese Postman'', Mathematical Programming, Band 5, 1973, S. 88–124</ref>

== Modellierung des Problems mit Graphen ==
Modelliert wird das Problem mittels [[Graph (Graphentheorie)|Graphen]]. Dabei werden Straßen als [[Kante (Graphentheorie)|Kanten]] und Kreuzungen als [[Knoten (Graphentheorie)|Knoten]] modelliert. Den Kanten wird die Länge der entsprechenden Straße zugeordnet. Gefragt ist nun nach einem kürzesten [[Zyklus (Graphentheorie)|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 [[Grad (Graphentheorie)|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 > 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 [[Min-Plus-Matrixmultiplikations-Algorithmus|Matrixmultiplikations-]] oder dem [[Algorithmus von Floyd und Warshall|Tripelalgorithmus]] ermittelt) zwischen den beiden entsprechenden Knoten im ursprünglichen Graphen. In diesem vollständigen Graphen wird dann eine kostenminimale perfekte [[Matching (Graphentheorie)|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 ==
[[Datei:Chinespostman 1.png|mini|klasse=skin-invert-image|Graphenmodell einer Stadt mit 14 Straßen und 9 Kreuzungen. Die vier Knoten (1, 3, 6 und 9) mit ungeradem Knotengrad sind rot markiert]]
[[Datei:Chinespostman 2.png|mini|klasse=skin-invert-image|Der Vollständige Graph <math>K_4</math> der Knoten mit ungeraden Knotengrad und mit Kantengewichten der kürzesten Wege zwischen diesen. Die kostenminimale Paarung ist fett markiert.]]
[[Datei:Chinespostman 3.png|mini|klasse=skin-invert-image|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 <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.

== Ähnliche Probleme ==
* [[Eulerkreisproblem]]
* [[Hamiltonkreisproblem]]
* [[Problem des Handlungsreisenden]]

== Literatur ==
* {{Literatur
|Autor=Lutz Volkmann
|Titel=Fundamente der Graphentheorie
|Verlag=[[Springer Science+Business Media|Springer Verlag]]
|Ort=Wien, New York
|Datum=1996
|ISBN=3-211-82774-9
|Kapitel=3
|Online=[https://zbmath.org/0844.05001 ''zbMATH Open'']}}

== Weblinks ==
{{Commonscat|Route inspection problem|Briefträgerproblem}}
* [https://mathworld.wolfram.com/ChinesePostmanProblem.html Chinese Postman Problem bei Mathworld]

== Einzelnachweise ==
<references />

{{Normdaten|TYP=s|GND=4806884-6}}

{{SORTIERUNG:Brieftragerproblem}}
[[Kategorie:Problem (Graphentheorie)]]

Briefträgerproblem - Versionsgeschichte

imported>Schotterebene: Formatierung