Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:graphen:zpg:minimalspanningtree:kruskal:start [07.12.2022 11:51] – [Beispiel] 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 5: / Zeile 5: @@
 === (A1) ===
-Untersuche im Graphentester den Algorithmus "MST (Kruskal)" zur Bestimmung des minimalen Spannbaums im Graphentester auf die Karte der größten Städte in Deutschland (02_deutschlandkarte.csv im Ordner 08_minimalspanningtree).
+Untersuche im Graphentester den Algorithmus "MST (Kruskal)" zur Bestimmung des minimalen Spannbaums  auf der Karte der größten Städte in Deutschland (''02_deutschlandkarte.csv'' im Ordner ''08_minimalspanningtree'').
   * 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.
-  * Verhgleiche deine Beschreibung mit den Musterlösung (unten) und bewerte, ob du das Vorgehen richtig nachvollzogen hast.
+  * Vergleiche deine Beschreibung mit den Musterlösung (unten) und bewerte, ob du das Vorgehen richtig nachvollzogen hast.
 ++++ Beschreibung des Algorithmus von Kruskal |
+==== Beschreibung des Algorithmus (Kruskal) ====
 Der Algorithmus verfolgt die Idee, immer die kürzeste Kante des Graphen dem Baum hinzuzufügen, wenn dadurch nicht ein Zyklus entsteht und die Kante damit überflüssig ist. Es entstehen dabei zunächst viele einzelne Bäume (ein Wald), die sukzessive zu einem einzigen Baum zusammengeführt werden. Um die Zyklen leicht erkennen zu können, werden die Knoten jedes einzelnen Baums in einer eigenen Farbe eingefärbt.
 Zunächst werden die Kanten also nach ihrem Gewicht sortiert und dann für jede Kante folgende Regeln beachtet:
@@ Zeile 25: / Zeile 28: @@
 ==== Beispiel ====
-| {{ :faecher:informatik:oberstufe:graphen:zpg:minimalspanningtree:kruskal:300px-prim_algorithm_0.svg.png?220 |}}|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. |
+((Quelle https://de.wikipedia.org/wiki/Algorithmus_von_Kruskal, Bilder von [[https://commons.wikimedia.org/wiki/User:Alexander_Drichel|Alexander Drichel]], Lizenz [[https://creativecommons.org/licenses/by-sa/3.0|CC-BY-SA 3.0]]))
-| {{ :faecher:informatik:oberstufe:graphen:zpg:minimalspanningtree:kruskal:300px-kruskal_algorithm_1.svg.png?220 |}}|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.)  |
-| {{ :faecher:informatik:oberstufe:graphen:zpg:minimalspanningtree:kruskal:300px-kruskal_algorithm_2.svg.png?220 |}}|Nun ist CE die kürzeste, noch nicht ausgewählte Kante. Da sie mit AD keinen Kreis bildet, wird sie nun ausgewählt.  |
+<callout>
-| {{ :faecher:informatik:oberstufe:graphen:zpg:minimalspanningtree:kruskal:300px-kruskal_algorithm_3.svg.png?220 |}}|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.  |
+<grid>
-| {{ :faecher:informatik:oberstufe:graphen:zpg:minimalspanningtree:kruskal:300px-kruskal_algorithm_4.svg.png?220 |}}|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 sm="3">
-| {{ :faecher:informatik:oberstufe:graphen:zpg:minimalspanningtree:kruskal:300px-kruskal_algorithm_5.svg.png?220 |}}|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.  |
+{{ 300px-prim_algorithm_0.svg.png?220 |}}
-| {{ :faecher:informatik:oberstufe:graphen:zpg:minimalspanningtree:kruskal:300px-kruskal_algorithm_6.svg.png?220 |}}|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>
+<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  |}}
 === (A2) ===
-Übersetze die Beschreibuung aus Aufgabe 1 in Pseudocode.
+Übersetze die Beschreibung aus Aufgabe 1 in Pseudocode.
 ++++ Pseudocode Kruskal  |