Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:graphen:zpg:minimalspanningtree:kruskal:start [07.12.2022 12:28] – Frank Schiebel
+++ faecher:informatik:oberstufe:graphen:zpg:minimalspanningtree:kruskal:start [27.09.2024 13:26] (aktuell) – [Algorithmus von Kruskal zur Bestimmung eines MST] Marco Kuemmel
@@ Zeile 8: / Zeile 8: @@
   * Versuche herauszufinden, wie der Algorithmus funktioniert, indem du ihn Schritt für Schritt ausführst.
-  * Welche Situation muss vermieden werden? Fällt dir dafür eine einfache Lösung ein.
+  * Welche Situation muss vermieden werden? Fällt dir dafür eine einfache Lösung ein?
   * Beschreibe deinen so gefundenen Algorithmus in einem kurzen Text.
   * Vergleiche deine Beschreibung mit den Musterlösung (unten) und bewerte, ob du das Vorgehen richtig nachvollzogen hast.
@@ Zeile 34: / Zeile 34: @@
 <col sm="3">
 {{ 300px-prim_algorithm_0.svg.png?220 |}}
+</col>
+<col sm="9">
 Dies ist der Graph, zu dem der Algorithmus von Kruskal einen minimalen Spannbaum berechnen wird. Die Zahlen bei den einzelnen Kanten geben das jeweilige Kantengewicht an. Zu Beginn ist noch keine Kante ausgewählt.
+</col>
+</grid>
+</callout>
+<callout>
+<grid>
+<col sm="3">
 {{ 300px-kruskal_algorithm_1.svg.png?220 |}}
+</col>
+<col sm="9">
 Die Kanten AD und CE sind die kürzesten (noch nicht ausgewählten) Kanten des Graphen. Beide können ausgewählt werden. Hier wird zufällig AD ausgewählt. (Dass diese keinen Kreis bildet, ist im ersten Schritt selbstverständlich.)
+</col>
+</grid>
+</callout>
+<callout>
+<grid>
+<col sm="3">
 {{ 300px-kruskal_algorithm_2.svg.png?220 |}}
+</col>
+<col sm="9">
 Nun ist CE die kürzeste, noch nicht ausgewählte Kante. Da sie mit AD keinen Kreis bildet, wird sie nun ausgewählt.
+</col>
+</grid>
+</callout>
+<callout>
+<grid>
+<col sm="3">
 {{ 300px-kruskal_algorithm_3.svg.png?220 |}}
+</col>
+<col sm="9">
 Die nächste Kante ist DF mit Länge 6. Sie bildet mit den schon gewählten Kanten keinen Kreis und wird deshalb ausgewählt.
+</col>
+</grid>
+</callout>
+<callout>
+<grid>
+<col sm="3">
 {{ 300px-kruskal_algorithm_4.svg.png?220 |}}
+</col>
+<col sm="9">
 Jetzt könnten die Kanten AB und BE, jeweils mit Länge 7, ausgewählt werden. Es wird zufällig AB gewählt. Die Kante BD wird rot markiert, da sie mit den bis jetzt gewählten Kanten einen Kreis bilden würde und somit im weiteren Verlauf des Algorithmus nicht mehr berücksichtigt werden muss.
+</col>
+</grid>
+</callout>
+<callout>
+<grid>
+<col sm="3">
 {{ 300px-kruskal_algorithm_5.svg.png?220 |}}
+</col>
+<col sm="9">
 BE ist nun mit Länge 7 die kürzeste der noch nicht ausgewählten Kanten und da sie mit den bisher gewählten keinen Kreis bildet, wird sie ausgewählt. Analog zur Kante BD im letzten Schritt werden jetzt die Kanten BC, DE und FE rot markiert.
+</col>
+</grid>
+</callout>
+<callout>
+<grid>
+<col sm="3">
 {{ 300px-kruskal_algorithm_6.svg.png?220 |}}
+</col>
+<col sm="9">
 Als letzte wird die Kante EG mit Länge 9 ausgewählt, da alle kürzeren bzw. gleich langen Kanten entweder schon ausgewählt sind oder einen Kreis bilden würden. Die Kante FG wird rot markiert. Da nun alle nicht ausgewählten Kanten einen Kreis bilden würden (sie sind rot markiert) ist der Algorithmus am Ende angelangt und der grüne Graph ist ein minimaler Spannbaum des zugrundeliegenden Graphen.
+</col>
+</grid>
+</callout>
 ----
 {{:aufgabe.png?nolink  |}}