Eigenvektoren von Graph-Laplace-Operatoren

Forschungsprojekt P 14094Eigenvektoren von Graph-Laplace-OperatorenJosef LEYDOLD06.03.2000 Die Grundlagen für die Spektraltheorie der Graphen wurden in den 50er und 60er Jahren gelegt. Seither haben sich diese Methoden als Standardtechnik in der (algebaischen) Graphentheorie etabliert. Die Eigenwerte der Graphen, definiert als Eigenwerte ihrer Adiazenzmatrizen, werden zur Charakterisierung von Graphen und zur Abschätzung bestimmter Parameter, wie Durchmesser, chromatische Zahl, Zusammenhang, etc. verwendet. Zur Zeit liegt das Interesse alerdings mehr bei den Eigenwerten des eng verwandten Graph-Laplace-Operators. Die Eigenvektoren wurden hingegen wenig beachtet. Sie wurden aber für verschiedene heuristische Verfahren wie Einfärben, Partionieren und Zeichnen von Graphen verwendet. Vor kurzem konnte gezeigt werden, daß die Kostenfunktionen für eine Reihe von kombinatorischen Optimierungsproblemen, darunter das Problem des Handelsreisenden, Eigenfunktionen derjenigen Graphen sind, die sich aus den entsprechenden Suchheuristiken ergeben. Überraschenderweise wurde erst vor ein paar Jahren gezeigt, das die Eigenfunktion das Graph-Laplace- Operators viele wichtige Eigenschaften mit den Eigenfunktionen des Laplace-Operators viele wichtige Eigenschaften mit den Eigenfunktionen des Laplace-Operators auf Riemannschen Mannigfaltigkeiten teilt. Dieses Forschungsprojekt untersucht die geometrischen Eigenschaften der Eigenfunktionen des Graph-Laplace- Operators abhängig von der Lage des entsprechenden Eigenwertes im Spektrum und der Struktur des zugrundeliegenden Graphen. Ein Ziel ist die Verbesserung des Courantschen Satzes über die Anzahl der Knotengebieten. Dieses besagt, das ein Eigenfunktion zum k-ten Eigenwert (bei Berücksichtigung der Vielfachheit) höchstens k viele Knotengebiete hat, d.s. die Zusammenhangskomponenten der Teilgraphen mit nichtpositiven bzw. nichtnegativen Knoten. Diese Schranke ist für viele Graphen nicht scharf. Wir erwarten, daß sich mit Hilfe von, z.B., Minoren bessere Schranken finden lassen. Ein weiterer Punkt ist die Formulierung und der Beweis von Faber-Krahn-Ungleichungen. Dabei muß man einen Graphen mit gegebenen Volumen finden, der den kleinstmöglichen ersten Dirichleteigenwert hat. Die resultierenden Graphen sind ähnlich, aber überraschenderweise nicht gleich wie Kugeln, wie man aus Analogie zum klassischen Laplace-Operator erwarten würde. Neben reiner analytischer Arbeit werden auch numerische Experimente die Suche nach Strukturen und gegebenenfalls das Suchen von Gegenbeispielen unterstützen. Dafür ist die Entwicklung eines geeigneten Computerprogramms notwendig.

Graphen sind einfache mathematische Objekte: Man nehme einzelne Knoten und verbinde sie mit Linien (so genannten Kanten). Ein einfaches Anwendungsbeispiel ist etwa eine Straßenkarte: Ortschaften und Kreuzungen sind die Knoten, Straßen die Kanten. Dieses simple Konzept hat viele Anwendungen in unterschiedlichen Bereichen. Neben der offensichtlichen Modellierung von Transport- oder Telekommunikationsnetzwerken werden Graphen u.a. auch zur Beschreibung organischer Moleküle oder kombinatorischer Probleme verwendet. Die Graphentheorie beschäftigt sich nun mit den Eigenschaften solcher Graphen. Eines von möglichen Werkzeugen für die Untersuchung von Graphen ist der Laplace-Operator. Dessen Wirkungsweise kann man sich in etwa so vorstellen: Man denke sich die Knoten des Graphen als Kugeln, die entlang der Kanten durch Spiralfedern verbunden sind. Bringt man das ganze durch Anstoßen in Schwingung kann die Bewegung der Kugeln durch den Laplace-Operator beschrieben werden. Die einzelnen Schwingungsmodi kann man als Töne und Obertöne interpretieren. In diesem Forschungsprojekt wurde untersucht, wie die Knoten dieses Gebildes schwingen. Es gibt dabei immer Punkte, die nicht mitschwingen. Man kann nun die Kanten des Graphen in genau diesen Punkten auseinander schneiden. Der Graph wird dann in mehrere Teile zerfallen. Es konnte nun in diesem Projekt gezeigt werden, dass die mögliche Anzahl dieser Teile nicht beliebig groß sein kann. Wenn man den k-ten Schwingungsmodus (Oberton) betrachtet, dann kann es höchstens k viele Teile geben. Und in vielen Fällen sind es sogar weniger. Interessant wird es auch, wenn wir aus dem Graphen eine Trommel machen indem wir einige seiner Knoten auf einem Rahmen festnageln. Die Tonhöhe beim Schlagen dieser Trommel hängt nun von deren Größe ab: je größer, desto tiefer der Ton. Sie hängt aber auch von deren Form ab. Bei echten Trommeln haben kreisförmige den tiefsten Ton unter allen Trommeln mit gleicher Fläche. Bei den Graphen ist das fast genauso, aber nur fast. Die haben nämlich noch irgendwo am Rand eine Ecke. Das Bild mit der Trommel und dem Ton greift aber nicht weit genug. Durch die Abstraktheit dieser mathematischen Objekte gibt es durchaus einen Zusammenhang zu ganz anderen Bereichen: Etwa zum nur unvollständig gelösten Problem des Handelsreisenden, der versucht alle Kunden in der kürzestmöglichen Rundreise zu besuchen; oder auch zu Fragenstellungen in der theoretischen Biologie.