Anzahl möglicher Wege < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:08 Mo 27.08.2012 | | Autor: | ammy |
Hallo :)
Ich hab für meine Seminararbeit über kürzeste Wege mal eine Frage.
Ich habe einen "gitternetförmigen" Graphen mit n*n-Knoten
+-+-+-+...
| | | |
+-+-+-+...
| | | |
+-+-+-+...
| | | |
+-+-+-+...
: : : :
Die Anzahl der Knoten ist begrenzt, also nicht unendlich. Alle Kantenkosten sind positiv.
Wie kann man in so einem Graphen die Anzahl der verschiedenen Wege (nicht nur die Kürzesten) vom links oberen zum rechts unteren Knoten berechnen? Die einzige Bedingung die gestellt ist, dass jeder Knoten nur 1 mal befahren werden darf.
Ich konnte durch Google leider keine Lösung finden und meine Schulmathematik reicht dazu leider noch nicht aus :( Ich hoffe da gibt es überhaupt eine Möglichkeit das zu berechnen...
Ich hoffe ihr könnt mir da weiterhelfen :)
Danke schon einmal im voraus
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
> Hallo :)
>
> Ich hab für meine Seminararbeit über kürzeste Wege mal
> eine Frage.
>
> Ich habe einen "gitternetförmigen" Graphen mit n*n-Knoten
>
> +-+-+-+...
> | | | |
> +-+-+-+...
> | | | |
> +-+-+-+...
> | | | |
> +-+-+-+...
> : : : :
>
> Die Anzahl der Knoten ist begrenzt, also nicht unendlich.
> Alle Kantenkosten sind positiv.
>
> Wie kann man in so einem Graphen die Anzahl der
> verschiedenen Wege (nicht nur die Kürzesten) vom links
> oberen zum rechts unteren Knoten berechnen? Die einzige
> Bedingung die gestellt ist, dass jeder Knoten nur 1 mal
> befahren werden darf.
Die Menge aller Weg lassen sich durch "Sequenzen" von Buchstaben beschreiben.
UURDRUU ....
U - Up ( im deutschen sind die Anfangsbuchstaben doof: Runter,Rechts )
D - Down
L - Links
R - Rechts
Im allgemeinen (so kenne ich es nur) gab es noch die Beschränkungen, dass man nur die Richtungen Up und Rechts benutzen darf.
+-+-+-B
| | | |
+-+-+-+
| | | |
+-+-+-+
| | | |
A-+-+-+
A ist der Start und B ist das Ende. Es ist klar, dass bei einer Gitterbreite n und Gitterhöhe m man mindestens n-Mal nach rechts geht und m-Mal nach oben geht:
Analog lässt sich die Frage stellen: Wie viele Buchstabensequenzen "UUUURRURR..." lassen sich aus n Buchstaben R und m Buchstaben U bilden.
Das geht per Binomialkoeffizient und mit Schulmathematik.
Falls es dich weiter interessiert, dann wäre der Begriff der "catalanschen Zahlen" noch etwas.
>
> Ich konnte durch Google leider keine Lösung finden und
> meine Schulmathematik reicht dazu leider noch nicht aus :(
> Ich hoffe da gibt es überhaupt eine Möglichkeit das zu
> berechnen...
Jetzt wird es richtig komplizierter, falls du noch die anderen Richtungen D und L zulässt.
Die Problemstellung nennt sich "Self-Avoiding Walks" und lässt sich nicht als Formel so leicht lösen. Nicht einmal in quadratischen Gittern.
Siehe hierzu:
http://mathworld.wolfram.com/Self-AvoidingWalk.html
ein weiterer Link mit den möglichen Ergebnissen:
http://oeis.org/A007764
Falls es noch jemanden anderen interessiert (doch schon recht kompliziert):
http://arxiv.org/pdf/cond-mat/0506341v2.pdf
Allgemein lässt sich das also nur approximativ angeben. Exakte Werte bekommt man durch Computerhilfe.
>
> Ich hoffe ihr könnt mir da weiterhelfen :)
>
Hoffe das mit dem Helfen trifft zu.
liebe Grüße
wieschoo
|
|
|
|
