Anzahl der Wege für Pfad mit 3 Kanten und 4 Knoten
Neue Frage »

29.01.2020, 18:55 noahkamara Auf diesen Beitrag antworten »
Anzahl der Wege für Pfad mit 3 Kanten und 4 Knoten
Meine Frage:
Hallo,
wir sollen herausfinden, wie viele verschiedene Wege der Länge der k es im Pfad P3 (mit 4 Knoten) gibt. Ich weiß leider gar nicht wo ich hier anfangen soll.


Meine Ideen:
Man hat mir schon den Tipp gegeben die Fibonacci-Zahlen zu verwenden und das ganze mit Induktion zu beweisen.
29.01.2020, 19:34 Elvis Auf diesen Beitrag antworten »

Könntest du eventuell genauer formulieren, was die Aufgabe ist ? Welche Bedeutung haben 4 Knoten, wenn man für die Wege nur 3 Kanten benutzen darf ? Soll man da geschlossene und offene Wege unterscheiden ? Wie groß darf k sein (0,1,2,3,...,4711 ???)
29.01.2020, 21:06 noahkamara2 Auf diesen Beitrag antworten »

Oh, sorry,
Es geht um einen Pfad mit 4 Knoten und 3 Kanten. Von diesem soll man alle Wege mit der länge k bestimmen. Ist das verständlicher? k ist nicht genauer definiert. Ich denka mal man soll eine Weg finden mi9t dem man k einsetzen kann
29.01.2020, 21:51 Elvis Auf diesen Beitrag antworten »

Ich verstehe nur Bahnhof. Kannst du bitte eine Skizze machen, damit ich eine Vorstellung bekomme, worum es geht?
Was ist ein Pfad? Was ist ein Weg?
29.01.2020, 22:24 noahkamara2 Auf diesen Beitrag antworten »

Ein Pfad ist ein Weg, bei dem kein Knoten doppelt vorkommt
z.B.: (1,2,3,4)
Wege mit länge zwei in diesem Pfad wären zum Beispiel:
(1,2,3)
(2,3,4)
(2,3,2)
29.01.2020, 23:11 Finn_ Auf diesen Beitrag antworten »

Ah ok, man so einen Graph:

code: 
1:
2:

    * ---- * ---- * ---- *
    1      2      3      4

und will da von Knoten zu Nachbarknoten laufen. Die Länge des Weges ist die Anzahl der gelaufenen Kanten, bzw. der zurückgelegte Weg, wobei jede Kante die Länge eins hat.
 Anzeige 
 
30.01.2020, 10:21 Elvis Auf diesen Beitrag antworten »

Ordnet man die Wege der Länge k lexikografisch, so fällt auf, dass ein Weg, der mit 1 oder 4 endet, zu einem Weg der Länge k+1 verlängert werden kann, und ein Weg, der mit 2 oder 3 endet kann zu 2 Wegen der Länge k+1 verlängert werden. Die Anzahl der Wege ergibt tatsächlich eine Fibonnacifolge 4,6,10,16,26,... Das muss "nur noch" bewiesen werden. Insbesondere wird man untersuchen müssen, wie viele Wege bei 1 und 4 und wie viele Wege bei 2 und 3 enden.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »


MatheBoard » Hochschulmathematik » Sonstiges » Anzahl der Wege für Pfad mit 3 Kanten und 4 Knoten