Basiswissen

Eine Bedingung heißt notwendig für einen bestimmten Fall, wenn sie auf jeden Fall gelten muss, wenn der Fall zutreffen soll. Eine Bedingung heißt hinreichend, wenn bei Erfüllung der Bedingung der Fall zwangsläufig auch folgt. Bedingungen können notwendig aber nicht hinreichend oder auch notwendig und hinreichend zugleich sein. Für letztes steht hier ein Beispiel.

Königsberger Brückenproblem

Was interessiert: gibt es überhaupt eine Lösung?

Beim Königsberger Brückenproblem soll ein Pfad über insgesamt 7 Brücken gefunden werden, die zwei Inseln und zwei Flussufer untereinander verbinden: man soll genau einmal über jede Brücke laufen. Man darf also keine Brücke auslassen und man darf auch nicht zweimal oder noch öfters über eine einzelne Brücke gehen. Man kann diese Frage verallgemeinern zu einer beliebigen Anzahl von Brücken mit beliebig vielen Inseln und Festländern. Die Frage ist, ob es überhaupt einen möglichen Weg gibt. Die Frage kann nochmal in zwei Varianten aufgespalten werden. Die Varianten unterscheiden sich darin, ob man am Ende des Weges wieder am Anfangspunkt sein muss (geschlossener Pfad) oder nicht (offener Pfad). Ganz allgemein gilt:

a) Offener Pfad: einen Weg, der jede Kante genau einmal benutzt (Eulerpfad), gibt es nur, wenn genau 0 oder 2 Knoten eine ungerade Anzahl von Kanten haben.

b) Geschlossner Pfad: einen Rundgang (Eulerkreis) gibt es nur, wenn alle Knoten eine gerade Anzahl von Kanten haben sind.

Übersetzt für das Brückenproblem heißt das: wenn von jedem Ufer aus oder von jeder Insel aus entweder niemals oder nur genau zweimal eine ungerade Anzahl von Brücken wegführt, dann gibt es eine Lösung. Man kommt dann aber nicht am Startpunkt heraus, sondern irgendwo anders. Und: wenn von einem Ufer oder jeder Insel aus immer nur eine gerade Anzah von Brücken wegführt, dann kann man immer eine Lösung finden, bei der man am Ende auch wieder am Startpunkt herauskommt.

Wenn die Bedingungen nur notwendig wären, könnte man zwar prüfen, ob sie gelten. Aber damit wüsste man immer noch nicht sicher, ob es eine Lösung gibt. Da die zwei Bedingungen aber auch hinreichend sind, kann man sicher wissen, dass es auch Lösungen gibt. Das kann man praktisch nutzen.

Wer zum Beispiel einen Graphen zeichnen möchte, für den es ganz sicher einen geschlossenen Weg, einen sogenannten Eulerkreis, als Lösung gibt, kann ganz einfach so vergehen:

Zeichne eine beliebige Anzahl von Punkten.

Verbinde die Punkte so dass von jedem Punkt immer eine gerade Anzahl von Linien zu einem anderen Punkt ausgeht.

Jeder Punkt muss über irgendeinen Pfad mit jedem anderen Punkt verbunden sein (es darf keine Inseln von Punkten geben).

Wenn man diese hinreichende Bedingung einhält, dann hat der gezeichnete Graph auf jeden Fall einen Eulerkreis als geschlossenen Weg. Diesen Weg dann auch noch zu finden, ist allerdings ein ganz anderes Problem. Mit den Bedingungen weiß man erst einmal nur, dass sich die Suche am Ende gelohnt haben wird. Siehe dazu auch 👉 Königsberger Brückenproblem

Fußnoten

[1] Der amerikanische Mathematiker Joel David Hamkins behandelte das Thema im Jahr 2014 in einem Schulprojekt mit 8 Jahre alte Mädchen aus der Klasse seiner Tochter. Dazu schrieb er: "It is a remarkable fact that amongst connected finite graphs, those necessary conditions are also sufficient. One can prove this by building up an Eulerian path or circuit (starting and ending at the two odd-degree nodes, if there are such); every time one enters a new vertex, there will be an edge to leave on, and so one will not get stuck. If some edges are missed, simply insert suitable detours to pick them up, and again it will all match up into a single path or circuit as desired." Joel David Hamkin: Math for seven-year-olds: graph coloring, chromatic numbers, and Eulerian paths and circuits. 29. Mai 2014. Online: https://jdh.hamkins.org/math-for-seven-year-olds-graph-coloring-chromatic-numbers-eulerian-paths/