Graphen sind Grundlage vieler klassischer aber auch moderner
Problemstellungen. So ist es kaum verwunderlich, dass unzählige
Algorithmen existieren um diese Problemstellungen mal mehr mal
weniger effizient zu lösen.
Das Applet BiPartGraph visualisiert einen Algorithmus zum Lösen
eines Matchingproblems auf Bipartiten Graphen.
Ein paar Grundlagen zum Verständnis.
Graphen:
Ein ungerichteter Graph G = (V,E) besteht aus einer Menge von Knoten V
und einer Menge von Kanten E, wobei E ist Teilmenge aus V x V.
Bipartite Graphen:
Ein Graph heißt bipartit, wenn man ihn in 2 disjunkte Knotenmengen
aufteilen kann, so dass es keine Kanten zwischen 2 Knoten innerhalb
einer dieser Teilmengen gibt. Somit besitzen Bipartite Graphen keine
Zyklen ungerader Länge. Daher sind Algorithmen zur Konstruktion von
maximalen Matchings weniger komplex.
Matching:
Als Matching M (dt. Paarung) eines Graphen G bezeichnet man eine
Teilmenge von Kanten, so dass keine 2 Kanten aus M einen gemeinsamen
Endpunkt haben.
BiPartGraph Applet starten
Sourcecode: biGraph-0.3.1.tar.gz (85 KB)
Die Oberfläche des Applets gliedert sich in 4 Teile. Der linke obere Teil zeigt den zu betrachtenden bipartiten Graphen. Es besteht die Möglichkeit Kanten durch Mausklicks hinzuzufügen. Weiterhin wird zur Laufzeit des Algorithmusses die Wirkung auf den Graphen (gerade betrachtete Knoten, schon gematchte Kanten, etc.) in diesem Panel dargestellt. Im zweiten Teil (unten links) ist der Algorithmus selbst als C++ Quelltext zu sehen. Während der Abarbeitung zeigt ein Markierungsbalken die aktuelle Zeile, in der sich der Algorithmus befindet, an. Der dritte Teil (rechts unten) wird für die Darstellung von wichtigen Datenstrukturen zur Laufzeit verwendet. Die Ausgabe von Arrays erfolgt in Tabellenform. Der vierte Teil der Oberfläche dient zur Bedienung des Programms. Das Eingabe-Tab bietet die Möglichkeit neue Graphen mit den entsprechenden Knotenmengen zu generieren. Weiterhin können hier Kanten zufällig unter Beachtung eines frei wählbaren Wahrscheinlichkeitsfaktors erzeugt werden. Im Matching-Tab wird der Ablauf des Algorithmusses kontrolliert. Durch entsprechende Buttons kann die Ausführung gestartet und angehalten werden. Weiterhin gibt es einen Lauf-Modus der eine langsame automatische Abarbeitung bewirkt und einen schnellen Vorlauf, durch den die Abarbeitung möglichst schnell, unter Verzicht auf Visualisierungen, beendet werden kann.