Question

Wie viele Wege der Länge 4 gibt es im folgenden Graphen von der Ecke
3 zur Ecke 4?

Problem/

Ich freue mich auf eure Hilfe.

Comments

Ich freue mich auf deinen Versuch, die äußerst überschaubare Menge von möglichen Wegen selbst abzuzählen.

Zu klären wäre vielleicht noch, ob man umkehren darf.

Ist 3-1-3-5-4 ein gültiger Weg?

Answer 1

Ich komme auf 26 und das sowohl rechnerisch als auch durch aufzählen. Eines davon solltest du auch können.

1214, 1314, 1354, 1414, 1424, 1434, 1454, 1514, 1534, 5124, 5134, 5154, 5314, 5354, 5414, 5424, 5434, 5454, 4124, 4134, 4154, 4214, 4314, 4354, 4514, 4534

Sollte ein Knoten nicht nochmals benutzt werden dürfen, wovon ich nicht ausgehe, dann wären die entsprechenden Pfade zu streichen. Das sollte dann aber auch nicht schwer sein.

Comments

... und das sowohl rechnerisch als auch durch aufzählen.

wie geht das 'rechnerisch'?

---

Zunächst überlegt man sich wie viele Möglichkeiten man hat von jedem Feld in einem Schritt zu Feld 4 zu gelangen.

Rekursiv darauf aufbauend überlegt man sich wie viele Möglichkeiten man hat in 2 Schritten zum Feld 4 zu kommen.

Rekursiv darauf aufbauend überlegt man sich wie viele Möglichkeiten man hat in 3 Schritten zum Feld 4 zu kommen.

...

In Excel sieht das ganze z.B. dann so aus

Das kann man jetzt natürlich auch mit Hilfe der Matrizenrechnung modellieren.

Wie viel Möglichkeiten hat man von in 4 Schritten von Feld 3 nach Feld 4 zu kommen:

[0, 0, 1, 0, 0]·[0, 1, 1, 1, 1; 1, 0, 0, 1, 0; 1, 0, 0, 1, 1; 1, 1, 1, 0, 1; 1, 0, 1, 1, 0]^4·[0; 0; 0; 1; 0] = 26

---

Danke - wieder was gelernt ;-)

---

Gerade bei mehrstufigen Sachen kann man mal an Markovketten und die Matrizenrechnung denken. Auch wenn die Aufgabenstellung bei Markovketten ein klein wenig anders liegen. Da würde es dann z.b. Lauten mit welcher Wahrscheinlichkeit ist man in 4 Schritten im Zustand 4. Da müssten dann allerdings auch noch Wahrscheinlichkeiten für die Pfade gegeben sein.