Mathematik, Was ist...?

Was ist… Topologie?

Bereits ein paar Mal habe ich die Topologie erwähnt und nie so wirklich erklärt, worum es sich dabei handelt. Das möchte ich heute ändern und euch zumindest eine Idee davon geben, womit sich Topologen beschäftigen und wie sie die Welt sehen.

Ähnlich wie in der Geometrie beschäftigt man sich in der Topologie mit Formen. Anders als Geometer interessieren sich Topologen aber nicht für konkrete Größen, Längen oder Winkelverhältnisse. Auch Unterscheidungen, auf welchen Oberflächen sich die Formen befinden, sind für topologische Betrachtungen komplett uninteressant.

Ein topologischer Quasikreis – Für einen Topologen ist das hier quasi ein Kreis. Klingt vielleicht eigenartig, ist aber so…

Warte, hier geht es weiter! …

Advertisements
Allgemein, Informatik, Mathematik

Über den Hamiltonkreis und NP-Vollständigkeit

Im heutigen Artikel möchte ich euch noch einmal mit in die Welt der Graphentheorie nehmen.

Vor einem Weilchen hatte ich euch ja bereits über das Königsberger Brückenproblem berichtet. Dabei ging es darum, dass Leonhard Euler ein einfaches Kriterium angeben konnte, wie sich die Anzahl der Brücken (dargestellt durch Kanten) und der Landteile (dargestellt durch Punkte / Ecken) zueinander verhalten müsste, damit es in einem Graphen einen Eulerkreis geben kann. Dabei ist ein Eulerkreis ein Weg durch den Graphen, bei dem jede Kante genau einmal passiert wird. Wer den kompletten Artikel dazu noch einmal lesen möchte, klickt HIER.

Der Graph zum Königsberger Brückenproblem. Einen Eulerweg gibt es nicht, wie ist es mit einem Hamiltonweg?

Heute geht es um eine ganz leicht veränderte Fragestellung, die aber einen riesigen Unterschied in der Lösung machen wird!

Warte, hier geht es weiter! …

Allgemein, Mathematik

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.

 

Warte, hier geht es weiter! …

Allgemein, Mathematik

Das Königsberger Brückenproblem

… und die Entstehung der Graphentheorie.

Leonhard Euler stieß auf ein Rätsel, was sich die Bewohner der Stadt Königsberg (heute Kaliningrad) ausgedacht hatten: Königsberg hatte vier Stadtteile, die durch insgesamt sieben Brücken über den Fluß Pregel miteinander verbunden waren. Die Bewohner fragten sich, ob es möglich wäre, einen Spaziergang zu machen, bei der jede Brücke genau einmal betreten würde. Natürlich kann man bei solch einem praktischen Problem erst einmal einige Versuche starten und sehen, ob man solch einen Weg findet. Findet man einen, ist das Problem gelöst. Findet man keinen, ist es aber noch lange nicht geklärt. Euler ging das Problem sehr mathematisch – logisch an, indem er es auf die Kernfrage zusammen schrumpfte und es somit noch klarer vor ihm lag: Statt sich selbst auf die Brücken zu stellen oder einen Stadtplan zu studieren, auf dem viele ablenkende Zusatzinformationen standen, zeichnete er ein Diagramm. Auf diesem Diagramm wurden die Stadtteile durch Punkte und die Brücken durch Linien gekennzeichnet.

Das ist eines der grundlegendsten Talente, die man als Mathematiker mitbringen sollte: So stark zu vereinfachen, wie es geht, aber eben nicht mehr! Man muss erkennen, was der Kern des Problems ist und darf sich nicht von unwichtigen Nebeninformationen ablenken lassen.

Warte, hier geht es weiter! …