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)$ .

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Skizze[Bearbeiten | Quelltext bearbeiten]

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

Lösungsvorschlag von deez[Bearbeiten | Quelltext 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 | Quelltext bearbeiten]

Gerüste[Bearbeiten | Quelltext 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):

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

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

Und eine "Schlange" :-)

Minimalgerüst[Bearbeiten | Quelltext 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).