TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen WS18/Beispiel 311

Aus VoWi
Wechseln zu: Navigation, Suche
Dieses Beispiel ist von WS18. Entspricht die Angabe auf dieser Seite der Angabe von SS19?

Gegeben sei ein ungerichteter, zusammenhängender, bewerteter Graph G = (V, E, w) mit V = {a,b,c,d,e,f,g,h,i,j,k,l} durch seine Kanten / Bewertungen:

ab/3, ac/2, ad/7, ae/2, bd/4, bf/8, bk/6, bl/1, cf/2, ck/5, de/1,
df/6, dg/9, dh/6, dj/1, ef/2, ei/1, fg/2, gh/4, fk/6, gi/6, hk/7.

(a) Man gebe drei verschiedene Gerüste von G an.

(b) Man bestimme ein Minimalgerüst T von G und dessen Gesamtlänge w(T).

Skizze[Bearbeiten]

Skizze, aktualisiert. --Mnemetz 13:24, 6. Dez 2005 (CET)

Bsp180 1.png




Lösungsvorschlag von deez[Bearbeiten]

Also ich hab die Kanten geordnet: bl/1, de/1, dj/1, ei/1,

ac/2, ae/2 cf/2, ef/2, fg/2,

ab/3,

bd/4, gh/4,

ck/5,

bk/6, df/6, dh/6, fk/6, gi/6,

hk/7 ad/7

bf/8,

dg/9,

Und bin dann auf folgenden Graph gekommen: bl/1, de/1, dj/1, ei/1,

ac/2, ae/2 cf/2, ef/2, fg/2,

ab/3,

bd/4, gh/4,

ck/5

und bin dabei nie auf einen Kreis gestoßen. Ist alles zusammen falsch, da ich irgndwie von einem gerichteten Graph ausgegangen bin!! Tut mir sehr leid!

Lösungsvorschlag von mnemetz[Bearbeiten]

Gerüste[Bearbeiten]

Ein Spannbaum (synonym auch aufspannender Baum oder kürzer spannender Baum; englisch spanning tree) ist in der Graphentheorie ein Teilgraph eines ungerichteten Graphen, der ein Baum ist und alle seine Knoten enthält. Spannbäume existieren nur in zusammenhängenden Graphen.

Einen Teilgraphen, der in (nicht notwendigerweise zusammenhängenden) Graphen für jede Komponente einen Spannbaum ergibt, nennt man Gerüst, Spannwald, aufspannender Wald oder kürzer spannender Wald. In zusammenhängenden Graphen sind Gerüst und Spannbaum also identische Begriffe, während Spannbäume für unzusammenhängende Graphen nicht definiert sind.

In kantengewichteten Graphen lässt sich als Gewicht eines Graphen die Summe seiner Kantengewichte definieren. Ein Spannbaum bzw. ein Gerüst heißt minimal, wenn kein anderer Spannbaum bzw. kein anderes Gerüst in demselben Graphen mit geringerem Gewicht existiert. Häufig kürzt man minimaler Spannbaum auch mit MST (Abkürzung des englischen Begriffs Minimum Spanning Tree) ab. Statt minimales Gerüst sagt man auch Minimalgerüst.

Anders gesagt: Ein Gerüst T_G = \langle V',E' \rangle eines Graphen G = \langle V,E \rangle liegt als Teilgraph von G vor, wenn es ein Baum ist und V'=V erfüllt, d.h. die beiden Knotenmengen sind gleich gross (= die Anzahl der Knoten).


Der ganze Graph (Ohne Gewichte, Punktbezeichnungen - die sind nun nicht wichtig):


Bsp180 3 1.png


Drei Lösungen, die alle Kreise eliminieren und die Anzahl der Knoten gleich halten. Ich habe der Einfachheit halber zusammenhängende Gerüste erstellt!


Bsp180 3 2.png


Ach leck mich doch ... eine Kante umstellen :-)


Bsp180 3 3.png


Und eine "Schlange" :-)


Bsp180 3 4.png

Minimalgerüst[Bearbeiten]

Es wird der Algorithmus von Kruskal verwendet. Zunächst sortierte ich die Kanten nach ihrer Bewertung:

  1   (b,l)  (d,e)  (d,j)  (e,i)
  2   (a,c)  (a,e)  (c,f)  (e,f)  (f,g)  
  3   (a,b)  
  4   (b,d)  (g,h)
  5   (c,k)  
  6   (b,k)  (d,f)  (d,h)  (f,k)  (g,i)  
  7   (a,d)  (h,k)
  8   (b,f)  
  9   (d,g)


Dann legen wir mal die 1-er Kanten aneinander - sie bilden keinen Kreis. Bitte, im Normalfall geht man von einer leeren Menge aus - die Zeichnungen zeigen alles (hat verarbeitungstechnische Gründe).


Bsp180 2 1.png


Nun legen wir die 2-er Kanten aneinander. Da ein Kreis gebildet wird, entfernen wir (a,e).


Bsp180 2 2.png


Der nächste Schritt ist klar. (a,b) wird hinzugefügt und es kann bleiben - kein Kreis entsteht.


Bsp180 2 3.png


Nun fügen wir die 2 Vierer-Kanten an. (b,d) bildet einen Kreis und wird daher ausgeschlossen.


Bsp180 2 4.png


Nun die 5-er Kante. Wiederum wird kein Kreis gebildet


Bsp180 2 5.png


Alle 6-er Kanten bilden einen Kreis => ausgeschlossen!


Bsp180 2 6.png


Wie man leicht sehen kann, bilden die Kanten 7-9 jeweils Kreise ...


Bsp180 2 7.png


Das Minimalgerüst ist also:


Bsp180 2 8.png


Die Länge des Minimalgerüsts beträgt 24.