TU Wien Diskussion:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 316
Der Link verweist auf den Algorithmus von Djikstra, sollte aber zur bestimmung des minimalgerüst der Algorithmus von Kruskal (Skritp s33) verwendet werden?
Du hast recht (ich hatte noch nicht die Zeit, den Link näher zu überprüfen - stecke grad in der Vorbereitung für morgen).
Wenn wir auf http://de.wikipedia.org/wiki/Algorithmus_von_Kruskal gucken, lesen wir:
Der Algorithmus von Kruskal ist ein Algorithmus der Graphentheorie mit dessen Hilfe man minimale Spannbäume in zusammenhängenden, ungerichteten, kantengewichteten Graphen berechnen kann.
Der Dijkstra-Algorithmus hingegen, so lesen wir in http://de.wikipedia.org/wiki/Algorithmus_von_Dijkstra
dient der Berechnung eines kürzesten Pfades zwischen einem Startknoten und einem beliebigen Knoten in einem kantengewichteten Graphen.
Ich glaube daher auch, dass hier der Algorithmus von Kruskal zum Tragen kommt. --Mnemetz 16:20, 5. Dez 2005 (CET)
Achtung! Deine Lösung ist zwar richtig, hast sie aber falsch gezeigt!! Die 6er fallen automatisch weg da der Algorithmus nach |V|-1 Schritten terminiert! --Deez 11:18, 7. Dez 2005 (CET)
|V| ist die Mächtigkeit der Knotenmenge. Wie würdest Du Deine Behauptung begründen können, wenn b,l das Gewicht 10 hätte? --Mnemetz 11:31, 7. Dez 2005 (CET)
Ist gar nicht meine Behauptung sondern von Kruskal, der diesen Algorithmus auch bewiesen hat. Der Algorithmus wird genau dann abbgebrochen, wenn i = |V|-1 ist (Skript S33). Nach diesen |V|-1 Schritten muss das minimalgerüst vorliegen. (Ansonsten wär der Algorithmus nicht allgemeingültig) Somit fallen die 6er automatisch weg, nicht weil sie einen Kreis bilden, sondern weil der Algorithmus schon vorher terminiert. --Deez 11:41, 7. Dez 2005 (CET)
Ersetze mal das Gewicht der Kante b-l durch 9. Ich glaube nicht, dass der Algorithmus dann schon bei 6 terminiert. Wo steht auf S. 33 ein Beleg für Deine Behauptung? --Mnemetz 14:56, 7. Dez 2005 (CET)