Wenn jede Kante im TSP mindestens die Länge 1 hat, hat jede Tour im TSP mindestens die Größe n. Um z.B. 4 Knoten miteinander zu verbinden, sind mindestens 4 Kanten notwendig (Viereck). Versuchen Sie doch, sich an einem einfachen Beispiel die Umwandlung klar zu machen!
|
|
---|
Copyright 1996 by Matthias Hoffmann (TFH Berlin)
letzte Änderung: 1-11-1996