Was hat die Anreise zur Akademie mit Mathematik zu tun? Wie viele Farben benötigt man, um eine Landkarte einzufärben, wenn benachbarte Länder je unterschiedliche Farben haben sollen? In welchen Städten kann man einen Rundweg finden, ohne eine Brücke zweimal zu überqueren? Und was hat ein Karate-Club mit dem Ganzen zu tun?

Auch wenn diese Fragen auf den ersten Blick nicht sehr viel gemeinsam zu haben scheinen, so lassen sie sich doch alle auf ein Gebiet der Mathematik zurückführen: die Graphentheorie. Graphen sind zunächst einfache Gebilde aus Knoten, die durch Kanten verbunden werden (s. Abbildung). Doch hinter diesen einfachen Konstrukten stecken teils außerordentlich schwierige und herausfordernde Probleme.

Dieser Kurs erarbeitet sich ausgehend von den mathematischen Grundlagen der Graphentheorie einige dieser schwierigen Probleme. Die Thematik umfasst daher zunächst einige mathematische Grundprinzipien, gefolgt von einer Einführung in die Graphentheorie und die Komplexitätstheorie. Die Komplexitätstheorie beschreibt die „Schwierigkeit“ eines Problems auf mathematische Art und Weise und wird hier benötigt, um die Schwierigkeit eines Graphenproblems beschreiben zu können. Zudem diskutiert der Kurs in Grundzügen, ob und inwiefern Quantencomputer für die Lösung von Graphenproblemen nützlich sein können.

Danach untersuchen die Teilnehmerinnen und Teilnehmer in Kleingruppen verschiedene Graphenprobleme auf ihre Schwierigkeit (bzw. Komplexität), und erarbeiten außerdem praktische Beispiele für Graphen in ihrer eigenen Umgebung. Dabei kann neben Stift und Papier bei Interesse auch ein (klassischer) Computer zum Einsatz kommen.

Für den Kurs sind keine speziellen Vorkenntnisse nötig. Von den Teilnehmerinnen und Teilnehmern wird die Bereitschaft zur Vorbereitung eines kurzen Referats erwartet.