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

Achtung!!

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

Siehe Theorie vom 06.12.!

Lösungsvorschlag von mnemetz (graphisch)

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

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