Realisierungen starrer Graphen

Ausgehend von Überlegungen der Statik bei der Konstruktion von Fachwerken war und ist die Beschäftigung mit stabilen bzw. starren Konstruktionen Thema wissenschaftlicher Arbeiten. Fachwerke, bestehend aus Stäben und Verbindungsstücken, werden durch Graphen mit Kanten und Knoten modelliert. Dadurch können Eigenschaften wie die Stabilität der Fachwerke anhand mathematischer Objekte studiert werden. Diese mathematischen Objekte werden starre Graphen genannt und bilden den Ausgangspunkt dieses Projekts. Ein Graph mit gegebenen Kantenlängen ist dann starr, wenn es nur endlich viele Möglichkeiten gibt, den Graphen zu zeichnen, sodass die Distanzen der Knoten mit den Kantenlängen übereinstimmen. Dabei ignorieren wir Rotationen und Verschiebungen. Eine Zeichnung, also die Koordinaten der Knoten, nennen wir Realisierung. Wir sind an der Anzahl dieser Realisierungen interessiert. Erst kürzlich wurde ein Algorithmus entwickelt, um die Anzahl der Realisierungen für einen starren Graphen in der Ebene zu berechnen. Ziel des Projektes ist es, zum einen die Anzahl der Realisierungen zu analysieren. Wir untersuchen Klassen von Graphen mit möglichst hoher oder niedriger Anzahl von Realisierungen. Diese Graphen helfen, allgemeine Schranken zu finden. Des weiteren untersuchen wir die Realisierungen von starren Graphen im dreidimensionalen Raum. Die Eigenschaft der Starrheit kann auch auf allgemeinere Objekte erweitert werden, etwa auf sogenannte Hypergraphen. In diesen Fällen ist bisher weit weniger bekannt. Ziel dieses Projekts ist es also, ein tieferes Verständnis für diese starren Objekte aufzubauen. Das Projekt verbindet verschiedene mathematische Disziplinen: Graphentheorie, Kombinatorik, Symbolisches Rechnen und Algebraische Geometrie. Diese Vielfalt erlaubt es, Methoden aus mehreren Bereichen zu kombinieren und dadurch neue Resultate zu erlangen. Starre Graphen spielen eine wichtige Rolle in vielen Anwendungen, etwa beim rechnerunterstützten Konstruieren, in der molekularen Biologie, in Sensornetzwerken, in der Robotik, in Materialwissenschaft und im maschinellen Lernen. Diese Anwendungen zeigen auf, dass es wichtig ist, die zugrundeliegenden Modelle aus der Grundlagenforschung heraus besser zu verstehen.

Ziel des Projektes war die Analyse von Realisierungen von starren Graphen. Graphen bestehen dabei aus Knoten, welche mit Kanten verbunden sind. Ein Graph kann als starr bezeichnet werden, wenn es nur endlich viele verschiedene Möglichkeiten gibt, ihn zu zeichnen, wenn die Kantenlängen vorgegeben sind. Zwei Zeichnungen sind verschieden, wenn sie nicht durch Rotationen und Verschiebungen ineinader übergeführt werden können. Es gab bereits Methoden zur Berechnung der Anzahl an Zeichnungen (auch Realisierungen genannt). In dem Projekt wurden diese verbessert. Mit aktuellen Methoden kann für viele Graphen die Anzahl deutlich schneller berechnet werden. Die Problemstellung wurde außerdem auf andere Situation ausgeweitet, zum Beispiel auf Realisierungen auf einer Kugeloberfläche. Hier wurde ein Algorithmus zur Berechnung der Anzahl erstellt. Erste Resultate zur Anzahl von Realisierungen im Raum wurden ebenfalls erreicht. Besonders interessierten uns Graphen mit besonders wenig Realisierungen, unter anderem auch global starre Graphen, die nur eine einzige Realiesrung haben (bis auf Spiegelung). Auf der anderen Seite wurden Graphen mit möglichst vielen Realiesrungen gefunden. Manche Graphen haben für bestimmte Kantenlängen eine unendliche Anzahl an Realisierungen. Diese Realisierungen können dann in einer Bewegung des Graphen dargestellt werden. Wir nennen jede davon dann eine flexible Realisierung. In vielen Fällen überlappen sich aber dann Knoten während der ganzen Bewegung. In diesem Projekt konnten wir bestimmte Klassen von Graphen zeigen, in welchen Fällen flexible Realisierungen existieren, die keine überlappenden Knoten haben. Weiters konnten auch hier Resultate auf die Kugeloberfläche, auf rotationssymmetrische Realisierungen und für spezielle Graphen auf den dreidimensionalen Raum erweitert werden. In allen Fällen spielte algebraische Geometrie eine wesentliche Rolle. Während die Ergebnisse oft mit den Grundlagen der Graphentheorie beschrieben werden können, benötigen die Beweise die Anwendungen von algebraischen Methoden. Diese basieren auf den Gleichungen, die aus den Bedingungen der Kantenlängen entstehen. Realisierungen von starren Graphen spielen auch in Anwendungen eine Rolle. Erste Annäherungen an Anwenungen in der algebraischen Statistik und der Biologie konnten geknüpft werden.