Statt unvollständige Rundwege einfach zu verwerfen und einen neuen Versuch zu starten, wollen wir jetzt überlegen, wie wir solche Wege weiter ausbauen können.
Die Versuche zeigen:
2. Beobachtung
In einem unvollständigen Rundweg existiert immer ein Gebiet, aus welchem noch nicht begangene Brücken führen.
Wir können den unvollständigen Rundweg also in diesem Gebiet "aufbrechen" und mit der nicht begangenen Brücke weiter ausbauen.
Demonstration dieser Beobachtung
anhand von Beispielen bei Stadtplan 3.
Zurück zu Stadtplan 3
Auch diese Beobachtung wollen wir beweisen.
Behauptung: In einem unvollständigen Rundweg befindet sich immer ein Gebiet X mit noch nicht begangener Brücke.
Verwendung der Zusammenhangs- bedingung
Beweis:
Ausgangssituation (Rundweg)
Da insgesamt noch nicht alle Brücken begangen sind, existiert eine unbegangene Brücke. Wir nennen sie YZ.
unbegangene Brücke YZ
Mit G bezeichnen wir ein (beliebig gewähltes) Gebiet aus dem unvollständigen Rundweg. Aufgrund der Zusammenhangsbedingung gibt es einen Weg von G nach Y.
Weg von G nach Y
Falls der Weg von G nach Y die Brücke YZ nicht schon beinhaltet, bauen wir ihn durch Anhängen von YZ zu einem Weg nach Z aus.
Weg von G nach Z
Von diesem Weg suchen wir die erste unbegangene Brücke heraus. Eine solche existiert stets (spätestens ist es YZ). Diese Brücke startet in einem Gebiet X.
Gebiet X mit erster unbegangener Brücke
Weil sie die erste unbegangene Brücke ist, ist die Vorgängerbrücke (diese endet in X) bereits begangen worden. Das bedeutet X befindet sich im unvollständigen Rundweg.
|
|
|
