TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 320
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
{{Beispiel|1= Angabetext }}
oder
{{Beispiel| Angabetext }}
zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)
{{Beispiel|status=solved|1= Angabetext }}
Achtung!![Bearbeiten | Quelltext bearbeiten]
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[Bearbeiten | Quelltext bearbeiten]
Siehe Theorie vom 06.12.!
Lösungsvorschlag von mnemetz (graphisch)[Bearbeiten | Quelltext bearbeiten]
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[Bearbeiten | Quelltext bearbeiten]
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