Abgeschlossene Projekte

• Kurze Beschreibung des Projektes. Switching Graphs sind ein relativ neuer Graphformalismus. Neben den aus herkömmlichen Graphen bekannten Knoten und Kanten, gibt es in einem Switching Graph noch zusätzliche 'Switches'. Diese sind formal ein Tupel aus drei Knoten (u, v, w), wobei ein 'switch setting' dann für jeden Switch eine der zwei möglichen Kanten (u,v) oder (u,w) auswählt. Switching Graphen weisen interessante Verbindungen zu anderen Problemen in der Informatik auf (wie bspw. dem Model Checking Problem im mü-Kalkül) und sind auch für sich selbst genommen interessant. Sie sind allerdings noch kaum untersucht und es ist möglich aus der Graphentheorie bekannte Probleme zu übertragen, sowie völlig neue zu untersuchen. In diesem Projekt konzentrieren wir uns auf Färbbarkeitsprobleme. Zu diesen gibt es bezüglich normaler Graphen eine vielfältige Literatur, bezüglich Switching Graphen liegen allerdings noch keinerlei Ergebnisse vor. Wir wollen in dem Projekt Färbbarkeitsprobleme (zunächst insb. Knoten- und Kantenfärbbarkeit) auf Switching Graphen übertragen und definieren und sie dann hinsichtlich ihrer Komplexität untersuchen. Es wird dabei vermutlich entweder möglich sein einen effizienten Algorithmus zu entwickeln (der dann ggf. auch implementiert werden kann) oder nachzuweisen, dass diese Probleme NP-vollständig oder ähnliches sind.
• Vorwissen dieser Module wäre nützlich: AuD, etwas DM und FGI1
• Das Projekt passt am besten zu diesem Modul: AuD
• Kontakt: Frank Heitmann
• Erfahrungsbericht: Dieses Projekt wurde von Bianca Noack bearbeitet und ist bereits abgeschlossen. Nachfolgend ist ihr Erfahrungsbericht zu lesen.

Dank des Projektes und meines Betreuers Frank Heitmann hatte ich bereits in meinem Bachelorstudium die Chance, in das wissenschaftliche Arbeiten und Forschen tiefer hinein zu schnuppern.

Unter Franks Anleitung habe ich mich zunächst intensiver in die Graphentheorie eingearbeitet, die ich schon aus Verantstaltungen wie DM (Diskrete Mathematik) oder AuD (Algorithmen und Datenstrukturen) etwas kannte. Er stellte mir zunächst Aufgaben, um mein Verständnis für Graphen zu verbessern. Anschließend habe ich mich insbesondere in die Färbbarkeit von Graphen eingelesen und mich mit dem neuartigen Graph-Formalismus der Switching Graphen befasst. Danach habe ich das Problem der Färbbarkeit auf diese Switching Graphen übertragen und untersucht, was vor mir noch niemand gemacht hatte.

Die Arbeit an diesem doch sehr theoretischen Thema hat mir sehr gefallen. An den verschiedenen Aufgaben zu tüfteln hat Spaß gemacht, auch wenn es mal ein wenig frustrierend sein konnte, wenn ich einen gegebenen Beweis nicht auf Anhieb verstanden hatte oder eigene Beweisversuche nicht klappten. Doch nach einem Weilchen knoblen und dem ein oder anderen Hinweis von Frank, war kaum noch ein Beweis vor mir sicher. Dank des Projektes konnte ich einen tollen Eindruck vom wissenschaftlichen Arbeiten gewinnen und mich auch in diesem Üben. Es hat mir eine tolle Grundlage und auch gleich ein super Thema für meine damals anstehende Bachelorarbeit geboten.