Traveling Salesman Problem Antwort



Das war richtig!

T hat eine Tour der Länge von maximal n+1 g.d.w. G einen Hamiltonschen Pfad besitzt.

Sehen wir uns das an einem Beispiel an:
Umwandlung
Hamiltonscher Pfad ins TSP
Alle Kanten aus G aufaddiert ergeben n-1 (4) Einheiten. Dazu kommt noch die Kante, die die Rundreise schließt, mit zwei Einheiten. Das macht zusammen n+1 (6) Einheiten.

Es könnte aber sein, daß diese schließende Kante im Graphen G schon vorhanden war. In diesem Fall wird lediglich eine Einheit aufaddiert. Insgesamt sind das dann n (5) Einheiten. Deshalb ist nur eine maximale Angeabe korrekt.


TSP & NPC Homepage TSP & NPC

Copyright 1996 by Matthias Hoffmann (TFH Berlin)
letzte Änderung: 1-11-1996