TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 315
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
Contents
Achtung!![edit]
Für Gruppen Mo, Mi WS07:
Mo, 3.12.: 214, 220, 222 (Anmerkung zu Bsp. 214: ergänze w(e)=6 für die fehlende Bewertung bei einer Kante.)
Mi, 5.12.: 214, 221, 223 (Anmerkung zu Bsp. 214: ergänze w(e)=7 für die fehlende Bewertung bei einer Kante.)
Der hier gezeigte Lösungsvorschlag gilt nur für w(e)=5!
Theorie[edit]
Siehe Theorie vom 06.12.!
Lösungsvorschlag von mnemetz (graphisch)[edit]
Zuerst die 1er-Kanten
Windschütze
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
Lösungsvorschlag von Windschütze[edit]
Gilt für x=4,sprich Beispiel 219 im WS 2008.
Minimaler Spannender Baum (beginnend bei 1):
Maximaler Spannender Baum (beginnend bei 8, ergeben sich 2 Möglichkeiten):
Nützliche Hilfe: Wikipedia: Beispiel Kruskal Algorithmus
Windschütze =)
Hinweis: Bei x und der danebenliegenden 4er Kante gibt es zwei mögliche Lösungen.
Entweder x oder 4 in den spannenden Baum miteinbeziehen.
Daher auch die rote und grüne Linie doppelt bei der obigen Lösung!
~Mario