Was aus dem Königsberger Brückenproblem wurde

… und wie die Eulersche Charakteristik gefunden wurde.

Erinnert ihr euch an das Königsberger Brückenproblem und die Anfänge der Graphentheorie? Wir hätten es nicht mit Leonhard Euler zu tun gehabt, wenn er das Thema mit der Feststellung beendet hätte, dass es für Königsberg keinen sogenannten Eulerkreis gibt. Er erforschte und entwickelte die Graphentheorie weiter und begründete damit auch gleich noch die Topologie.

Lasst uns ein kleines Experiment probieren: Nehmt einen Stift, ein Blatt Papier und malt ein paar Kringel. Die Endpunkte müssen verbunden sein und die Linien sollten sich ein paar Mal überschneiden. Nun zählt die Schnittpunkte der Linien, die Linienabschnitte zwischen den Schnittpunkten und die eingeschlossenen Flächen. Nun rechnet mal E – V + 1 aus, wobei E die Anzahl der Linienabschnitte ist, V die Anzahl der Schnittpunkte und F sei die Anzahl der Innenflächen. Ich rate mal: E – V + 1 = F?!

In diesem Beispiel ist E = 8, V = 4 und F = 5. Damit gilt also auch E – V + 1 = 8 – 4 + 1 = 5 = F.

 

Die Beziehung X = V – E + F -1 (*) ist die sogenannte Euler’sche Charaktersitik. Sie wurde 1758 von Leonhard Euler bewiesen und ist ein tolles Beispiel für topologische Invarianten. Diese Invarianten sind vollkommen unabhängig von den konkreten Formen. Egal, wie viele Kringel euer Graph hat, wie viele Schnittpunkte ihr einbaut, immer gilt diese Formel. Man kann die Formel sogar für 3D – „Graphen“ anpassen, indem man die Flächen durch eingeschlossene Volumina und die Linienabschnitte durch die entsprechenden Oberflächen ersetzt.

Gerade in der Topologie versucht man immer, über möglichst allgemeine Eigenschaften von Formen zu sprechen. Das ist ziemlich spannend und wird uns noch öfter begegnen. Beispielsweise auch bei der eventuell erst einmal eigenartig klingenden Frage, was ein Donut mit einer Tasse gemeinsam haben könnte und was beide von einer Bretzel oder der Erde unterscheidet…

~~~~~~~~~~~~~~~~~~~~~~

Der ein oder andere mag sich nun fragen, wie Euler seine Charakteristik bewiesen hat. Ein sehr gute Frage! Denn immerhin haben wir es hier mit einem mathematischen Satz zu tun, der selbstverständlich einen Beweis benötigt. Ich möchte euch eine Skizze des Beweises geben:

Die Grundidee ist, vom einfachsten Graphen überhaupt auszugehen: Ein einfacher Punkt, also E = 0, V = 1 und F = 0. Hierführ gilt die Formel offenbar (vgl. im Bild a)).
Nun überlegt man sich, wie der Graph erweitert werden kann. Wie in b) kann eine Kante dazu kommen plus eine zusätzliche Fläche, dann kommt aber kein weiterer Knotenpunkt hinzu. Die Kante gleicht also hier die Fläche aus. Wie in c) kann auch eine weitere Kante dazu kommen, die mit einem zusätzlichen Punkt verbunden wird. Bei diesem Fall gleichen der neue Knoten und die Kante sich aus. Für beide Fälle gilt die Formel weiterhin, vgl. Abbildung.
Das ist im Prinzip alles, was man braucht. Denn die Formel gilt für den einfachsten Graphen überhaupt und jede Erweiterung kann durch eine der beiden Fälle, die oben beschrieben wurden, beschrieben werden. Denn jede Erweiterung braucht eine neue Kante, die wiederum eine neue Fläche oder eine neue Kante nach sich zieht. Beides führt zu einem Ausgleich in der Formel. Deswegen trifft die Formel auf alle möglichen Netze zu.

 

(*) Manchmal sieht man auch statt der 1 eine 2 in der Formel. Das liegt daran, dass manchmal die Außenfläche mitgezählt wird, ich habe sie allerdings nicht mitgezählt, deswegen steht im Text eine 1.