In Navigationsgeräten und Spracherkennung steckt Graphentheorie, ein Teilbereich der modernen Mathematik, die voller Rätsel ist. Eines davon soll nun gelöst sein. Die Zeit berichtet:

Wie zusammenhängend ein Graph ist, ist heute zum Beispiel für Netzwerkadministratoren interessant. Der „Zusammenhang“ beschreibt, wie viele Knoten im Netz ausfallen müssen, bis zwei Computer in dem Netzwerk nicht mehr miteinander kommunizieren können.

Woran andere seit 40 Jahren scheiterten, wollen drei junge Mathematiker des Georgia Institute of Technology geschafft haben: den Beweis für die Kelmans-Seymour-Vermutung. Ihre dazu ersten, nun im Internet veröffentlichten Ausführungen sehen vielversprechend aus und haben einiges Aufsehen erregt. Doch es sind erst zwei von fünf geplanten langen Arbeiten – eine Menge Text, wenn man bedenkt, dass das ursprüngliche Problem nur einen Satz lang ist.

Zugegeben: Was der Brite Paul Seymor und der Russe Alexander Kelmans unabhängig voneinander in den siebziger Jahren formuliert haben, klingt ganz schön kryptisch. „Jeder 5-zusammenhängende nicht-planare Graph besitzt einen Unterteilungsgraphen des K5“, vermuteten sie. Der Laie fragt sich: Bitte was? Der Mathematiker: Ob das stimmt und wenn ja, warum?

Die Theorie solcher Graphen wird allerorten im Alltag verwendet, in Navigationsgeräten und Routenplanern zum Beispiel oder in den „neuronalen Netzen“, mit denen man Handys künstliche Intelligenz, Spracherkennung oder Computern das Go-Spielen beibringt. Sie ist ein vergleichsweise junger Teilbereich der modernen Mathematik. Und sie boomt.

Die Graphen, um die es in diesem Fall geht, sind nicht die bananenförmigen Linien auf der Schultafel, es geht um Landkarten oder Netzwerke. Stellen Sie sich Freunde vor, die über Facebook miteinander verbunden sind oder die Ecken eines Würfels, die an den Würfelkanten zusammenhängen. Die Theorie solcher Graphen wird allerorten im Alltag verwendet, in Navigationsgeräten und Routenplanern zum Beispiel oder in den „neuronalen Netzen“, mit denen man Handys künstliche Intelligenz, Spracherkennung oder Computern das Go-Spielen beibringt. Sie ist ein vergleichsweise junger Teilbereich der modernen Mathematik. Und sie boomt.

Die Kelmans-Seymour-Vermutung hilft beim Einordnen von Graphen.
The Kelmans-Seymour conjecture II:
Dawei He, Yan Wangy, Xingxing Yuz
Georgia Tech Mathematicians Solve 40 Year Old Math Mystery