Suche

VINA


Der Zweck dieses Programmes ist der Einsatz in der Lehre zur Veranschaulichung der Arbeitsweise einiger grundlegender Algorithmen aus der Graphentheorie bzw. der kombinatorischen Optimierung. Das Programm ist weitgehend selbsterklärend. Die Algorithmen sind an ausgewählten Beispielen aus der Vorlesung getestet worden. In der aktuell vorliegenden Version sind folgende Algorithmen implementiert:
  • kürzeste Wege: Dijkstra 
  • minimaler aufspannendner Baum: Prim 
  • maximaler Fluss: Ford-Fulkerson; Goldberg-Tarjan 
  • maximales Matching: Edmonds; Galais-Edmonds-Zerlegung; Ungarischer Algorithmus 
  • TSP: nearest insertion; farthest insertion; 2-Austausch 
  • Minimale Schnitte: Algorithmus von Stoer und Wagner 
  • Kantenfärbung: Ein Verfahren von Berge und Fournier


Historie: 

Dieses Programm ist aus verschiedenen studentischen Projekten hervorgegangen.

Im ersten Anlauf (Maria Schmaus, 2005) wurde das Konzept samt Oberfläche (erzeugen, darstellen, ändern von Graphen) erstellt  und die Algorithmen zu Dijkstra, Prim, Ford-Fulkerson, nearest insertion, farthest insertion, 2-Austausch implementiert.

Martin Mayr (2007) hat danach die Matching-Algorithmen implementiert und einige Darstellungsmöglichkeiten verbessert.

Michael Rupp (2008) hat den Flussalgorithmus von Goldberg-Tarjan implementiert und die Darstellung erneut weiter verbessert, so dass sich mittlerweile abzeichnet, welche Informationen beim Ablauf eines entsprechenden Algorithmus sinnvoll dargestellt werden kann.

Matthias Tinkl (2012) hat den Quellcode und die Implementierungen gründlich überarbeitet.

Jochen Schippl (2014) hat den Algorithmus von Stoer und Wagner zur Bestimmung minimaler Schnitte in ungerichteten Graphen implementiert.

Julia Andrea Schmidt (2014) hat ein konstruktives Verfahren von Berge und Fournier zur Kantenfärbung in Multigraphen implementiert.

Zukunft:

Gerne kann das Programm im Rahmen zukünftiger Projekte weiter ausgebaut und von der Darstellung her vereinheitlicht werden.  Im Bereich der Flusstheorie und des TSP sollten noch Korrekturen und Verbesserungen in der Darstellung vorgenommen werden.

Gebrauch:

Die unten aufgeführte zip-Datei herunterladen, entpacken und das Programm start_vina.bat aufrufen.

Graphen können selbst erzeugt werden oder aus dem Ordner EXAMPLES geöffnet werden. Viel Spaß beim Testen.

  • VINA -  (rar, 3871 KB)