Graph - Anzahl möglicher Pfade

29.07.2004, 16:48

Beteigeuze

Graph - Anzahl möglicher Pfade

Hallo,

eigentlich eine ganz simple Sache, aber ich finde da keine Lösung dafür: Ich will / muss herausfinden, wie viele mögliche Pfade in einem Graphen sind. Eine Möglichkeit wäre, den Graphen mit einer Tiefensuche zu traversieren, dann gibt mir die Anzahl der Blätter im erhaltenen Baum die Zahl der Pfade. Das muss doch aber einfacher gehen, oder?

Das gleiche wäre auch noch interessant für alle möglichen Wege, weil es in meinem Fall auch sein kann, zu einem Knoten zurückzukehren und dort dann anders 'abzubiegen'. Nur die Kanten dürfen nur einmal 'befahren' werden.
Der Graph ist übrigens ungerichtet.

Hat jemand eine Idee, wie man das berechnen kann?

Christina

Hilfe

29.07.2004, 20:41

Oudeis

Auf diesen Beitrag antworten »

RE: Graph - Anzahl möglicher Pfade
Hallo,

Zitat:

Original von Beteigeuze
Das gleiche wäre auch noch interessant für alle möglichen Wege, weil es in meinem Fall auch sein kann, zu einem Knoten zurückzukehren und dort dann anders 'abzubiegen'. Nur die Kanten dürfen nur einmal 'befahren' werden.

Mir scheint, zumindest so auf den ersten Blick, daß es ausreicht, den Fall zu betrachten, daß Knoten nicht mehrfach besucht werden dürfen, weil sich Dein Problem durch Konstruktion eines passenden anderen Graphen leicht auf dieses Problem zurückführen lässt.
Die Anzahl der Wege durch Deinen Graphen, in denen kein Knoten mehrfach besucht wird, bekommst Du dann imho, wenn Du Dir genau genug die Folge $\begin{eqnarray*} A_1 := f(A), A_{i+1} = f(AA_i) \end{eqnarray*}$ anschaust, wobei f die lineare Abbildung ist, für die $\begin{eqnarray*} f(E_{ij}) := (1-\delta_{ij}) E_{ij} \end{eqnarray*}$ ist und $\begin{eqnarray*} A \end{eqnarray*}$ die Adjazenzmatrix des Graphen.

Grüße,
Oudeis

30.07.2004, 10:49

Beteigeuze

Auf diesen Beitrag antworten »

RE: Graph - Anzahl möglicher Pfade
Hallo,

Zitat:

Original von Oudeis
Die Anzahl der Wege durch Deinen Graphen, in denen kein Knoten mehrfach besucht wird, bekommst Du dann imho, wenn Du Dir genau genug die Folge $\begin{eqnarray*} A_1 := f(A), A_{i+1} = f(AA_i) \end{eqnarray*}$ anschaust, wobei f die lineare Abbildung ist, für die $\begin{eqnarray*} f(E_{ij}) := (1-\delta_{ij}) E_{ij} \end{eqnarray*}$ ist und $\begin{eqnarray*} A \end{eqnarray*}$ die Adjazenzmatrix des Graphen.

Danke für die Hilfe, aber so ganz verstehe ich das jetzt leider nicht. Ich habe mir die Folge mal für einen Beispielgraphen ausgerechnet, aber was kann ich daran erkennen? Wie weit muss ich die Folge fortsetzen?

Grüße,
Christina

30.07.2004, 11:49

Oudeis

Auf diesen Beitrag antworten »

RE: Graph - Anzahl möglicher Pfade

Zitat:

Original von Beteigeuze

Danke für die Hilfe, aber so ganz verstehe ich das jetzt leider nicht. Ich habe mir die Folge mal für einen Beispielgraphen ausgerechnet, aber was kann ich daran erkennen?

Mein Fehler, das kommt davon, wenn man Sachen nur andenkt und gleich losplappert, weil man glaubt, alles wäre ganz klar smile

.
Mir würde zwar spontan eine Reparaturmöglichkeit einfallen (die nicht elegant ist, aber für das gegebene Problem immer noch einen Algorithmus mit guter Laufzeit liefern sollte, wenn ich mich nicht nochmal täusche), aber das gucke ich mir lieber heute abend mit Papier und Bleistift nochmal an, bevor ich weiterplappere smile

.

Grüße,
Oudeis

31.07.2004, 11:35

MatheBlaster

Auf diesen Beitrag antworten »

Hi,

eine kurze blöde Zwischenfrage: was genau ist ein Pfad? Im Zusammenhang mit Graphen kenne ich Kantenfolgen, Kantenzüge und Wege, aber mit Pfaden weiß ich spontan nichts genaues anzufangen. Ist ja auch schon fast einen Monat her, dass wir das Thema hatten... smile

Neue Frage »

Antworten »

Graph - Anzahl möglicher Pfade

Verwandte Themen