Pfade finden < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Es sei gegeben ein ungerichteter Graph mit n Knoten und m Kanten. Der Graph ist zusammenhängend, es kommen keine Zyklen und Mehrfachverbindungen zwischen den Knoten vor. Ein Knoten sei als Quelle definiert, ein Knoten als Senke. |
Hallo zusammen!
ich suche Informationen über Algorithmen, die in einem ungerichteten Graphen
a.) alle möglichen Pfade zwischen Quelle und Senke finden
b.) einen möglichen Pfad zwischen Quelle und Senke (dies kann MUSS aber nicht der kürzeste Pfad im Graphen sein)
Hat jemand eine Idee? Vielen Dank für eure Hilfe!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:20 Di 11.09.2012 | | Autor: | felixf |
Moin!
> Es sei gegeben ein ungerichteter Graph mit n Knoten und m
> Kanten. Der Graph ist zusammenhängend, es kommen keine
> Zyklen und Mehrfachverbindungen zwischen den Knoten vor.
> Ein Knoten sei als Quelle definiert, ein Knoten als Senke.
>
> ich suche Informationen über Algorithmen, die in einem
> ungerichteten Graphen
> a.) alle möglichen Pfade zwischen Quelle und Senke finden
Die Menge aller Pfade ist ein Baum. In diesem kannst du eine Tiefensuche machen und somit alle aufzaehlen.
> b.) einen möglichen Pfad zwischen Quelle und Senke (dies
> kann MUSS aber nicht der kürzeste Pfad im Graphen sein)
Das kannst du in O(n+m) Operationen machen, falls der Graph n Ecken und m Kanten hat.
Gehe einfach von jeder Ecke alle Kanten entlang; kommst du zu einer neuen Ecke, die du noch nicht hattest, merke sie dir fuer spaeter vor (von dort aus wieder alle Kanten abgrasen); andernfalls ignoriere die Ecke (da du sie schon hattest). Frueher oder spaeter taucht die Senke auf, dann hast du einen Pfad, wenn du jeweils bei jeder besuchten Ecke notiert hast woher du gekommen bist.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:26 Di 11.09.2012 | | Autor: | Teufel |
Hi!
Wobei sich in diesem Setting [mm] $\mathcal{O}(m+n)$ [/mm] zu [mm] $\mathcal{O}(m)$ [/mm] vereinfacht, weil in zusammenhängenden Graphen stets [mm] $m\ge [/mm] n-1$ gelten muss, woraus $n [mm] \in \mathcal{O}(m)$ [/mm] folgt.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:14 Di 11.09.2012 | | Autor: | felixf |
Moin,
> Wobei sich in diesem Setting [mm]\mathcal{O}(m+n)[/mm] zu
> [mm]\mathcal{O}(m)[/mm] vereinfacht, weil in zusammenhängenden
> Graphen stets [mm]m\ge n-1[/mm] gelten muss, woraus [mm]n \in \mathcal{O}(m)[/mm]
> folgt.
stimmt! Wobei das hier noch genauer geht  Es gilt naemlich nicht nur $m [mm] \ge [/mm] n - 1$, sondern auch $m [mm] \le [/mm] n - 1$, da der Graph keine Zyklen hat und ungerichtet ist. Damit hat der Graph eine sehr einfache Form und man braucht gar nicht so viel zu tun um alle Pfade zu bestimmen.
LG Felix
|
|
|
| |
|
Hallo zusammen!
Ich hätte da eine ähnliche Frage und zwar arbeite ich derzeit mit einem Algorithmus der alles kann:
1. Finde alle möglichen Wege von Quelle zu Senke
2. Finde einen möglichen Weg ...
3. Finde den kürzesten Weg ...
Der Algorithmus ist von dem Schlleimpilz Physarum polycephalum abgeschaut und das mathematische Modell wurde von Tero et. al. entwickelt. Je nachdem wie ich einen Parameter im mathematischen Modell wähle, erhalte ich meine gewünschte Ausgabe. Wähle ich [mm] \mu \in[0,1], [/mm] so erhalte ich alle möglichen Pfade zwischen Quelle und Senke. Wähle ich [mm] \mu=1 [/mm] dann erhalte ich den kürzesten Pfad im Graphen (Physarum Solver) und für [mm] \mu>1 [/mm] eben einen möglichen Pfad. (Das mathematische Modell basiert auf einem System von Differentialgleichungen)
Meine Frage ist nun, ob es bereits einen Algorithmus gibt, der dies auch kann?
So wie ich es verstanden habe, findet die Tiefensuche nur einen möglichen Weg zwischen Quelle und Senke.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:24 Fr 14.09.2012 | | Autor: | Teufel |
Hi!
Also ich weiß nicht genau, wie das [mm] \mu [/mm] in den Algorithmus genau einfließt, aber für deine Fragestellungen gibt es Algorithmen. Den zweiten Punkt hast du ja abgehakt (z.B. Tiefensuche).
Zu Punkt 3: Such mal nach dem Dijkstra-Algorithmus. Dieser finden den kürzesten Weg zwischen 2 Punkten in einem gerichteten Graphen, wenn du noch jeweils positive Kantenkosten an den Kanten hast. Ist dein Graph ungerichtet, so kannst du das so modellieren, dass eine ungerichtete Kante jeweils 2 gerichteten Kanten entspricht (einmal vom Knoten hin und zurück), die jeweils Kantenkosten 1 haben. So findet der Algorithmus am Ende den kürzesten Weg von der Quelle zur Senke und gibt sogar die Kosten aus, die aber hier dann der Kantenanzahl entsprechen. Sollte genau das sein, was du suchst.
Zu Punkt 1: Hier würde ich die Tiefensuche sozusagen einfach weiterlaufen lassen. Hat die Tiefensuche einen Weg gefunden, so speicherst du diesen, danach nimmst du aber den letzten Knoten (die Senke) wieder weg und lässt den Algorithmus weiterlaufen, als wenn er noch nichts gefunden hätte. Dann findet er bald den nächsten Weg usw.
|
|
|
| |
|
Bei dem Algorithmus von Tero ist nur wichtig zu wissen, dass man mit ihm die 3 genannten Wegeprobleme lösen kann.
Deine Antwort bedeutet aber, dass es keinen dir bekannten Algorithmus gibt, der dies ebenfalls kann, oder? Ich bräuchte für die Lösung dieser 3 Fragestellungen somit 2 Algorithmen (Tiefensuche und Dijkstra-Algorithmus).
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:08 Fr 14.09.2012 | | Autor: | Teufel |
Wenn die Laufzeit nicht ganz so wichtig ist, kann man auf den Dijkstra auch verzichten und stattdessen den kürzesten Weg so bestimmen:
Löse Problem 1 und such den kürzesten Weg raus. :) Dann brauchst du im Prinzip nur die Tiefensuche.
|
|
|
|
