Graphrepräsentationen SS12
Inhaltsverzeichnis |
Rückblick
Sortierte Folgen
Graphentheorie
Königsberger Brückenproblem
Beim Königsberger Brückenproblem handelt es sich um eine mathematische Fragestellung aus dem 18. Jahrhundert. Königsberg wurde am Fluss Pregel erbaut, welcher sich im Stadtgebiet teilt. Über die beiden Flussarme wurden mehrere Brücken gebaut, um schnell von einem Stadtteil zum anderen zu gelangen. Im Jahr 1736 gab es sieben Brücken. Die Einwohner Königsbergs stellten sich die Frage, ob es möglich ist, alle sieben Brücken nur genau einmal zu überqueren. Wenn dies möglich ist, kann man auch einen Rundweg gestalten, bei dem man am Ende wieder am Ausgangspunkt ankommt?
Diesen Fragen nahm sich Leonhard Euler, ein bis heute bedeutender Mathematiker an. 1736 veröffentlichte er seine Arbeit "Solutio problematis ad geometriam situs pertinentis", in der er sich mit dem Königsberger Brückenproblem befasst. Er versuchte sich bei der Untersuchung des Problems nur auf die relevanten Informationen zu beschränken. So stellte er fest, dass es vier Stadtteile gab, die durch sieben Brücken verbunden sind. Er repräsentiert jeden Stadtteil durch eine Punkt und jede Brücke stellt eine Linie, also eine Verbindung zwischen zwei Stadtteilen dar. Nach dem Zusammenfügen aller dieser Informationen erhält man die nachfolgende Grafik.
Durch dieses grafische Hilfsmittel ist leicht zu erkennen, dass das Königsberger Brückenproblem nicht lösbar ist. Beim Passieren eines Punktes (Stadtteil) müssen zwei Linien (Brücken) durchlaufen werden (hinein und hinaus). Egal wie in welcher Reihenfolge man versucht die Brücken zu überqueren, ist es unmöglich jede Brücke nur einmal zu benutzen. Somit ist auch ein Rundgang, bei dem Anfangs- und Endpunkt übereinstimmen unmöglich. Um beide Fragen positiv beantworten zu könne, müsste von jedem Punkt eine gerade Anzahl von Linien ausgehen, d.h. ein Stadtteil muss mit einer geraden Anzahl von Brücken erreichbar sein.
Leonhard Eulers Arbeit zum Königsberger Brückenproblem gilt als eine der ersten Arbeiten auf dem Gebiet der Graphentheorie.
Grundlegende Begriffe
Graph
Kante
Ecke
Graph
test
dszlkshflkashflkaf