Graphentheorie: Pfade durch eine Trellis

Neue Frage »

DaPhreak Auf diesen Beitrag antworten »
Graphentheorie: Pfade durch eine Trellis
Hallo Matheboard.
Bisher konnte mir keiner damit helfen, vielleicht hat ja einer von euch ne Idee.

Also.
Ich suche eine Möglichkeit, in einer Trellis [gibs da n deutsches Wort für?] die Anzahl der Pfade von einem Zustand zu einem anderen mit einer bestimmten Pfadlänge zu berechnen.

Meine Trellis ist gegeben durch die folgenden Regeln:
- Zu jedem Zeitpunkt gibt es N Zustände 1..N.
- Ich starte in Zustand k.
- Zu jedem Zeitpunkt kann ich von Zustand n in Zustand n-1 oder n+1.
- Der kleinstmögliche Zustand ist 1, den kann ich also nur nach unten verlassen (in Richtung 2).
- Der größtmögliche Zustand ist N. Zustand N kann nicht wieder verlassen werden. N hat also eine hinführende Kante von N-1 und keine wegführenden Kanten.
- Die Trellis kann unendlich lang sein.

Ich suche nun alle Wege um vom Zustand k in den Zustand N zu kommen.

Offensichtlich ist, dass der kürzeste Weg die Länge N-k hat, indem ich N-k mal nach "unten" gehe. Es gibt also genau einen Weg der Länge N-k. Auch offensichtlich ist, dass nur Weglängen der Form N-k+2n möglich sind. Für einen Weg der Länge N-k+2n gehe ich n mal nach oben und N-k+n mal nach unten (in nahezu beliebiger Reihenfolge).
Die Frage ist nun, wieviele Wege der Länge N-k+2n vom Zustand k in den Zustand N gibt es? Das Problem wäre trivial, wenn die Anzahl der Zustände unendlich ist wie beim random walk, dann wäre es ein schlichter Binomialkoeffizient. Aber da ich ja Zustand 1 nur in eine Richtung verlassen kann geht es eben nicht so einfach.

Mir fällt dazu spontan nur Masons gain formula ein, mit der bekomm ich's aber nicht hin, weil der Graph ja nicht wirklich fest ist, sondern noch von N abhängt und außerdem verdammt viele Schleifen hat.

Wenn irgendjemand dazu 'ne Idee hat würde ich mich wirklich freuen.

Falls meine Erklärungen nicht verständlich genug waren bitte nachfragen.
DaPhreak Auf diesen Beitrag antworten »

Hmm, keiner? Hilfe
Leopold Auf diesen Beitrag antworten »

Tut mir leid, ich weiß nicht einmal was eine Trellis ist.
DaPhreak Auf diesen Beitrag antworten »

Naja wie ich versuchte zu erklären: es gibt zu jedem diskreten Zeitpunkt N Zustände und wir befinden uns in genau einem der N. Die möglichen Zustandswechsel sind beschrieben durch obige Regeln. Wenn wir nun in Zustand k anfangen, können wir im nächsten Schritt in k+1 oder k-1 sein, einen Schritt danach in k+2, k oder k-2 usw.
Das lässt sich halt in ner baumförmigen Struktur zeichnen, z.B. Zeit horizontal, Zustände vertikal.
Ich kenns halt nur unter dem Namen Trellis...
Neue Frage »
Antworten »



Verwandte Themen

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