0 Daumen
478 Aufrufe


Die Städte \( S_{1}, \ldots, S_{n}(n \geq 1) \) seien untereinander durch Straßen verbunden und zwischen zwei Städten gibt es immer genau eine Straße. Wegen Bauarbeiten sind zur Zeit alle Straßen nur in eine Richtung befahrbar. Zeigen Sie, dass es trotzdem mindestens eine Stadt gibt, von der aus alle anderen Städte erreichbar sind.
Hinweis: Vollständige Induktion.

Avatar von

1 Antwort

0 Daumen

O.b.d.A. seien von Sn aus alle Städte erreichbar.

Es wird die Stadt Sn+1 gebaut und mit allen anderen Städten verbunden.

Die Verbindung zwischen Sn und Sn+1 läuft entweder in die Richtung von Sn nach Sn+1, oder in die Richtung von Sn+1 nach Sn. Im ersten Fall sind alle Städte von Sn aus erreichbar. Im zweiten Fall sind alle Städte von Sn+1 aus erreichbar.

Avatar von 105 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community