Graphpartitionierung

Ein Graph ist eine Menge von Knoten und Kanten zwischen diesen Knoten. Man unterscheidet zwischen gerichteten Graphen, wo Einbahnstraßen darstellbar sind, oder den ungerichteten Graphen, wo Beziehungen zwischen zwei Knoten immer beidseitig sind. Beispiele sind die graphische Darstellung von Beziehungen in einem sozialen Netz oder Straßennetze, für deren Verarbeitung das Forschungsgebiet von Christian Schulz immer bedeutender wird, wie wir in seinem Gespräch mit Gudrun Thäter erfahren. Eine wichtige Aufgabe im Umgang mit Graphen ist die Aufteilung (oder fachsprachlich Partitionierung), von Graphen in kleinere Teile. Dies kommt z.B. der Parallelisierung der Arbeit auf den Graphen zugute, und ist unumgänglich, wenn Graphen eine Größe haben, die nicht mehr von einem Prozessor bearbeitet werden kann. Ein wichtiges Merkmal ist hier, die Aufteilung möglichst gleichmäßig vorzunehmen, damit die Aufteilung von z.B. Rechenzeit gleichmäßig erfolgt, und gleichzeitig wenig Kommunikation zwischen der Bearbeitung der Einzelteile erforderlich ist. Es geht um eine möglichst gute Skalierbarkeit der Graphverarbeitung. Ein wichtiges Anwendungsproblem ist die Routenplanung, bei der zwischen zwei Punkten auf der Erde die zeitlich kürzeste Verbindung berechnet werden soll. In der Informatik ist der Dijkstra-Algorithmus der passende Basis-Algorithmus für diese Aufgabe, doch er ist für große Graphen in seiner ursprünglichen Form sehr ineffizient. In Kombination mit einer passenden Graphpartitionierung und Algorithmen kann man das Verfahren deutlich effizienter ausführen und beschleunigen. Ein klassisches Verfahren zur Aufteilung ist das Mehrschichtverfahren über die Laplace-Matrix, wo ausgenutzt wird, dass zwischen den Eigenwerten der Matrix und der Schnittstruktur des Graphen enge Zusammenhänge bestehen. Dieses Verfahren wurde zum Mehrschichtverfahren für Graphen weiterentwickelt, bei dem in einer sogenannten Kontraktion benachbarte Knoten und parallele Kanten jeweils zusammengeführt werden, und der Graph zu einem kleinen und kantengewichteten Graph vereinfacht wird. Schließlich wird das Problem auf einem vereinfachten, groben Gitter gelöst, und dann jeweils mit lokalen Suchen auf feinere Graphen erweitert. Für die Kontraktion werden Heuristiken und Kantenbewertungsfunktionen verwendet. Ein weiterer Ansatz sind auch evolutionäre Algorithmen. Dabei wurde eine allgemeinere Umgebung geschaffen, die auf eine weite Klasse von Optimierungsproblemen angewendet werden kann. Die Graphentheorie ist natürlich auch Teil der diskreten Mathematik, und besonders berühmt ist auch das Traveling Salesperson Problem. Gleichzeitig ist das Thema aber auch in der Theoretischen Informatik, im Algorithm Engineering und in der Software-Entwicklung beheimatet.