Hallo Leute,
ich bin sehr schlecht in Beweisaufgaben. Hat jemand eine Idee?
Wir können weiter diskutieren. Bitte hilf mir.
Hier ist meine Aufgabe:
Wir wollen das kurzeste Straßennetz bauen, das n Städte verbindet, d.h. die Summe der Langen aller Straßenabschnitte soll minimiert werden (ein Problem, an dem schon Gauß gearbeitet hat).
Sei p die Zahl der Kreuzungen, die zusätzlich zu den Städten eingeführt
werden. Das Netzwerk hat dann also (n + p) Knotenpunkte. Beweisen Sie, dass fur das kürzeste Straßennetz p <= n - 2 gelten muss. Dabei können Ihnen folgende Schritte als Hilfestellung
dienen:
1. Die kurzeste Straße zwischen zwei Knotenpunkten ist eine Gerade.
2. In einer Kreuzung mussen sich mindestens 3 Straßen treffen (sonst kann sie einfach eliminiert werden).
3. Folgern Sie, dass die Zahl der Straßen mindestens (3p + n)/2 sein muss.
4. Zeigen Sie, dass das kurzeste Straßennetz mit n + p Knoten höchstens
n + p - 1 Straßen hat.
5. Schließen Sie, dass das kurzeste Straßennetz zwischen n Städten höchstens n − 2 Kreuzungen hat.
Betrachten Sie nun 4 Städte auf den Ecken eines Quadrats. Finden Sie die kurzesten Straßennetze mit p = 0, 1, 2 Kreuzungen. Was ist das kurzeste aller möglichen Straßennetze?
