lösung Zahl Städte Bedingung Städten Bahnlinie Stadt A

bahnlinien (not that easy)

Von: , Frage gestellt am Mi, 16. Jun 2004

Hi Rätselfreunde,

Gegeben seien n Städte. Zwischen diesen sollen Eisenbahnstrecken eingerichtet werden. Dabei sollen allerdings ein paar Bedingungen eingehalten werden. Von und zu jeder Stadt gibt es Bahnstrecken jeweils in exakt gleicher Zahl von und zu anderen Städten. Also alle Städte sind direkt (ohne Zwischenstop) mit genau m anderen Städten per Bahnlinie verbunden. Und eine zweite Bedingung gilt. Zwischen je zwei Städten, gibt es eine Bahnreiseroute, derart, das auf der Bahnreise von Stadt A nach Stadt B maximal eine weitere Stadt als Zwischenstation durchfahren wird. Dank Weichen und Bahnbrücken, stellen Kreuzungen kein Problem dar und dürfen vorkommen.
Die Frage lautet: wieviel Städte sind es, die auf diese Weise miteinander verbunden sind? also wie groß ist n?

Ok. die Frage ist nicht ganz fair, weil sie nicht eindeutig zu beantworten ist. Deshalb eine kleine Einschränkung: wenn ich mehr als 100 aber weniger als 1000 Städte will, kann mir dann jemand die genaue Zahl an Städten nennen?

rauchende köpfe wünscht

unimportant

3 Antworten zu dieser Frage

1. Antwort von nach 10 Stunden 0 hilfreich

   Re: bahnlinien (not that easy)

   Hallo,
   sind die einzelnen Strecken nur in einer Richtung passierbar ? Wenn ich die Aufgabe richtig verstehe, ist zu einem fixen aber beliebigen m das ein n gesucht, so daß es ein Verbindungsnetz gibt, daß die zwei Bedingungen erfüllt. Fordert man für n, daß es maximal ist, würde ich annehmen, daß es eindeutig wird.
   Mich irritiert diesbzgl. nur Deine zusätzliche Einschränkung 100<=n<=1000 zu betrachten.
   
   Gruss
   Enno
   

   • Antwort von nach 11 Stunden 0 hilfreich

     Zusatz

     Hi, Hallo,
     sind die einzelnen Strecken nur in einer Richtung passierbar ?
     nein, immer in beide Richtungen. Wenn ich die Aufgabe richtig verstehe, ist zu einem fixen aber
     beliebigen m das ein n gesucht, so daß es ein Verbindungsnetz
     gibt, daß die zwei Bedingungen erfüllt. Fordert man für n, daß
     es maximal ist, würde ich annehmen, daß es eindeutig wird.
     Mich irritiert diesbzgl. nur Deine zusätzliche Einschränkung
     100<=n<=1000 zu betrachten.
     nicht ganz, bereits ohne Annahme über m soll n folgen.
     Daraus lässt sich unmittelbar schlußfolgern, dass es wirklich nicht allzuviele verschiedene n gibt, für die das Problem lösbar ist.
     
     nur Mal so als Beispiele: das Problem ist für n=2 lösbar, und zwar mit dem vollständigen Graphen K₂ in diesem Fall wäre m=1.
     Für n=3 und n=4 gibt es keine Lösung. Für n=5 gibt es wieder eine Lösung und zwar der Graph, der lediglich einen Kreis durch die 5 Knoten bildet. Da wäre m=2. Das nächstgrößere n wäre n=10 mit dem Petersen-Graphen und m=3. Dass sollte als Anschauungsmaterial genügen.
     
     Ich hab mir aber leider eine kleine Unexaktheit in der Formulierung geleistet. Statt Zwischen je zwei Städten, gibt es eine Bahnreiseroute, derart, das auf der Bahnreise von Stadt A nach Stadt B maximal eine weitere Stadt als Zwischenstation durchfahren wird.
     muss es korrekt lauten: 'Zwischen je zwei Städten, gibt es genau eine Bahnreiseroute, derart, das auf der Bahnreise von Stadt A nach Stadt B maximal eine weitere Stadt als Zwischenstation durchfahren wird.'
     
     aber dass die Lösung nicht gerade einfach ist, das gilt immer noch.
     jedoch kann man sich dem Problem durchaus durch Überlegungen annähern, also man muss jetzt nicht wirklich jedes n zwischen 100 und 1000 untersuchen und muss das Problem auch nicht mit dem Computer bruteforcen.
     
     Vielleicht, weil es wirklich nicht ganz einfach ist, noch als Info:
     
     es gibt genau 6 Zahlen n, für die das Problem lösbar ist, das sind 2,5,10,50,3250 sowie die gesuchte Zahl. Damit kann man schon mal ganz gut überprüfen, ob die Überlegungen in die richtige Richtung gehen.
     
     dann noch viel Spaß
     
     unimportant
     
     

     • Antwort von nach 6 Tagen 0 hilfreich

       Re: Zusatz

       Hallo,
       poste bitte vorerst erst mal keine Antwort. Ich komme erst heute abend dazu, mir das Problem näher anzuschauen.
       
       Gruss
       Enno
       

Keine passende Antwort gefunden? Jetzt eigene Frage stellen!