Minimalgerüst |
| 13.05.2013, 13:36 | Melissa11 | Auf diesen Beitrag antworten » |
| Minimalgerüst Also ich soll ein Minimalgerüst für den vollständigen Graphen über V={1,..,n} mit der Gewichtsfunktion w(ij)=i+j bestimmen. Meine Ideen: Mir ist schon klar, wie ich das mit dem Greedy-Algorithmus machen kann, allerdings weiß ich nicht, wie das jetzt hier in diesem allgemeinen Fall geht. Kann mir einer einen Tipp geben? |
||
| 13.05.2013, 14:18 | Mystic | Auf diesen Beitrag antworten » |
| RE: Minimalgerüst Mein Tipp: Rechne mal kleine Fälle, wie z.B. n=4 oder n=5, ganz normal durch, schau dir die Lösungen dazu an und überleg dir dann, wir die allgemeine Lösung aussehen könnte... |
||
| 13.05.2013, 16:33 | Melissa11 | Auf diesen Beitrag antworten » |
| RE: Minimalgerüst Hallo Mystic, vielen Dank für deinen Tipp. Also ich hab mir das mal angeschaut und dabei ist aufgefallen, dass das Minimalgerüst immer nur aus den Kanten besteht, die vom ersten Knoten zu allen anderen gehen. Wie schreibe ich das denn aber jetzt mathematisch richtig auf? Und kann ich die Behauptung dann mit Induktion beweisen? |
||
| 13.05.2013, 23:33 | Mystic | Auf diesen Beitrag antworten » |
| RE: Minimalgerüst Der Beweis geht natürlich induktiv. Als erste Kante wird natürlich 12 gewählt, da sie das kleinste Gewicht hat. Angenommen, 12,13,...,1k wurden für ein k>1 schon gewählt. Du musst dir dann überlegen, dass als nächstes auf jeden Fall die Kante 1(k+1) drankommt, denn alle Kanten mit welche als Konkurrenten überhaupt in Frage kommen, scheiden ja aus, da durch ihre Wahl die Kreisfreiheit zunichte gemacht wird... |
||
|
|