Aufgabe

Zu einem Graphen G=(V,E) ist das Graph Färbungsproblem ist folgendermaßen definiert: finde eine Abbildung c: V -> {1,…,k}, mit e={u,v} in E => c(u) != c(v). Dabei ist die Anzahl Farben k zu minimieren. Man möchte also den Knoten des Graphen Farben zuweisen, so dass benachbarte Knoten verschiedene Farben haben. Das Minimierungsproblem ist NP-vollständig, so dass in der Praxis häufig Heuristiken verwendet werden, um das Problem anzunähern.

Ziel der Arbeit ist es, basierend auf Graph Partitionierung einen evolutionären Algorithmus zu entwerfen und zu implementieren, der das Graph Coloring Problem annähert. Dazu müssen verschiedene Graph Coloring Heuristiken implementiert und evaluiert werden. 

 

Vorraussetzungen

 

• Interesse und solide Kenntnisse uber Algorithmen und Datenstrukturen
• Gute Programmierkentnisse in C++