Das Königsberger Brückenproblem | MathePrisma

Das Königsberger Brückenproblem

Andere Städte

Einleitung

Mathematisch

Lösung

Andere Städte

Euler

Arbeitsblatt

Aufgabe 1

(mathematische Aufbereitung)

Betrachtet werden die beiden Stadtpläne

a) Bezeichnen Sie in beiden Stadtplänen die Gebiete und Brücken mit Buchstaben.

b) Geben Sie für beide Stadtpläne einen Weg (in Gestalt einer Buchstabenfolge) an, der genau vier verschiedene Brücken benutzt.

Aufgabe 2

(Eulerbedingung, Zusammenhangsbedingung)

a) Für welche der beiden Stadtpläne existiert ein Weg, der jede Brücke genau einmal benutzt? Begründen Sie Ihre Antwort.

b) Geben Sie im Falle der Existenz einen solchen Weg an. Existiert auch ein Rundweg, der jede Brücke genau einmal benutzt?

c) Wenn der gesuchte Weg nicht existiert: Welche Brücken muss man ergänzen, damit er existiert?

Aufgabe 3

(indirekter Beweis)

Eine Primzahl ist eine natürliche Zahl > 1, die nur durch sich selbst und durch 1 geteilt werden kann.

Sind $\text{p}_1$ , $\text{p}_2$ , ..., $\text{p}_m$ endlich viele Primzahlen und ist $\text{p} \, = \, \text{p}_1 \cdot \text{p}_2 \cdot ... \cdot \text{p}_m \, + \, 1$ , so ist $\text{p}$ entweder selbst eine Primzahl oder durch eine von $\text{p}_1$ , $\text{p}_2$ , ..., $\text{p}_m$ verschiedene Primzahl teilbar.

Formulieren Sie einen auf dieser Beobachtung fußenden indirekten Beweis für die Aussage: "Es gibt unendlich viele Primzahlen".

Aufgabe 4

(notwendige und hinreichende Bedingung)

Betrachtet werden folgende Aussagen über natürliche Zahlen p > 1:

A1: p ist keine Quadratzahl
A2: p ist durch keine Primzahl < p teilbar
A3: im Dezimalsystem besitzt p eine ungerade Endziffer
A4: p+2 ist Primzahl

Welche dieser Aussagen sind notwendig, welche hinreichend, welche notwendig und hinreichend für die Aussage

A5: p ist eine Primzahl

Aufgabe 5

Das Spiel "Haus vom Nikolaus" besteht darin, nebenstehende Figur ohne abzusetzen aufzuzeichnen.

a) Erklären Sie, weshalb dieses Spiel als Brückenproblem betrachtet werden kann. Zeichnen Sie den zugehörigen Stadtplan auf. (Achtung: Luftbrücken!)

b) An welcher Stelle muss man mit dem Zeichnen beginnen, damit man ohne abzusetzen zum Ziel kommt? Verwenden Sie a) zur Begründung.

Drucken

Eulerbedingung ist keine hinreichende Bedingung

Für den Stadtplan 2 existiert kein gesuchter Weg, obwohl die Eulerbedingung erfüllt ist.
Die Eulerbedingung alleine ist also nicht hinreichend für die Existenz eines gesuchten Weges.

Nochmals: Stadtplan 2

Bei Beispiel 2 fällt auf: Man kommt von Gebiet A (oder B) aus nicht zu Gebiet C (oder D). Wir formulieren deshalb folgende Zusammenhangsbedingung:

Definition: Zusammenhangs- bedingung

Zusammenhangsbedingung:

Von jedem Gebiet X aus gibt es einen Weg zu jedem anderen Gebiet Y.

Die Zusammenhangsbedingung ist ebenfalls eine notwendige Bedingung für die Existenz eines gesuchten Weges.

Zu zeigen:
aus Aussage 2 folgt Aussage 1

Beweis:

Aussage 1: Die Zusammenhangsbedingung ist erfüllt.
Aussage 2: Ein gesuchter Weg existiert.

Existiert ein gesuchter Weg, so kommen jedes beliebige Gebiet X und jedes weitere Gebiet Y in diesem Weg vor.
Das Teilstück zwischen X und Y im gesuchten Weg ist ein Weg von X nach Y.
Also können X und Y verbunden werden.
Damit ist die Zusammenhangsbedingung erfüllt.

Als unser zentrales Ergebnis wollen wir jetzt herleiten:

Eulerbedingung und Zusammenhangsbedingung gemeinsam sind eine hinreichende Bedingung für die Existenz eines gesuchten Weges.

Dabei gehen wir konstruktiv vor. Wir zeigen also nicht nur, dass dann ein gesuchter Weg existiert, wir geben auch an, wie man ihn konstruiert.