Klemens Böhm

Dennis Kobert

Herr Böhm

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.