matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenKombinatorikRöhrenpost
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Informatik • Physik • Technik • Biologie • Chemie
Forum "Kombinatorik" - Röhrenpost
Röhrenpost < Kombinatorik < Stochastik < Oberstufe < Schule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Kombinatorik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Röhrenpost: Aufgabe
Status: (Frage) beantwortet Status 
Datum: 11:59 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
           /  \  / \
          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.)

        
Bezug
Röhrenpost: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 12:05 Di 16.10.2012
Autor: Diophant

Hallo sazzi und

[willkommenmr]

Könntest du uns der Form halber noch sagen, wo genau diese Aufgabe herstammt? Vielen Dank!


Gruß, Diophant

Bezug
                
Bezug
Röhrenpost: Antwort aus Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 13:04 Do 18.10.2012
Autor: sazzi

Ja das kann ich.
Unser Mathematiklehrer hat sie uns gestellt :)

Bezug
                        
Bezug
Röhrenpost: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 13:18 Do 18.10.2012
Autor: Diophant

Hallo sazzi,

> Ja das kann ich.
> Unser Mathematiklehrer hat sie uns gestellt :)

ok, ich habe die bisher gegebene Antwort wieder entschlüsselt. Ich bitte um Verständnis für meine Vorgehensweise: solche Kombinatorik-Aufgaben könnten Wettbewerbsaufgaben zu einem laufenden Wettbewerb sein; und es ist hier streng untersagt (wie anderswo auch), solche Aufgaben zu diskutieren.

Hat euer Lehrer denn etwas zu der Herkunft der Aufgabe gesagt, denn eine ganz gewöhnliche Schulbuchaufgabe scheint mir das denn doch auch nicht zu sein?


Gruß, Diophant


Bezug
                                
Bezug
Röhrenpost: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 14:20 Di 23.10.2012
Autor: sazzi

er meinte : " Hier, da könnt ihr in den Ferien (noch 2 Wochen), ein bisschen drauf herum beißen." Wo er die her hat weiß ich wirklich nicht.

Danke für die Hilfe

Bezug
        
Bezug
Röhrenpost: Idee
Status: (Antwort) fertig Status 
Datum: 14:43 Di 16.10.2012
Autor: pits

Hallo sazzi,

ich denke man muss erst mal eine Strategie entwickeln, wie man die Häuser geschickt anordnet um dann mit Hilfe eines Systems eine Formel zu entwickeln.

Ich würde dazu für feste Häuserzahlen K mal durchgehen, wie sich die Weglängen entwickeln, so z.B. wie das für 6 Häuser gemacht worden ist.

K=6:
Bei N=2 ist  1-2-3-4-5-6-1 eine gute Kombination, oder auch die einzige ;-) , der längste Weg ist von 1 nach 4 (bzw 2 nach 5 usw.)
Falls ich N=3 wähle kann ich die Wege optimieren, da würde ich dann 1 mit 4 verbinden usw., der Längste Weg ist dann von 1 nach 3 und ähnlich.
Bei N=4 gibt es immer noch ein Haus, das nicht direkt benachbart ist
Bei N=5 ist alles klar.

Das würde ich jetzt für mehrer Hausanzahlen ausprobieren und nach einem System ausschau halten.
Für N=2 ist die maximale Weglänge bei jedem K leicht zu ermitteln.
Für N=K-1 auch, K-2 wahrscheinich auch.

Viel Erfolg
pits

Bezug
                
Bezug
Röhrenpost: Frage (überfällig)
Status: (Frage) überfällig Status 
Datum: 14:23 Di 23.10.2012
Autor: sazzi

Ja das habe ich gemacht. Bei N=10 und k=3 z.B. wird es aber schon recht unübersichtlich. Außerdem bin ich mir bei meinen Zeichnungen nicht schlüssig ob ich nicht eine bessere Anordnung übersehen habe.

Außerdem verstehe ich nicht wie man das beweist.

Vielen Dank noch einmal für die Hilfe

Bezug
                        
Bezug
Röhrenpost: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 15:20 Do 25.10.2012
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
                        
Bezug
Röhrenpost: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 13:47 Fr 26.10.2012
Autor: sazzi

Aufgabe
Gleiche Frage

Ich weiß nicht warum die Zeit abgelaufen ist. Nächste Woche sind auch noch Ferien. Ich hätte die Antwort zu gern bei Mitte übernächster Woche.

Danke schön

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Kombinatorik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]