Überführung der Ausgangssituation in einen Graph

Die Ausgangssituationen sollten den Schülerinnen und Schülern in verschiedener Form angeboten werden. Denkbar sind Abbildungen (z.B. Landkarten), textuelle Beschreibungen der Situation (z.B. Freundschaftsbeziehungen) oder tabellarische Darstellungen (z.B. Entfernungstabellen). Die Überführung der Ausgangssituation in den Graphen kann dann entweder unplugged auf einem Blatt Papier erfolgen oder durch die Unterstützung des Graphen-Testers erfolgen.

Im Graphen-Tester wählt man den Bearbeitungsmodus. Dort wählt man aus, ob die Kanten gerichtet und/oder gewichtet sein sollen (A). Gerichtete Kanten werden als Pfeile dargestellt, ungerichtete als Verbindungslinien. Bei gewichteten Kanten wird das Gewicht der Kanten zusätzlich angezeigt.

Dient eine Abbildung als Ausgangssituation, fügt man als erstes das Bild als Hintergrund ein. Das Bild wird dabei in den Unterordner images des Graphen-Testers kopiert (B).

Neue Knoten setzt man durch einen Linksklick in die Darstellungsfläche. Man kann die Knoten verschieben, indem man sie mit der Maus in der Mitte "anfasst" und an die neue Stelle zieht. Zieht man mit der Maus vom Rand eines Knotens eine Verbindung zu einem anderen Knoten wird eine neue Kante erstellt. Mehrere Kanten von einem Knoten zu einem anderen (Multigraphen) sind nicht möglich.

Bildquelle: Graphentester von ZPG Informatik [CC BY-NC-SA 3.0 DE], aus 2_unterrichtsverlauf.odt

Ein Rechtsklick mit der Maus öffnet ein Kontextmenü zum ausgewählten Element (C). Dort kann das ausgewählte Element gelöscht, das Gewicht einer Kante geändert oder ein Infotext zu einem Knoten (z.B. Name einer Stadt oder einer Person) erfasst werden. Dieser Infotext dient nur der Übersicht und der besseren Lesbarkeit des Ablaufprotokolls bei der Simulation eines Algorithmus. Wenn das Gewicht der Kanten die geometrische Entfernung zwischen den Knoten repräsentiert, können alle Gewichte durch den Button "Distanzen bestimmen" berechnet werden. Dabei wird jeweils der Abstand der Knoten in Pixeln bestimmt.

Um für bestimmte Anwendungssituationen eine optimale Darstellung direkt beim Laden des Graphen zu gewährleisten, kann die Standarddarstellung der Knoten (leere Kreise, Knoten sind durchnummeriert oder der Wert eines Knotens wird angezeigt) und ihre Größe voreingestellt werden (D). Während der Simulation eines Algorithmus kann die Darstellung aber jederzeit verändert werden.

Vor dem Speichern des Graphen kann man noch wählen, ob der Graph als Adjazenzmatrix oder Adjazenzliste gesichert werden soll (E). Den Unterschied sieht man nur, wenn man die gespeicherte csv-Datei mit einem Texteditor betrachtet. In der csv-Datei kann man außerdem die Farbeinstellung der Knoten und Kanten verändern:

# Kantenfarben: RGB-Hexcode (z.B. FF0000) oder invisible
# Reihenfolge: normale Kanten, markierte Kanten, gelöschte Kanten
edgeColor,invisible,FF0000,A0A0A0
# Knotenfarben: RGB-Hexcode (z.B. FF0000) oder invisible
# Reihenfolge: nichts, markiert, besucht, markiert + besucht
# Es müssen mind. 12 Farben angegeben werden.
vertexColor,A0A0A0,FF0000,FFFF00,00FFFF,AA00AA,888800,008888,880088,00a0FF,a400FF,FFa400,FF00a4,00FFa4,a4FF00

Dabei müssen mindestens 12 Farben für die Knoten angegeben werden. Die Farbe "invisible" sorgt dafür, dass eine Kante überhaupt nicht gezeichnet wird. Dies ist z.B. bei größeren vollständigen Graphen für das Traveling Salesman Problem notwendig.

Unterrichtsverlauf: Herunterladen [odt][298 KB]

Weiter zu Froschperspektive vs. Adlerperspektive