Fokus Forschung: Promovieren und Wandern

Netzwerke spielen in unserem Leben eine immense Rolle. Wir alle leben in einem Netzwerk aus sozialen Beziehungen und wir sind umgeben von technischen Netzwerken (Straßennetze, Wasserleitungsnetze, Computernetzwerke). Nicht zuletzt haben wir alle ein gewaltiges neuronales Netzwerk in unseren Köpfen. Alle diese Netzwerke sind Gegenstand wissenschaftlicher Untersuchungen. Aus mathematischer Sicht haben sie alle etwas gemeinsam: ihre Struktur kann mit der Sprache der Graphentheorie modelliert werden. Ein Graph ist ein abstraktes Modell, bestehend aus Knoten und Kanten, das die Topologie eines Netzwerkes repräsentiert. Graphen (Netzwerke) sind jedoch im Allgemeinen nicht zeitlich konstant, sie unterliegen Veränderungen, zum Beispiel durch Baumaßnahmen, technische Ausfälle oder biologische Entwicklung. Zudem werden oft Graphen bewusst lokal verändert (Reduktionen), um bestimmte Kenngrößen einfacher berechnen zu können.

Eine wichtige Frage in diesem Zusammenhang ist, wie sich Kenngrößen des Graphen, zum Beispiel Zusammenhangs- oder Unabhängigkeitseigenschaften, verändern, wenn der Graph lokal modifiziert wird. Genau hier setzt das Forschungsprojekt von Hany Ibrahim an. Er betrachtet in seinem Promotionsprojekt die Charakterisierung von Grapheneigenschaften, die bei Kontraktionen von Kanten erhalten bleiben. Eine wichtige Rolle spielen in diesem Zusammenhang Graphenklassen, die sich durch verbotene Untergraphen definieren lassen. Etwas anschaulicher gesagt sind das Netzwerke, die bestimmte Muster oder lokale Teilstrukturen nicht enthalten dürfen. Die Abbildung zeigt einen Graphen, in dem der vorgegebene Untergraph (H) zweimal, jedoch ein anderer (L) nicht vorkommt.

Diese Graphenklassen spielen für Fragen der Komplexität von Berechnungen auf Graphen eine große Rolle. Oft können Probleme, die allgemein auf beliebigen Graphen äußerst schwer berechenbar sind (NP-schwierige Probleme), auf eingeschränkten Graphenklassen effizient gelöst werden.

Hany Ibrahim entwickelte dafür zunächst eine Hierarchie von Graphenklassen sowie eine Theorie über Relationen und Konstruktionen für diese Klassen, die es ihm dann ermöglichten, bekannte Klassen von Graphen auf neue Weise durch Kontraktionseigenschaften zu charakterisieren. Die für die Korrektheit dieser Darstellung erforderlichen mathematischen Beweise sind technisch äußerst anspruchsvoll. Die Ergebnisse der Doktorarbeit lassen weitere interessante Anwendungen in der Strukturtheorie von Graphen erwarten.

Hany Ibrahim arbeitete in der Forschungsgruppe Diskrete Mathematik unter Leitung von Professor Peter Tittmann. Die beiden verbindet neben der Begeisterung für die Forschung in der Graphentheorie das gemeinsame Hobby Wandern. Hany Ibrahim, obwohl erst vor wenigen Jahren aus Kairo nach Deutschland gekommen, kennt in der Tat deutlich mehr Wanderwege in Sachsen aus eigener Erfahrung als die meisten der hier bereits lange beheimateten Menschen.