zum Inhalt springen

Algebraische Algorithmen

In der algebraischen Graphentheorie versucht man Graphen in algebraischen Strukturen zu kodieren, um somit die kombinatorischen Eigenschaften von Graphen durch algebraische Eigenschaften zu repräsentieren. Ein wesentlicher Teil der Vorlesung wird sich deshalb mit der Zuordnung von Graphen zu Matrizen und der sich daraus ergebenden spektralen Graphentheorie befassen. Insbesondere werden Eigenwerte spezieller Graphklassen wie z.B. der Kantengraphen thematisiert. Der algebraische Hintergrund entstammt hier im wesentlichen der linearen Algebra. Daneben werden gruppentheoretische Aspekte von Graphen, wie die Automophismengruppe untersucht. In diesem Zusamenhang werden auch kanten- bzw. eckentransitive Graphen und deren Eigenschaften studiert. Eine wichtige Bedeutung in der algebraischen Graphentheorie haben weiter Polynome, die (partielle) Invarianten für Graphen bilden. Hier wird u.a. das chromatische Polynom eines Graphen definiert, welches die Anzahl möglicher (eigentlicher) (Ecken-)Färbungen des Graphen mit einer gegeben Anzahl von Farben kodiert. Sodann wird das Rangpolynom in einem möglichst allgemeinen Rahmen eingeführt, nämlich für Matroide. Dies führt in Spezialisierung auch zu einer Definition dieses Polynoms für Graphen. Das Rangpolynom hängt eng mit dem Tutte-Polynom zusammen, welches wiederum eine Verallgemeinerung insbesondere des chromatischen Polynoms ist. Im letzten Teil wird mittels des Rangpolynoms eine moderne Invariante für die Knotentheorie das sogenannte Jones-Polynom hergeleitet. Ein Knoten ist eine geschlossene, sich nicht selbst schneidende Kurve endlicher Länge im reellen drei-dimensionalen Raum. Das Jonespolynom bietet ein Werkzeug zur Klassifikation von Knoten. Es wird stets auch der algorithmische Aspekt im Rahmen einer Problemstellung betrachtet und untersucht ob die algebraische Sichtweise von Nutzen sein kann.

Literatur:

  • Bollobas, B.: Modern Graph Theory. In: Graduate Texts in Mathematics, Springer-Verlag, 2002.
  • Godsil, C.; Royle, G.: Algebraic Graph Theory. In: Graduate Texts in Mathematics, Springer-Verlag, 2001.
  • Biggs, N.: Algebraic Graph Theory. 3. Auflage, Cambridge University Press, 1994.