Optimierung |
| 03.11.2015, 20:46 | HIMYM | Auf diesen Beitrag antworten » |
| Optimierung Hallo! Ich habe hier eine Aufgabe bei der ich leider nicht weiter komme.Für jeden Tipp bin ich sehr dankbar. Aufgabe: G=(V,E) ist ein ungerichteter Graph mit einer Nichtnegativen Kostenfunktion. T ist der Minimaler Spannbaum(MST) bzgl der Kostenfunktion c E-> R. X ist eine geeignete Teilmenge von V. a) Ist T im allgemeinen auch ein MST für die Kostenfunktion (i) c^{i}=(c(e))^2 (ii) c^{ii}= 2*c(e) if e=(v,w) mit v aus X, w aus V ohne X c(e) else (iii) c^{iii}=c(e)+2 if e={v,w} mit v,w in X c(e) else Die Behauptungen entweder mit Gegenbeispiel widerlegen oder beweisen. Meine Ideen: Ich hatte gedacht dass die i stimmt,weil wenn ich vorher die kleinsten Kanten auswaehle,so dass c minimal, dann habe ich mit der Kostenfunktion aus (i) immer noch gewaährleistet, dass ich ein MST habe. Bei den anderen Teilaufgaben weiß ich leider gar nicht wie ich daran gehen soll. Tut mir leid,dass es nicht so gut aufgeschrieben worden ist. |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
