prev up inhalt next


14 Chinese Postman

Gegeben: G = (V,E) ungerichtet, gewichtet mit c : E$\to$$
\mathbb {N}
$

Gesucht: Billigste Kantenrundreise, d.h. geschlossene Kantenfolge, in der jede Kante mindestens einmal auftritt.

i)
Ist G eulersch (d.h., jeder Knoten hat geraden Kantengrad), so liefert die Eulertour die billigste Postman-Tour.
ii)
Ist G nicht eulersch (d.h., es ex. Knoten mit ungeradem Kantengrad), so muß G durch Verdoppelung einiger Kanten in einen Eulergraph G' überführt werden. Die gesuchten Kanten bilden ein System von kantendisjunkten Wegen zwischen den Knoten ungeraden Grades in V .


Eine Kante in G' wird maximal zweimal durchlaufen, sonst entferne zwei Kanten $\Rightarrow$ 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.


prev up inhalt next