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

Aus VoWi
Wechseln zu: Navigation, Suche

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.