Da es hierzu ja noch gar keinen Hinweis gab, kommt jetzt ein etwas deutlicherer dazu.

Auch wenn sich hinter dieser Aufgabe ein Standard-Problem aus der Graphentheorie verbirgt, so kann man diese Aufgabe auch einfach durch "Malen" lösen - also Punkte für die Sender und Linien zwischen zwei Punkten, wenn diese nahe genug beieinander liegen.
Das könnte dann so ähnlich aussehen:

Das linke Bild zeigt dabei eine Sendeleistung, die nicht ausreicht: Wenn der Sender in der Mitte ausfällt, können die drei auf der linken Seite nicht mehr mit den dreien auf der rechten Seite kommunizieren. Erhöht man die Reichweite der Sender, dann wird das Netz dichter, und bei Ausfall eines Senders gibt es noch eine Ersatzroute.

So, dann wollen wir das mal auflösen. Die richtige Antwort ist: 85 wm.

Man kann diese Aufgabe durch malen und scharf hingucken lösen. Eine Online-Lösung dazu hat Christian S. schon in der Shoutbox vorgestellt, eine für Delphi ist im Anhang.

Wenn die Sendeleistung bei 80wm liegt, dann gibt es in der Ecke "NRW/Niedersachsen" einen Zipfel, der von dem Rest des Netzes bei Ausfall eines Knotens getrennt werden kann. Bei 83wm kommt an dieser Stelle eine Ausweichroute hinzu.

Wenn man das algorithmisch lösen möchte, dann ist der Begriff "zweifacher Zusammenhang" eines Graphen interessant. Dieser lässt sich effizient mit einer Tiefensuche berechnen. Man müsste dann für die einzelnen Sendeleitungen den so genannten Unit-Disk-Graphen mit dem passenden Radius aufbauen und diesen auf zweifachen Zusammenhang testen. Diese Unit-Disk-Graphen spielen bei der Modellierung von mobilen Adhoc-Netzen eine große Rolle, zum Beispiel im Gebiet "Sensornetze" oder auch bei der "Fahrzeug-zu-Fahrzeug-Kommunikation".

Ich habe zum Lösen minimale Spannbäume des Graphen berechnet und nacheinander je einen Knoten rausgenommen.
Von dann ist die Entfernung die längste Kante aller minimalen Spannbäume.

Als Grund-implementierung hab ich mir dazu den Code von narses zu WLAN-Kabeln letztes Jahr kopiert
War dann schon fast zu einfach

Könntest du das mit den minimalen Spannbäumen mal genauer erläutern? Was ein minimaler Spannbaum ist, ist mir klar, aber wie kann man den für die Aufgabe hier verwenden?

Eine Frage bleibt noch aus ...
Warum braucht der Weihnachtsmann in Deutschland ein Netzwerk?
Und warum ist ein Wichtelmeter ca 1,5 Kilometer wenn doch die Wichtel (Vermutlich) kleiner sind?

Niko S. hat folgendes geschrieben :

Und warum ist ein Wichtelmeter ca 1,5 Kilometer wenn doch die Wichtel (Vermutlich) kleiner sind?

Wurde von dem Weihnachtswichtel William J. Ichtel (abgekürzt W.Ichtel) erfunden um dem Weihnachtsmann eine bessere Berechnung der Route zu ermöglichen. Er war ebenso der derjenige der versucht hat das Kilometermaß in England einzuführen. Leider ist er bei dem Versuch gestorben.

Niko S. hat folgendes geschrieben :

Warum braucht der Weihnachtsmann in Deutschland ein Netzwerk?

Verteilte Systeme. Ist effizienter die Wünsche aufzuteilen als alle am Nordpol in eine riesige Serverfarm anzulegen. Außerdem würde die Serverfarm zum schnelleren Schmelzen der Polkappen führen.

This Signature-Space is intentionally left blank.
Bei Beschwerden, bitte den Beschwerdebutton (gekennzeichnet mit PN) verwenden.

Weil die Wichtel 1.5 Km an einem Tag gehen können
Ich habe erst eine Algorithmische Lösung versucht, Hatte den Graphen auch schon in einer Adjazenzmatrix, bin dann aber an der Tiefensuche gescheitert.
Dann hab ichs einfach durch malen gelöst...

hi

Lösungen werden gerne getestet

E: Setzen weiterer Punkte entweder per Mausklick oder manuell, Ändern der Reichweite per Scrollrad.

PS: Ich sehe gerade, mit Gausis Programm sind es eigentlich genau genommen 83WM Sollte ich mit meinen 84 einem Rundungsfehler unterliegen?

Sagt mal, ist das hier die Lösung vom Adventsgewinnspiel 2009 - 2. Gewinnspiel?? Weil wenn ja herrscht da ech Erklär Bedarf für mich.

JungerIslaender hat folgendes geschrieben :

Sagt mal, ist das hier die Lösung vom Adventsgewinnspiel 2009 - 2. Gewinnspiel?? Weil wenn ja herrscht da ech Erklär Bedarf für mich.

Wenn ich nicht ziemlich absolut falsch liege, ist sie das Was können wir für dich tun?

@Hidden: Ja du hast da einen Fehler. Genau wären es 82.73 wm

@Gausi:
Ok, ein minimaler Spannbaum verbindet alle Punkte eines Graphen und achtet dabei darauf, dass die Verbindungen so kurz wie möglich sind.
Also wenn ich einen minimalen Spannbaum zu dem Graphen finden kann, dessen längste Kante <= der Rechweite ist, sind alle Stationen damit erreichbar.

Rest ist nur noch "probieren":
1. Knoten fällt aus, welche Reichweite brauche ich? -->Minimaler Spannbaum, längste Seite wählen
2. Knoten fällt aus. Das gleiche nochmal.
So dann man der Reihe nach jeweils einen Knoten ausblenden und von allen längsten Seiten des MSB die längste nehmen, um sicherzustellen, dass mit dieser Reichweite in jedem möglichen Graphen, bei dem 1 Knoten fehlt, ein MSB mit Kantenlänge <= dieser Länge existiert.

Das ganze dann noch grafisch kontrolliert, in dem ich mir alle Kanten mit länge >80wm rot anzeigen lassen hab, und damit das Problem bei einer Reichweite von nur 80wm direkt sehen konnte.

Mein erster Ansatz war aber auch, einen Slider o.ä. zu nehmen und einfach "zu gucken"

Hidden hat folgendes geschrieben :

PS: Ich sehe gerade, mit Gausis Programm sind es eigentlich genau genommen 83WM Sollte ich mit meinen 84 einem Rundungsfehler unterliegen?

Mein Programm sagt mir das 83 WM die erste ganzzahlige Reichweite ist, bei dem die Aufgabe gelöst ist.
(siehe Anhang, source enthalten)

@Hidden: Nein, dein Programm liefert doch auch 83. Nur über das Scrollrad kommst du nur in Zweierschritten an die Lösung ran. Bei einer Direkteingabe der 83 oben in das Edit kommt auch schon die fehlende Verbindung.

@Spannbäume: Ah, ok. Mit dem Spannbaum bekommst du die Reichweite, die man für einfachen Zusammenhang braucht. Und wenn du jeden Knoten je einmal rausnimmst und für diesen Graphen den Zusammenhang über den MST herstellst und dir dabei das Maximum der benötigten Reichweiten merkst, kommst du dahin. Ok, Algorithmus verstanden.

Das ist meine Lösung, da ist auch noch ein Ansatz für die "Richtige" Lösung drin, aber da bin ich an der Tiefensuche gescheitert.

Gausi hat folgendes geschrieben :

@Hidden: Nein, dein Programm liefert doch auch 83. Nur über das Scrollrad kommst du nur in Zweierschritten an die Lösung ran. Bei einer Direkteingabe der 83 oben in das Edit kommt auch schon die fehlende Verbindung.

Oh Ich war mir so totsicher dass ich's garnicht mehr ausprobiert habe vor dem Posten^^

habs auch richtig

82,7 sind mindestens nötig

Danke für die Rätsel!

Sylvus hat folgendes geschrieben :

habs auch richtig 82,7 sind mindestens nötig Danke für die Rätsel!

Mit 82,7 kommst du noch nicht hin
82,73 wm sind es genau. Also wären deins gerade so zu kurz

Aber Lösung am Ende stimmt ja.

als wenn wir jetzt so anfangen reicht deins aber auch nicht

es müssen schon 82,74 oder besser:
82,734515167492218767139425743058 wm sein!

Können wir uns einfach auf √6845 einigen ?

Besser 37√5
Das ist schöner!
Teilweises radizieren FTW!!