Traveling Salesman Polytop < Optimierung < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Hallo zusammen!
Ich grübel seit eniger Zeit über den Facetten des Symmetrischen Traveling Salesman Polytopes und bin diesbezüglich schon einiges weitergekommen. Wir haben ja als minimales Gleichungssystem die Gradgleichungen. Dieses Gleichungssystem hat vollen Rang n.
Als Facetten kommt nun einiges an Ungleichungen hinzu (allerdings sind nicht alle Facetten bekannt, außer für sehr kleine n).
Nun ist die Dimension des Polytopes dim(STSP(n))=|E|-|V|=n(n-3)/2
Allerdings verstehe ich nicht so recht warum sich die Dimension um n verringert. Der Lösungsvektor muss doch nach wie vor alle Kanten beinhalten, sonst würde man doch Teilwege unterschlagen, oder?
Wie kann es nun sein, dass anscheinend n Einträge des Lösungsvektors ignoriert werden können? Ansonst bräcuhte man ja für jede mögliche Kante eine Variable und ich käme auf eine Dimension von |V|.
In Beispielen die ich mir angeschaut habe bleibt der Lösungsvektor auch |V|-Dimensional, also hab ich vielleicht die Definition der Dimension des Polytopes falsch verstanden?
Als Beweis habe ich gefunden, dass sich alle nichttrivialen Gleichungen aus den Gradgleichungen linear kombinieren lassen, das ist auch soweit schlüssig, da es |E| Gradgleichungen gibt würde das die - |E| erklären, aber verstehen tu ich es bisher noch nicht.
Vielen Dank schonmal für alle Ideen und Anregungen
GREETz
Eddie
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:20 Sa 05.09.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
