Wenn ich Aufgabe 4.5.10 versuche so zu lösen klappt das nicht.
Mir fehlt da die Kantenkontraktion.
Was meinst du mit Kantenkontraktion ?
Also wenn du dir die Lösung mal ansiehst ist dort ja in Abbildung 4.9 die favorisierten Kanten der einzelnen Knoten eingezeichnet.
Mal als Übersicht:
{1,2} Knoten 1 hat zu Knoten 2 das minimalste Kantengewicht von 2 daher diese Markieren
{2,4} Knoten 2 hat zu Knoten 4 das minimalste Kantengewicht von 2 daher dieses Markieren (es könnte nun auch von Knoten 2 {2,1} gewählt werden
{4,2} Knoten 4 hat zu Knoten 2 bzw. 8 das minimalste Kantengewicht, ich hab nun auch nirgends gelesen was nun zu bevorzugen ist, da es für diesen Baum grundsätzlich egal ist, gehe davon aus das es hierbei irrelevant welche Kante genommen wird da kein Kreis entsteht.
{8,4}, {16,8}, {26,13},{17,1},{19,1},{23,1},{29,1},{24,12},{12,6},{6,3},{3,6}, {18,9},{27,9},{9,18},
{5,10},{20,10},{10,5},{25,5}, {15,30}, {30,15}, {28,14}, {14,7},{21,7},{7,14},{22,11}, {11,22},{26,13},{13,26}
Das könnte man nun noch von 1 aufsteigend ordnen denn erhielte man die Tabelle aus der Lösung.
Wenn man dies nun also gemacht hat, denn sind die entstandenen Zusammenhangskomponenten noch nicht verbunden.
Es muss aber verbunden sein da es ja sonst kein minimal aufspannender Baum ist.
Also werden noch die Kanten: {3,1} (=3), {9,3} (=3), {15,5} (=3), {5,1} (=5), {7,1} (=7), {13,1} (=13) hinzugefügt.
Die Zahl in () soll das Kantengewicht sein.
