www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Englisch
  Status Grammatik
  Status Lektüre
  Status Korrekturlesen
  Status Übersetzung
  Status Sonstiges (Englisch)

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 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" - Pfade finden
Pfade finden < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Pfade finden: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 11:06 Di 11.09.2012
Autor: KomplexKompliziert

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!

        
Bezug
Pfade finden: Antwort
Status: (Antwort) fertig Status 
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


Bezug
                
Bezug
Pfade finden: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
                        
Bezug
Pfade finden: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
                
Bezug
Pfade finden: Algorithmus der alles kann
Status: (Frage) beantwortet Status 
Datum: 09:54 Fr 14.09.2012
Autor: Selbstbedienung

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.


Bezug
                        
Bezug
Pfade finden: Antwort
Status: (Antwort) fertig Status 
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.


Bezug
                                
Bezug
Pfade finden: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 16:58 Fr 14.09.2012
Autor: Selbstbedienung

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).

Bezug
                                        
Bezug
Pfade finden: Antwort
Status: (Antwort) fertig Status 
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.

Bezug
                                                
Bezug
Pfade finden: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 13:09 So 16.09.2012
Autor: Selbstbedienung

Danke!


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


^ Seitenanfang ^
www.englischraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]