Röhrenpost < Kombinatorik < Stochastik < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) für Interessierte  | | Datum: | 11:57 Di 16.10.2012 | | Autor: | sazzi |
| Aufgabe | Ein Ort will mehrere Häuser mit einem Röhrenpostsystem ausstatten. Jedes Haus kann nur N Zu-/Ableitungen besitzen (Briefe können pro Röhre in beide Richtungen verschickt werden).
Jedes Haus kann nur N Nachbarn direkt eine Nachricht schicken. Wenn eine Nachricht zwischen 2 Häusern verschickt wird, welche nicht direkt benachbart sind, soll diese über möglichst wenige andere Häuser weitergeleitet werden.
Aufgabe A:
N=3, Anz.Häuser=6
Überprüfe über wie viele Stationen ein Brief verschickt werden muss um alle Nachbarn zu erreichen! Wie viele Station sind bei geschickter Anordnung maximal nötig um Briefverkehr zwischen allen Häusern sicher zu stellen?
Aufgabe B:
Finde eine allgemeine Formel für N direkte Nachbarn und K Häuser! Beweise! |
A: Lösung:
1-2-3-4-5-6 : schlechte Anordnung (N=2):
längste Verbindung: Weiterleitung über 4 Häuser wenn 1 <-> 6 eine Nachricht schicken will.
Gute Anordnung
1 - 2
/ \ / [mm] \
[/mm]
3----X--- 4
\ / \ /
5 - 6
längste Verbindung 2; Weiterleitung über max. ein anderes Haus: Z.B. wenn 1 <-> 5 eine Nachricht schickt, dann Weiterleitung über 3 oder 6.
-> Bis hierhin ist es einfach :D
-> aber B ?? Wie kann man denn daraus eine Formel ableiten? Wie beweist man denn so etwas?
Hiiiilfe ;)
(Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.)
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:06 Di 16.10.2012 | | Autor: | Diophant |
Hallo sazzi,
bitte stelle jede Aufgabe nur einmal ein.
Gruß, Diophant
|
|
|
|
