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

From VoWi
< TU Wien:Algebra und Diskrete Mathematik UE (diverse)‎ | Übungen SS19
Revision as of 16:47, 7 March 2019 by Gittenborg (talk | contribs) (Gittenborg verschob die Seite TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen WS18/Beispiel 315 nach TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 315 und überschrieb dabei eine Weiterleitung: versch…)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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

Bsp206 1.png

Theorie[edit]

Siehe Theorie vom 06.12.!

Lösungsvorschlag von mnemetz (graphisch)[edit]

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[edit]

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