Land habe n Städte. Zeigen, dass es eine Route gibt, die jede Stadt genau einmal besucht.

Question

ich finde gerade nicht heraus wie ich das lösen soll

Induktionsbeweis

Aufgabe:

Ein Land habe n Städte, so dass je zwei Städte durch eine Einbahnstraße verbunden sind. Zeigen sie, dass es eine Route gibt, die jede Stadt genau einmal besucht.

Ansatz:

IA: für n = 2 ist trivial

IV: 2 Städte sind durch eine Einbahnstrecke verbunden

IS: n -> n+1

und ab hier weiß ich net weiter.

Comments

Deine IV ist falsch.

Answer 1

IV: 2 Städte sind durch eine Einbahnstrecke verbunden

IV ist "Für jede Menge von n Städten gibt es eine Route, die jede Stadt genau ein mal besucht."

IS: Seien A₁ ... A_n+1 Städte. Laut IV gibt es eine Route s₁, ..., s_n-1, die die Städte A₁, ..., A_n genau ein mal besucht. Ende dieser Route sei die Stadt A. Laut Voraussetzung gibt es eine Einbahnstraße s von A nach A_n+1. Dann ist s₁, ..., s_n-1, s eine Route, die jede der Städte A₁ ... A_n+1 genau ein mal besucht.

Comments

Fragt sich nur, ob man deine Route auch befahren kann. Das dürfte mit der Fragestellung nämlich gemeint sein.

---

Die eigentliche Frage ist doch, was die Aufgabe ist.

Soll die Aussage bewiesen werden, dann ist "je zwei Städte durch eine Einbahnstraße verbunden sind" so gemeint, dass sowohl von A nach B eine Einbahnstraße existiert, als auch eine von B nach A, oder die Befahrbarkeit der Route ist nicht relevant. Sonst wäre die Aussage nämlich falsch.

---

Sonst wäre die Aussage wegen A←B→C nämlich falsch.

Dein zweiter Irrtum.

---

Ich bin heute echt noch nicht wach.

---

Also stimmt es nicht, was du oben geschrieben hast?