TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 315

Aus VoWi
Zur Navigation springen Zur Suche springen

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!![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!

Bsp206 1.png

Theorie[Bearbeiten]

Siehe Theorie vom 06.12.!

Lösungsvorschlag von mnemetz (graphisch)[Bearbeiten]

Zuerst die 1er-Kanten

Bsp206 2.png

Windschütze

Nun die 2er-Kanten

Bsp206 3.png

Die 3er-Kanten

Bsp206 4.png

Die 4er-Kanten

Bsp206 5.png

Die restlichen Kanten

Bsp206 6.png

Eine im Informatikforum gepostete Lösung deckt sich mit meiner:

206 al.png


Für den maximal spannenden Baum beginnt man mit der Kante 8, dann 7 usw.

Hapi

Lösungsvorschlag von Windschütze[Bearbeiten]

Gilt für x=4,sprich Beispiel 219 im WS 2008.

Minimaler Spannender Baum (beginnend bei 1):

Minispannbaum.jpg

Maximaler Spannender Baum (beginnend bei 8, ergeben sich 2 Möglichkeiten):

Maxispannbaum.jpg

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