Die Mathe-Redaktion - 17.12.2017 12:44 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden oder den Newsletter bestellen.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 761 Gäste und 25 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Kombinatorik & Graphentheorie » Möglichkeiten, Knoten zu durchlaufen
Druckversion
Druckversion
Autor
Universität/Hochschule J Möglichkeiten, Knoten zu durchlaufen
chip
Neu Letzter Besuch: im letzten Monat
Dabei seit: 17.11.2017
Mitteilungen: 4
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2017-11-17


Hallo zusammen,

die Aufgabe ist die folgende: Angenommen man habe n Knoten. Einer der Knoten sei als Start-Knoten markiert. Wie viele Möglichkeiten gibt es die Knoten zu durchlaufen, sodass jeder mindestens einmal durchlaufen wird?

So wie ich das sehe, ist es dabei egal, ob
- man von Knoten 1 in alle anderen kommt
- oder man bei Knoten 1 startet, dann in 2 geht, ....., bis man bei Knoten n angelangt ist
- oder eine Mischform daraus.

Folgende Lösungen habe ich mit einem Baumdiagramm erhalten:
n=2: 1 Möglichkeit
n=3: 3 Möglichkeiten
n=4: 16 Möglichkeiten
n=5: 95 Möglichkeiten
n=6: 656 Möglichkeiten

Ich schaffe es aber nicht, auf eine allgemeine Formel zu kommen.

Meine Fragen sind nun:
1. Sind die Lösungen denn überhaupt richtig?
2. Kann daraus eine allgemeine Formel abgeleitet werden?

Ich freue mich über jede Hilfe.
Danke schon mal im Voraus.





  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 3719
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2017-11-17


Hallo chip,

willkommen auf dem MP!

Zu deiner Aufgabe:
- Meinst du wirklich mindestens oder genau ein Mal?
- Dürfen die Knoten in beliebiger Reihenfolge durchlaufen werden, oder gibt es Einschränkungen?
- Wie kommst du bei n=3 auf 3 Möglichkeiten?

Gruß
StrgAltEntf



  Profil  Quote  Link auf diesen Beitrag Link
chip
Neu Letzter Besuch: im letzten Monat
Dabei seit: 17.11.2017
Mitteilungen: 4
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2017-11-17


Hallo,

Ich meine tatsächlich mindestens einmal. Und die Knoten können in beliebiger Reihenfolge durchlaufen werden. Der Hintergrund ist Grundrisserstellung. Es geht um die Frage, wie n Räume (Knoten) mit minimaler Anzahl an Links (n-1) verbunden sein können, sodass die Zugänglichkeit immer gewährleistet wird. Mir fällt gerade auch auf, dass die n-1 Links in meiner ursprünglichen Frage fehlen.

Auf die 3 komme ich folgendermaßen:
Knoten 1 sei der Startknoten
- von Knoten 1 zu Knoten 2 und 3
- von Knoten 1 zu Knoten 2 zu Knoten 3
- von Knoten 1 zu Knoten 3 zu Knoten 2

Also  (2 über 2) + (2 über 1) * (1 über 1) = 1 + 2*1 = 3

Danke schon mal und viele Grüße



  Profil  Quote  Link auf diesen Beitrag Link
viertel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2003
Mitteilungen: 26070
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2017-11-17


Hi chip

Willkommen auf dem Planeten

chip schreibt:
Ich meine tatsächlich mindestens einmal.
Bei <math>n-1</math> Links, wie du sie nennst, läuft das doch auf „genau einmal“ hinaus.
Oder willst du A-B-C-B-C-B-C...C-D erlauben (bei 4 Knoten)? Es sind nur 3 Links, aber durch die Wiederholung kannst du beliebig viele und beliebig lange Wege erzeugen.

Überdenke die Problemstellung.

Gruß vom ¼



-----------------
Bild



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 3719
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2017-11-17


Ich vermute wie viertel ebenfalls, dass du eigentlich doch "genau ein Mal" meinst.

Suchst du eventuell die Anzahl der Bäume mit n Knoten? Davon gibt es <math>n^{n-2}</math> Stück. Überprüfe mal die 95, ob es nicht eventuell 125 sind.



  Profil  Quote  Link auf diesen Beitrag Link
chip
Neu Letzter Besuch: im letzten Monat
Dabei seit: 17.11.2017
Mitteilungen: 4
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2017-11-18


Meine Frage ist in dem Fall, wie viele Möglichkeiten es gibt, n-1 Links zwischen n Knoten zu verteilen, sodass ausgehend von einem Startknoten alle Knoten erreicht werden können.

Im Beispiel von 4 Knoten A, B, C, D:
Sei A der Startknoten.
1. A-B, A-C, A-D
2. A-B, A-C, C-D
3. A-B, A-C, B-D
4. A-B, A-D, D-C
5. A-B, A-D, B-C
6. A-C, A-D, C-B
7. A-C, A-D, D-B
8. A-B, B-C, B-D
9. A-C, C-B, C-D
10. A-D, D-B, D-C
11. A-B, B-C, C-D
12. A-B, B-D, D-C
13. A-C, C-B, B-D
14. A-C, C-D, D-B
15. A-D, D-B, B-C
16. A-D, D-C, C-B

Was nicht geht wäre z.B.

B-C, C-D, D-B
...

Wie ich das verstehe, wird nicht jeder Knoten genau einmal durchlaufen, da in der ersten Zeile A drei mal durchlaufen wird.



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 3719
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2017-11-18


2017-11-18 00:01 - chip in Beitrag No. 5 schreibt:
Wie ich das verstehe, wird nicht jeder Knoten genau einmal durchlaufen, da in der ersten Zeile A drei mal durchlaufen wird.

Ja, du hast recht. Vergiss das mal mit dem "genau ein Mal". Ich hatte anfangs vernutet, du suchst die Anzahl der Wege x1, x2, x3, ... die alle Knoten 1, 2, ..., n durchlaufen und bei 1 starten.

Und davon gäbe es natürlich unendlich viele, wenn Knoten mehrfach durchlaufen werden dürfen.

Aber aufgrund deiner Auflistung glaube ich nun, dass du tatsächlich die Anzahl der Bäume mit Knotenmenge 1, 2, ... , n suchst.

Wie gesagt: Überprüfe bitte noch mal die 95.



  Profil  Quote  Link auf diesen Beitrag Link
viertel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2003
Mitteilungen: 26070
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2017-11-18


Ja, das war anfangs schon mißverständlich.

Alle Bäume zu zählen müßte rekursiv möglich sein. Hab ich aber noch nicht genauer drüber nachgedacht.



  Profil  Quote  Link auf diesen Beitrag Link
chip
Neu Letzter Besuch: im letzten Monat
Dabei seit: 17.11.2017
Mitteilungen: 4
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2017-11-20 11:18


Hallo,

ich suche tatsächlich die Anzahl der Bäume mit Knotenmenge 1, 2, ... , n. Dieser Gedankenschritt hat mir gefehlt, vielen Dank!

Viele Grüße



  Profil  Quote  Link auf diesen Beitrag Link
chip hat die Antworten auf ihre/seine Frage gesehen.
chip hat selbst das Ok-Häkchen gesetzt.
chip wird per Mail über neue Antworten informiert.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2017 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]