MST, Änderung von Kantengewichten. |
| 15.01.2008, 16:58 | Auf diesen Beitrag antworten » | ||
| JROppenheimer | MST, Änderung von Kantengewichten. Es geht um folgendes: Ich habe einen Graphen G=(E,V) und seinen minimalen Spannbaum T jeweils als Adjazenzliste gegeben. Jetzt soll ich eine Methode angeben, mit der in O(|E|) der neue Spannbaum erstellt werden kann, wenn die Länge einer Kante w(e) erhöht wird.... Ich muss gestehen ich hab nicht die geringste Ahnung, wie ich da ran gehn soll. Spontan dachte ich erstmal daran, dass Kruskal den MST ja relativ einfach kosntruiert. Kruskal arbeitet ja auf einer Ordnung der Menge der Kanten, in der Form, dass die Menge der Kanten nach Gewichten geordnet verarbeitet wird. Erst leichteste Kanten, dann schwere (oder kurze und dann lange, wie man will). Ich bin aber nicht sicher, wie ich von Adjazenzlisten (die ich persönlich so gar net mag, weil ich noch nie mit ihnen gearbeitet habe) zu der Lösung meines Problems komme. Für einen Ansatz oder ein Tip, der mich in die richtige Richtung treibt, wäre ich sehr dankbar! |
||
|
|
|||
| 15.01.2008, 17:28 | Auf diesen Beitrag antworten » | ||
| JROppenheimer | Angenommen, eine Kante (a,b) wird länger. Muss ich dann nicht einfach nru eine neue Kante suchen, die entweder die Form (...,b) oder (b,...) hat, und die bedingung stellen, dass kein Zyklus entsteht?! |
||
| 15.01.2008, 20:14 | Auf diesen Beitrag antworten » | ||
| Tobias | Versuch es mal mit dieser Idee: Entfernt man die neugewichtete Kante e aus dem Spannbaum T, zerfällt T-e in zwei knotendisjunkte Teilbäume mit den Knotenmengen V1 und V2. Sucht man nun die kürzeste Kante e', die jeweils einen inzidenten Knoten in der Menge V1 bzw. V2 hat, ist T-e+e' ein MST unter der neuen Gewichtungsfunktion. Ob das in O(|E|) geht habe ich mir noch nicht angeschaut. Übrigens: Man nennt bei einem Graphen die Knotenmenge für gewöhnlich zuerst. Ich gehe trotzdem mal davon aus, dass E die Kanten bei dir sind. |
||
| 16.01.2008, 14:08 | Auf diesen Beitrag antworten » | ||
| JROppenheimer | ach sorry, aus irgendeinem grund schreibe ich das AUS PRINZIP falsch herum, war natürlich G = (V,E) gemeint. Vielen Dank für die Hilfe, das mit den beiden Bäumen kam mir dann auch irgendwann, nach ein bisschen rumspielen und einen tip von noch wem anders. Vielen Dank! |
||
| Anzeige | |||
|
|
|||
| 17.01.2008, 20:52 | Auf diesen Beitrag antworten » | ||
| JROppenheimer | Ich habe jetzt ein ähnliches Problem und zwar gehts darum, dass diesmal ein Kantengewicht "verkleinert" wirt. Ich soll eine Methode konstruieren, die in O(|V|) einen neuen MST konstruiert. Ich hab mich mal dran orientiert, dass bei dem Bsp. oben Laufzeit O(|E|) gegeben war und dann die Menge der Kanten durchsucht werden musst ... Diesmal ist Laufzeit O(|V|) gegeben. Also dachte ich mir spontan schaust DU Dir mal die Knoten an. Wenn eine Kante günstiger wird, dann ist ja im Grunde nur von bedeutung, welche beiden Knoten durch sie verbunden werden. Und ob durch das Senken der Kantenlänge die beiden Knoten günstiger in den MST integriert werden können, als vorher. Alles natürlich untern den Bedingungen von wegen Zyklen und so ... Ich hatte zuerst überlegt, man könnte ja auch einfach die Lösung von oben anwenden. Dann hab ich mir aber über den Zusammenhang von Knoten und Kanten Gedanken gemacht. Und es sah für mich so aus, dass die maximale Kanten über ne Summenformel irgendwie zusammenhängen, in der Form: menge der kanten ist die summe von i = 1 bis |v| über i ....sehe aber gerade, dass die summe von 1 bis n quadratisch ist, das dann wohl nicht mehr in |E| ist |
||
| 17.01.2008, 21:55 | Auf diesen Beitrag antworten » | ||
| Tobias | Sei uv die Kante, die verkleinert wird. Nun gibt es zwei Möglichkeiten: 1.) Die Kante uv ist bereits im Spannbaum enthalten. Dann ändert sich der MST natürlich nicht. 2.) Die Kante uv ist im ursprünglichen Spannbaum nicht enthalten. Dann existiert ein eindeutiger Weg von u nach v im MST und durch Hinzunahme von uv entsteht genau ein Zyklus. Aus diesem Zyklus musst du nun die schwerste Kante herausnehmen um wieder einen MST zu erhalten. |
||
| 17.01.2008, 23:20 | Auf diesen Beitrag antworten » | ||
| JROppenheimer | DAnke für deine schnelle Antwort! Ich hab mir über das, was Du geschrieben hast Gedanken gemacht und mir ist folgendes aufgefallen: angenommen, es gibt folgenden graphen: a-1-b-1-c-1-d-4-e (in der form KNOTEN -kosten- KNOTEN, ich hoffe Du kannst folgen... ) und weiterhin gäbe es eine kante von a nach c mit kosten 5 mst wäre a-b-c-d-e wird (a,c) jetzt günstiger ... sagen wir 3. dann kommt das,was UD sagst net hin füge ich die kante ein entsteht ein zyklus, entferne ichd ann die teuerste kante (d,e), ist der zyklus aber nicht beseitigt. ähnlich wie in dem bild unten... Oder meintest Du "die teuserste Kante des Zyklus"? |
||
| 18.01.2008, 00:29 | Auf diesen Beitrag antworten » | ||
| Tobias |
|
||
| 18.01.2008, 09:01 | Auf diesen Beitrag antworten » | ||
| JROppenheimer | sorry, ich hab gepennt ... 1. Irgendwie ist mir das "Zyklus" in dem Satz total entgangen. 2. Mein Beispiel war totaler Käse. die Kante, die dann günstiger wird, würde ohnehin nicht in den MST aufgenommen ... das ist mit genau DANN eingefallen, als ich den PC gerade ausgemacht hatte ... Jetzt hab ich nur ein Problem mit der Laufzeit. Sicher, dass das in O(|V|) Ich hab mal versucht GANZ am Anfang meines Studiums Kruskal zu implementieren und bin genau an dem Zyklusding gescheitert. Wie implementiere ich denn effektiv die Abfrage nach Zyklen!? |
||
| 18.01.2008, 14:09 | Auf diesen Beitrag antworten » | ||
| Tobias | Hier musst du dich daran erinnern, dass der Zyklus durch den eindeutigen Weg von u nach v im bereits vorhandenen MST beschreiben wird, zu dem zusätzlich die Kante uv zugefügt wird. Was du also tun musst, ist den Weg von u nach v im Baum zu finden. Und das ist auf jeden Fall in O(|V|) machbar. Wichtig ist dafür die Erkenntnis, dass für jeden Baum stets gilt: |E| = |V| - 1 |
||
| 18.01.2008, 15:24 | Auf diesen Beitrag antworten » | ||
| JROppenheimer | AAAAACH klasse. Ich arbeite also eigendlich nur am MST und mache mir da zu nutze, dass eben diese minimale Spannbaum in O(|E|) bearbeitbar ist?! Müsste ich den Graphen durchsuchen, dann wäre das aufwendiger, oder?! |
||
| 18.01.2008, 15:41 | Auf diesen Beitrag antworten » | ||
| Tobias | Was du ja willst ist der Weg von u nach v im MST. Im Graphen G gibt es evt. mehr als einen Weg von u nach v. Deshalb bringt dir das Suchen dort garnichts . |
||
| 18.01.2008, 16:11 | Auf diesen Beitrag antworten » | ||
| JROppenheimer | klasse, ich danke DIr, bist ne riesen hilfe! |
||
|
|
