| Die letzten 10 Beiträge |
| JROppenheimer |
klasse, ich danke DIr, bist ne riesen hilfe! |
| 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 . |
| 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?! |
| 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 |
| 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!? |
| Tobias |
| Zitat: |
| Aus diesem Zyklus musst du nun die schwerste Kante herausnehmen um wieder einen MST zu erhalten. |
|
| 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"?
JROppenheimer hat dieses Bild (verkleinerte Version) angehängt:
|
| 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. |
| 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 |
| 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! |
| Es sind weitere Beiträge zu diesem Thema vorhanden. Klicken Sie hier, um sich alle Beiträge anzusehen. |
|
|
