Verschiedene Wege in einem Graph der Länge K

05.08.2015, 12:02	rainerZufall0815	Auf diesen Beitrag antworten »
Verschiedene Wege in einem Graph der Länge K Meine Frage: Hi, habe hier die Aufgabe: Wie viele verschiedene Wege der Länge k gibt es zwischen zwei beliebige Ecken des vollständigen Graphen K? Meine Ideen: Ich weis die Lösung ist $\begin{eqnarray} \begin{pmatrix} n-2 \\ k-1 \end{pmatrix} \left(k-1\right)! \end{eqnarray}$ Weiterhin weis ich, dass $\begin{eqnarray} \begin{pmatrix} n \\ 2 \end{pmatrix} \end{eqnarray}$ ja die maximale Anzahl an Kanten ist, da ich den Weg zwischen 2 Knoten wissen will, fallen diesen beide ja weg, deshalb $\begin{eqnarray} n-2 \end{eqnarray}$ . Aber wie kommt man auf das $\begin{eqnarray} k-1 \end{eqnarray}$ in $\begin{eqnarray} \begin{pmatrix} n-2 \\ k-1 \end{pmatrix} \end{eqnarray}$ und wie auf das $\begin{eqnarray} \left(k-1\right)! \end{eqnarray*}$ ? Ich tu mich allgemein etwas schwer mit solchen Aufgaben (wieviel Hamiltonkreise gibt es in einem Graphen....), gibt es da allgemeine Ansätze oder Tipps wie ich da ran gehen soll? Danke und viele Grüße
05.08.2015, 12:10	RavenOnJ	Auf diesen Beitrag antworten »
RE: verschiedene Wege in einem Graph der Länge K Kann es sein, dass du dabei eine wichtige Information unterschlägst? Dass nämlich jeder Knoten höchstens einmal besucht werden darf.
05.08.2015, 12:13	HAL 9000	Auf diesen Beitrag antworten »
RE: verschiedene Wege in einem Graph der Länge K Sieht ganz danach aus.
05.08.2015, 12:14	rainerZufall0815	Auf diesen Beitrag antworten »
Es stand mal nicht in der Aufgabe, aber ich denke es ist so gemeint
05.08.2015, 12:24	RavenOnJ	Auf diesen Beitrag antworten »
Ein Graph mit 4 Knoten und 3-Wegen wäre ein einfaches Gegenbeispiel, wenn du diese Annahme weglässt. Dann gäbe es nämlich 5 mögliche Wege statt der 2 entsprechend der Formel.
05.08.2015, 12:28	RavenOnJ	Auf diesen Beitrag antworten »
Zu deinem Problem: Da der Graph vollständig ist, kannst du das Problem einfach in ein anderes transformieren: Auf wieviele Arten kann man k-1 aus n-2 Knoten auswählen, wobei die Reihenfolge wichtig ist?
Anzeige

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »