www.vorhilfe.de
- Förderverein -
Der Förderverein.

Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Impressum
Forenbaum
^ Forenbaum
Status VH e.V.
  Status Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Suchen
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Graphentheorie" - Anzahl möglicher Wege
Anzahl möglicher Wege < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Anzahl möglicher Wege: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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.

        
Bezug
Anzahl möglicher Wege: Antwort
Status: (Antwort) fertig Status 
Datum: 19:48 Mo 27.08.2012
Autor: wieschoo


> 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



Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
ev.vorhilfe.de
[ Startseite | Mitglieder | Impressum ]