Software Entwicklung: Automatische Generierung und Auswertung vieler Beispiele für ein ungelöstes Informatik-Problem

Es gibt eine faszinierende Liste offener Mathematik- und Informatik-Probleme, s. b.
https://de.wikipedia.org/wiki/Ungel%C3%B6ste_Probleme_der_Mathematik oder
https://de.wikipedia.org/wiki/Liste_ungel%C3%B6ster_Probleme_der_Informatik.
Um Einsichten zu bekommen, die zur Lösung eines solchen Problems beitragen könnten, ist es möglicherweise hilfreich, sehr viele Beispiele zu haben, die man dann mit automatischen Methoden auswertet. Ihre Aufgabe besteht darin, ein Werkzeug zu bauen, die diese Sicht auf die Dinge für ein konkretes Problem umsetzt, wie folgt:

  • Das Problem, das aus unserer Sicht geeignet ist, ist die Total Coloring Conjecture, s. b. https://en.wikipedia.org/wiki/Total_coloring
  • Wir gehen davon aus, dass für manche Graphen eine totale Kolorierung schwerer zu berechnen ist als für andere, und wir fragen uns jetzt, welche Eigenschaften von Graphen mit der Eigenschaft 'Kolorierung ist schwer zu berechnen' wie zusammenhängen.
  • Das von Ihrem Team zu erstellende Werkzeug soll Folgendes leisten:
    • Generierung einer großen Zahl zufälliger Graphen, Speicherung dieser Graphen in einer Datei oder in einer Datenbank.
    • Berechnung der erforderlichen Anzahl von Farben bzw. einer Kolorierung für einen gegebenen Graphen.
    • Auswertung eines oder mehrerer einfacher Maße, wie schwierig die Berechnung der erforderlichen Anzahl Farben für den gegebenen Graphen war.
    • Berechnung anderer Eigenschaften eines Graphen (als Voraussetzung für die Suche nach o. g. Zusammenhängen). Hier können zum einen einfache Maße zur Anwendung kommen wie der durchschnittliche Grad der Knoten des Graphen (ist aber vielleicht nicht so aufschlussreich). Zum anderen gibt es aber beispielsweise unterschiedliche differenziertere Definitionen der Dichte von Graphen, die dürften hier interessanter sein. Wir haben uns noch ein paar weitere Hypothesen überlegt, aus denen sich sinnvolle Eigenschaften ergeben könnten.
    • Berechnung der Korrelationen der Eigenschaften, mit Hilfe einfacher Korrelationsmaße.
    • Brauchbare Benutzerschnittstelle, insbesondere:
      • Anzeige der Analyseergebnisse (o. g. Korrelationen insbesondere)
      • Darstellung einzelner ausgewählter Graphen mit ihrer Kolorierung
      • Möglichkeit des Hinzufügens einzelner 'von Hand' generierter Graphen zum Graph-Datenbestand.

Für die Bewertung ist nicht relevant, ob mit Hilfe Ihres Werkzeugs tatsächlich interessante Einsichten zustande kommen - es gelten die üblichen PSE-Bewertungskriterien.