TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2025W/Beispiel 324

Man bestimme im folgenden Graphen $H$ für den angegebenen Wert von $x=4$ mit Hilfe des Kruskalalgorithmus einen minimalen und einen maximalen spannenden Baum.

Dieses Beispiel ist als solved markiert. Ist dies falsch oder ungenau? Aktualisiere den Lösungsstatus (Details: Vorlage:Beispiel)

Aufgaben mit gleicher Angabe mit anderen $x$ Werten verfügbar unter TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2025W/Beispiel 322, TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2025W/Beispiel 323 und TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2025W/Beispiel 325

Hilfreiches

Kruskal-Algorithmus

Lösungsvorschlag von Windschütze

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