Gesucht: Billigste Kantenrundreise, d.h. geschlossene Kantenfolge, in der jede Kante mindestens einmal auftritt.
Eine Kante in G' wird maximal zweimal durchlaufen, sonst entferne zwei Kanten G' bleibt eulersch.
Seien n1,n2,...,nk die Knoten mit ungeradem Kantengrad. ( k gerade, denn in einem Graph ist die Anzahl der Knoten mit ungeradem Kantengrad gerade)
Bilde Distanzmatrix dij mit Floyd.
Bilde Clique mit k Knoten und Kantengewicht dij .
In dieser Clique suchen wir nun das Minimum Cost Matching. Dieses Matching liefert uns die Knotenpaare, die gemäß Floyd verbunden werden. Wir erhalten also einen Eulergraph und somit auch die Postman-Tour.