Klemens Böhm

Dennis Kobert

Im Folgenden eine kurze Beschreibung der Aufgabenstellung, die ausreichen sollte für einen ersten Eindruck. Weiter unten dann eine ausführlichere/vollständige Beschreibung.

PSE-Aufgabenstellung: "Generierung von totalen Kolorierungen von Graphen"

Die Aufgabe besteht darin, ein Werkzeug zu entwickeln, dass die Total Coloring Conjecture in der Graphentheorie betrachtet.

Dies umfasst die folgenden Schritte:

1. Graphenbearbeitung:
Sie ermöglichen das Erstellen von Graphen, sei es mit Hilfe eines Graph-Editors, sei es mit einer Textdatei, die den Graph spezifiziert.

2. ILP-basierte totale Kolorierung:
Sie verwenden einen existierenden ILP-Solver, um eine totale Kolorierung des Graphen mit bestimmten Eigenschaften zu finden. Ein Beispiel für eine Eigenschaft der gewünschten Kolorierung ist die minimale Verwendung einer bestimmten Farbe.

3. Visuelle Darstellung:
Sie stellen die gefundene Kolorierung visuell ansprechend dar, unter Verwendung geeigneter Werkzeuge.

Weitere Schritte sind die folgenden:

(a) Erzeugung zufälliger Graphen:
Sie ermöglichen die zufällige Erzeugung von Graphen mit vorgegebenen Eigenschaften, für die der ILP-Solver dann totale Kolorierungen finden soll.

(b) Vergleich von ähnlichen Graphen:
Sie ermöglichen die Erstellung und Kolorierung von Paaren von Graphen mit minimalen Unterschieden, für die der ILP-Solver maximal ähnliche totale Kolorierungen finden soll.

(c) Abspeichern von Ergebnissen:
Sie schaffen die Möglichkeit, Graphen, Paare von Graphen und zugehörige Kolorierungen zusammen mit Freitextannotationen abzuspeichern.

Diese Aufgabenstellung ermöglicht Ihnen neben dem Erreichen der klassischen Lernziele das Arbeiten mit ILP-Solvern. Nach Möglichkeit sollen auch existierende Werkzeuge für die Graphenerstellung und -darstellung verwendet (und nicht neu geschaffen) werden.

Klemens Böhm

PSE-Aufgabenstellung: "Generierung von totalen Kolorierungen von Graphen"

Ausgangspunkt für diese Aufgabenstellung ist die sogenannte Total Coloring Conjecture, ein faszinierendes offenes Problem aus der Graphentheorie. Sie ist wie folgt:

- Eine totale Kolorierung ist eine Abbildung, die sowohl den Knoten als auch den Kanten eines gegebenen Graphen je eine Farbe zuweist, sodass gilt:

* Ein Knoten und seine benachbarten Kanten haben unterschiedliche Farben.
* Kanten, die zum gleichen Knoten benachbart sind, haben unterschiedliche Farben.
* Knoten, die durch eine Kante verbunden sind, haben unterschiedliche Farben.
- maxdegree sei der maximale Grad eines Knotens im Graph.
- Die Vermutung besagt jetzt: Es gibt für alle Graphen eine totale Kolorierung, die mit maxdegree+2 Farben auskommt.

Die Aufgabenstellung, in einem Satz verkürzt zusammengefasst, besteht darin, ein Werkzeug zu bauen, mit dem (Schritt 1) man Graphen zusammenklicken kann, und das dann (Schritt 2) -- unter Verwendung eines ILP-Solvers -- eine totale Kolorierung mit bestimmten Eigenschaften findet, die ich im Folgenden noch beschreiben werde, und (Schritt 3) diese dann visuell ansprechend ausgibt.

Für Schritte (1) und (3) sollen existierende Werkzeuge für das Editieren und Darstellen von Graphen verwendet (und keinesfalls selbst implementiert) werden. Was Schritt (2) angeht, dürfte die Hauptarbeit darin bestehen, Graphen in ein ILP (integer linear program, d. h. ganzzahliges lineares Programm) zu überführen und umgekehrt, also das Ergebnis des Solvers als total kolorierten Graphen darstellbar zu machen. Sie sollen also keine "schweren" algorithmischen Probleme lösen im Rahmen der Aufgabenstellung. Sie lernen im Rahmen der Bearbeitung aber ILP Solver kennen, eine sehr nützliche und breit einsetzbare Art von Werkzeug, und werden so über die "üblichen" Lerneffekte hinaus von der Bearbeitung dieser Aufgabenstellung profitieren.

Aufbauend auf diesem grundlegenden Ablauf enthält die Aufgabenstellung die folgenden Verfeinerungen:

(a) Die Benutzerin/Der Benutzer Ihrer Software soll bestimmte Eigenschaften der gesuchten totalen Kolorierung vorgeben können. Dazu gehören die folgenden Punkte -- in Kombination miteinander:

(a1) Man soll in Schritt (1) Farben einzelner Knoten und Kanten vorgeben können.

(a2) Man soll Vorgaben machen können wie:

* "Möglichst wenige Knoten sollen die Farbe 1 haben." (In der Graphtheorie werden Farben üblicherweise als Nummern repräsentiert, also zum Beispiel 1, 2, 3, ... anstelle von rot, blau, grün, ...)
* Dto. Kanten.
* Dto. Objekte des Graphen. 'Objekt' ist hier der Oberbegriff sowohl für Knoten als auch für Kanten.

(a3) Man soll Vorgaben machen können wie: "Es soll eine 'möglichst helle' Kolorierung gefunden werden."
Das bedeutet Folgendes: Um zu entscheiden, ob zwei Graphen gleich sind, verwendet man oft kanonische Numerierungen der Graphen. Zwei Graphen G1 und G2 sind gleich, wenn sie gleich viele Knoten haben, und wenn zwischen zwei Knoten mit der gleichen kanonischen Nummer stets in beiden Fällen oder in keinem Fall eine Kante existiert. Bestimmte kanonische Numerierungen eines Graphen sollten sich mit ILP-Solvern finden lassen. (Ich werde Ihnen einen Zusammenschrieb zur Verfügung stellen, welche kanonische Numerierung, die nicht nur Knoten, sondern allen Objekten des Graphen eine Nummer zuweist, ich wünsche. Es soll die Möglichkeit bestehen, sich die kanonische Numerierung eines Graphen im Editor in Schritt (1) sowie zusammen mit der erzeugten Kolorierung in Schritt (3) anzeigen zu lassen. Es kann sein, dass das Finden der kanonischen Numerierung mit einem ILP Solver nur für kleine Graphen funktioniert, das braucht Sie aber nicht bekümmern; für größere Graphen soll in dem Fall entweder 'nur' die restliche in diesem Zusammenschrieb geforderte Funktionalität realisiert werden, oder das Finden der kanonischen Numerierung ist Teil der Kann-Funktionalität Ihrer Bearbeitung.) Eine Kolorierung K1 von G ist heller als eine andere (K2), wenn das erste Objekt, das gemäß K1 eine andere Farbe hat als gemäß K2, eine kleinere Farbe hat gemäß K1.

Auch das Finden einer möglichst hellen Kolorierung lässt sich als Ganzzahlproblem formulieren; das Generieren dieses Ganzzahlproblems ist ebenfalls Teil der Aufgabenstellung.

(b) In Schritt (1) soll die Möglichkeit bestehen, sich Graphen zufällig erzeugen zu lassen. D. h. man gibt idealerweise nur die Anzahl der Knoten des Graphen und maxdegree vor und bekommt einen zufälligen Graphen mit maximal vielen Kanten. Es soll die Möglichkeit bestehen, diesen Graph dann im Editor noch zu verändern, die Farben bestimmter Objekte vorzugeben usw., bevor Schritt (2) stattfindet.

(c) Wichtig ist mir die Möglichkeit, für Paare von Graphen, die sehr ähnlich zueinander sind, maximal ähnliche Kolorierungen erzeugen und die dann visuell vergleichen zu können. D. h. der Ablauf ist wie folgt:

(1) Generieren eines Paares von Graphen G1 und G2 im Editor. G2 unterscheidet sich von G1 dadurch, dass eine Kante e1 einen anderen Knoten als Nachbarn hat (v1 in G1, v2 in G2). Dafür hat eine Kante e2 in G1 den Knoten v2, in G2 den Knoten v1 als Nachbarn. Ansonsten sind die Graphen gleich. Der Editor soll das Zusammenklicken eines solchen Paars von Graphen und das Markieren dieser Unterschiedskanten ermöglichen.

(2) Finden von Kolorierungen von G1 und G2, die maximal ähnlich zueinander sind. 'maximal ähnlich' kann mehrere Bedeutungen haben. Eine ist, dass möglichst wenige Objekte eine unterschiedliche Farbe haben. Eine andere ist, dass außerdem die Unterschiedskanten in beiden Fällen die gleiche Farbe haben müssen. Eine dritte ist, dass die Unterschiedlichkeit der Kolorierungen erst möglichst spät, d. h. so weit hinten wie möglich gemäß der kanonischen Numerierung von G1, auftreten soll. (Sich hier noch mehr auszudenken und das dann umzusetzen könnten mögliche Kann-Kriterien im Rahmen dieser Aufgabenstellung sein.)

(3) Darstellung des Ergebnisses im Editor.

(d) Es soll die Möglichkeit geben, Graphen bzw. Paare von Graphen und ihre Kolorierungen abspeichern zu können, zusammen mit Freitextannotationen.