Blatt 12
Ronja Düffel 
Do 12:00-14:00
Gruppe 4

12.3

Nach Algorithmus von PRIM:
S = {a}; V = {a, b, c, d, e, f, g}
kreuzende Kanten:
länge(a,b) = 1; länge(a,g) = 6; länge(a,f) = 7
=> wähle Kante (a,b)
S = {a,b}; 
kreuzende Kanten:
länge(a,f) = 7; länge(g,e) = 2; länge(b,g) = 5; länge(b,c) = 9
=> wähle Kante (b,g)
S = {a,b,g}

usw.... bis S = V. Die Reihenfolge in der die Kanten ausgewählt werden ist dann:
(a,b); (b,g); (g,e); (g,d); (a,f); (b,c)

Nach Algorithmus von KRUSKAL:
Kanten:
länge(a,b) = 1		=> wähle (a,b)
länge(g,e) = 2		=> wähle (g,e)
länge(g,d) = 3		=> wähle (g,d)
länge(e,d) = 4		Kante schließt Kreis
länge(b,g) = 5		=> wähle (b,g)
länge(a,g) = 6		Kante schließt Kreis
länge(a,f) = 7		=> wähle (a,f)
länge(f,e) = 8		Kante schließt Kreis
länge(b,c) = 9		=> wähle (b,c)
länge(c,d) = 10

Auswahlreihenfolge der Kanten:
(a,b); (g,e); (g,d); (b,g); (a,f); (b,c)