TU Wien:Mathematik 1 UE (diverse)/Übungen WS06/Beispiel 206
Zur Navigation springen
Zur Suche springen
Angabe[Bearbeiten | Quelltext bearbeiten]
Man bestimme im folgenden Graphen H mit Hilfe des Kruskalalgorithmus einen minimalen und maximalen spannenden Baum. (nur minimaler verlangt => http://www.algebra.tuwien.ac.at/institut/inf/inf_panholzer/index1_WS05.html
Theorie[Bearbeiten | Quelltext bearbeiten]
Siehe Theorie vom 06.12.!
Lösungsvorschlag von mnemetz (graphisch)[Bearbeiten | Quelltext bearbeiten]
Zuerst die 1er-Kanten
Nun die 2er-Kanten
Die 3er-Kanten
Die 4er-Kanten
Die restlichen Kanten
Eine im Informatikforum gepostete Lösung deckt sich mit meiner:
Für den maximal spannenden Baum beginnt man mit der Kante 8, dann 7 usw.
Hapi