x

graphen
Euler's Problem der Brücken von Königsberg und ein dazu passender Graph (Königsberger Brückenproblem)

War es im damaligen Königsberg möglich einen Stadtumzug abzuhalten, so dass jede Brücke überschritten wurde, aber keine von ihnen öfter als einmal? Dieses Problem bereitete Carl Leonhard Gottlieb Ehler schlaflose Nächte und schließlich wandte er sich an Leonhard Euler. Dieser lehnte zunächst ab, da es sich um kein geometrisches Problem handelte. Aber schließlich bereitete er mit einer Lösung den Weg für eine neue mathematische Disziplin, die wir heute Graphentheorie nennen, indem er das Prinzip verallgemeinerte. Seine erste Erkenntnis war, dass jede Landmasse durch einen einzelnen Punkt auf einem Blatt Papier dargestellt werden kann und jede Brücke als Liniensegment, das die entsprechenden Punkte verbindet. Das nennen wir heute einen Graph. Die Punkte nennen wir Knoten (auf englisch: vertices) und die Linien Kanten (auf englisch: edges). Euler erkannte, dass es entscheidend war, sich darüber Gedanken zu machen, wie viele Kanten in einen Knoten münden. Für die Knoten 1, 3 und 4 ist diese Zahl (heute Knotengrad genannt) gleich drei, für den Knoten 2 gilt g(2) = 5. Denk, denk, denk, ... 😁

Graphentheorie hat nicht nur für Transportwesen, Kommunikation, Verkehrssysteme und Operations Research Bedeutung erlangt, sondern auch auf vielen anderen Gebieten. In den letzten Jahrzehnten kamen mathematische Computerwissenschaften dazu wie Datenstrukturen und Informationsflüsse.

dowload PDF: GRUNDBEGRIFFE DER GRAPHENTHEORIE
Siehe auch: Carl Leonhard Gottlieb Ehler