Königsberger Brückenproblem

Das Königsberger Brückenproblem

Das Königsberger Brückenproblem ist ein 1736 von Leonhard Euler gelöstes Problem aus der Graphentheorie. Am konkreten Beispiel bezieht es sich auf die Stadt Königsberg (heute Kaliningrad) und die Frage, ob es einen Rundweg gibt, bei dem man alle sieben Brücken der Stadt über den Pregel genau einmal überquert und wieder zum Ausgangspunkt gelangt.

Das Problem lässt sich auf beliebige Graphen und die Frage, ob es darin einen Kreis gibt, der alle Kanten genau einmal benutzt, verallgemeinern. Ein solcher Kreis wird als Eulerkreis bezeichnet und ein Graph der einen Eulerkreis besitzt als eulersch.

Die Frage, ob ein Graph eulersch ist, lässt sich relativ einfach beantworten und auch ist auch in gerichteten Graphen und Graphen mit Mehrfachkanten möglich. Das analoge Konzept eines Kreises, der alle Knoten genau einmal besucht nennt man Hamiltonkreis beziehungsweise einen Kreis, der einen Hamiltonkreis besitzt hamiltonsch.