Einführung in die Graphentheorie

“Armer, traurig aussehender Fremder” – so hat der amerikanische Schriftsteller Mark Twain einen Händler betitelt. Aber warum ist er traurig und arm? Vielleicht, weil er das Problem des Handlungsreisenden lösen musste: Die Aufgabe besteht darin, eine Reihenfolge für den Besuch mehrerer Orte so zu wählen, dass die gesamte Reisestrecke des Handlungsreisenden möglichst kurz und jede Station auch nur einmal besucht wird. Dieses Problem stellt die Grundlage des heutigen Handels dar und basiert auf der Graphentheorie.

Vor langer Zeit war das ein unbequemes Problem sowohl für Händler als auch für Mathematiker. Dieses wurde erstmals im 19. Jahrhundert vom irischen Mathematiker W.R. Hamilton und vom britischen Mathematiker Thomas Kirkman erwähnt.

Die “Sieben Brücken von Königsberg”, benannt von Leonard Euler

im Jahre 1736, beschreiben ein weiteres Problem der Thematik. Königsberg lag in Preußen, heute Kaliningrad, Russland, erstreckte sich auf beiden Seiten des Pregel Flusses und hatte außerdem zwei Inseln auf dem Fluss, die über Brücken mit dem Rest der Stadt verbunden waren. Die Herausforderung bestand darin, eine Route zu erstellen, die über jede Brücke nur ein einziges Mal führt. Die Einwohner forderten Reisende und Besucher immer auf sich dieser Aufgabe zu stellen. Jedoch konnte niemand eine Lösung finden, nicht einmal die Bewohner der Stadt. Leonard Euler bewies, dass es auf dieses Problem keine Lösung gibt, aber formulierte eine Regeln, nach der berechnet werden konnte, ob ein einmaliger Weg überhaupt möglich ist. Das ist die Regel, auf die die Graphentheorie fundiert ist. Euler schrieb eine Arbeit zu diesem Phänomen und veröffentlichte diese 1736. Es war die erste Arbeit über Graphentheorie in in der Geschichte und stellt die erste Seite in der Geschichte der Graphentheorie dar.

Bis heute ist das Thema für Postboten und Reisende auf der ganzen Welt aktuell. Den besten Lösungsansatz stellt die Graphentheorie dar.

Das ist die Geschichte. Wenn man jetzt einen Blick auf die Popkultur wirft, stellt man fest, dass Labyrinthe schon sehr lange dort auftauchen. Angefangen hat es mit den Legenden von Theseus und Minotaurus und wurde zuletzt im Science Fiction Action Thriller “Maze Runner” aufgegriffen. Oder, wenn man an den vierten Teil Harry Potters denkt – das Finale des Teils ereignete sich auch in einem Labyrinth. Selbst im Thriller “The Shining” von Stephen King muss der Held den Weg aus einem Labyrinth finden. Das alles hat auch was mit der Graphentheorie zu tun. Wenn die Protagonisten die Grundlagen gewusst hätten, wären sie vielleicht schneller aus den Labyrinthen rausgekommen.

 

Was genau ist also die Graphentheorie?

Die Wissenschaft der Graphen ist Teil der diskreten Mathematik. Ein Graph ist per Definition eine abstrakte Struktur, die eine Menge von Objekten zusammen mit den zwischen diesen Objekten bestehenden Verbindungen repräsentiert. Die mathematischen Abstraktionen der Objekte werden dabei Knoten (auch Ecken) des Graphen genannt. Die paarweisen Verbindungen zwischen Knoten heißen Kanten (manchmal auch Bögen). Die Kanten können gerichtet oder ungerichtet sein. Häufig werden Graphen anschaulich gezeichnet, indem die Knoten durch Punkte und die Kanten durch Linien dargestellt werden. Sowas kommt auf Landkarten, Konstellationen oder bei der Erstellung von Schemata und Zeichnungen vor. Graphen stellen außerdem die Grundlage für viele Computerprogramme dar, die moderne Kommunikation und technologische Prozesse ermöglichen. Außerdem hängen Graphen auch mit dem Denken zusammen, sowohl logisch als auch abstrakt. Vielleicht kennt man aus der Kindheit noch das Malen nach Zahlen, wo man in einer bestimmten Reihenfolge Punkte verbindet, die am Ende ein Gesamtbild ergeben. Wir kennen alle die Aussage, dass man Mathematik im Alltag nicht wirklich braucht. Allerdings ist die Graphentheorie tatsächlich anwendbar, denn erst aus dem realen Leben heraus ist man auch auf darauf gestoßen.

 

Über den Kurs

Der Kurs wurde von der ITMO Universität aus St. Petersburg, Russland erstellt. Prioritäten in der Forschung an der staatlichen Universität stellen Informationen und photonische Technologien dar. “Einführung in die Graphentheorie” fokussiert sich auf Methoden und Algorithmen und ihrer Anwendung im Alltag. Das Ziel ist es ein Grundverständnis und Grundwissen zu vermitteln, um damit die am häufigsten auftretenden Probleme zu klären. Zuerst soll man grundlegende Mathematik anwenden können, um dann als zweites effektive Methoden zum Lösen von Aufgaben anzuwenden. Der Kurs ist besonders für diejenigen gut, die auch in der Universität mit der Thematik zu tun haben, sowohl Beginner als auch Fortgeschrittene.

Es gibt vier Kapitel und einen Test am Ende. Die Lehrinhalte werden per Video vermittelt, die ungefähr jeweils 15 min lang sind. Anschließend gibt es immer ein kleines Quiz, damit man sichergehen kann, dass die Inhalte auch verstanden wurden.
Graphentheorie entwickelt sich immer weiter und steht niemals still. Deswegen ist es gut die grundlegende Konzepte verstanden zu haben.

This post is also available in: English (Englisch)