matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

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
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenGraphentheorieVerbindungen in Graphen
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Deutsch • Englisch • Französisch • Latein • Spanisch • Russisch • Griechisch
Forum "Graphentheorie" - Verbindungen in Graphen
Verbindungen in Graphen < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Verbindungen in Graphen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 11:55 Do 09.03.2006
Autor: DerKleineEisbaer

Hallo,

ich stehe vor dem folgenden Problem, ich habe einen ungewichteten (bzw. alle Kanten mit 1 gewichtet), ungerichteten Graphen und suche nun alle Verbindungen von Knoten x nach Knoten y, die über eine maximale Länge von z Knoten führen.

Gibt es einen anderen Weg / Algorithmus als sozusagen rekursiv die nachfolgenden Knoten von x, dann die jeweils nachfolgenden Knoten dieser Nachfolger, usw. zu überprüfen, ob der Knoten y zu dieser Menge zählt? (Breitensuche)

Vielen Dank für Eure Ideen, Anregungen oder Hinweise, wo ich weitere Informationen dazu finden könnte, es geht mir vielmehr auch um erste Anregungen und keine Komplettlösungen oder auch einfach ein klares "es geht nicht anders" :-)

Nach etwas weiterer Recherche entspricht meine Fragestellung in etwa der Aufgabe 2 des folgenden PDFs, die nahelegt, dass es wohl doch andere Verfahren gibt, doch welche? []http://www.math.tu-bs.de/~fekete/Einf2/ueb02.pdf

Viele Grüße, Lars

Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.

        
Bezug
Verbindungen in Graphen: Antwort
Status: (Antwort) fertig Status 
Datum: 12:34 Do 09.03.2006
Autor: mathiash

Hallo und guten Mittag,

fuer das von Dir geschilderte Problem, alle Pfade der vorg. Hoechstlaenge zu berechnen, geht es
nicht besser. Vorsicht: Wenn Du alle solche Pfade generieren moechtest, so sind dies im allgemeinen
exponentiell viele (in der Groesse des Graphen), und Du kannst nicht einfach nur BSF anschmeissen, sondern musst es
so tun, dass auch wirklich alle Pfade gefunden werden (d.h. jeder Knoten hat eine4 Liste von Pointern auf Vorgaengerknoten auf
einem Pfad der Laenge hoechstens z zur Wurzel, die anfangs leer ist und im Laufe von BFS gefuellt wird).

Die Aufgaben auf dem von Dir beigefuegten Blatt beziehen sich mE hingegen auf das Problem, einen (nicht alle)
kuerzesten Wege von x nach y oder so zu berechnen, und dafuer gibt es dann in der Tat wesentlich effizientere Algorithmen
(Dijkstra-Algorithmus zum Beispiel).

Gruss,

Mathias

Bezug
        
Bezug
Verbindungen in Graphen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 14:21 Do 09.03.2006
Autor: DerKleineEisbaer

Hallo Mathias,
vielen Dank für Deine schnelle Antwort ... ich denke auch, ich werde mich dann vorerst auf BFS beschränken.

Die Algorithmen von Dijkstra, Ford, Floyd & Co habe ich in den letzten Tagen durchgearbeitet, aber wie Du schon sagst, sie finden eben nur einen kürzesten Pfad.
Ich hatte aufgrund der Aufgabenstellung mit Preprocessing und Queries vermutet, dass es vielleicht doch andere Algorithmen geben könnte, denn so großartig Preprocessing, usw. findet bei BFS eigentlich ja nicht statt, außer mit Preprocessing sind Sachen wie Matrizeninitalisierung, usw. gemeint ... zumal in Aufgabenstellung d) aber ja auch nach Möglichkeiten mit und ohne Preprocessing gefragt ist und nach der Ermittlung der Pfade mit "vorab" ermittelteten Daten.

Also wenn noch jemand andere Ideen hat, wäre ich dafür sehr zu haben :-)

Viele Grüße, Lars

Bezug
                
Bezug
Verbindungen in Graphen: Antwort
Status: (Antwort) fertig Status 
Datum: 23:10 Do 09.03.2006
Autor: kretschmer

Hallo Ihr beiden,

also spontan gesagt, wenn man nicht gerade alle Pfade aufzählen will, braucht man nicht unbedingt exponentiell viel Zeit. Der Trick dabei ist natürlich, dass man die Pfade nur indirekt notiert. Dazu kann man BFS, bzw. eine Variante von Dijkstra nehmen. Beides ist aber im Fall von Kantengewicht 1 äquivalent.

Man geht einfach folgendermaßen vor: Starte mit Knoten $x$. Sei $X$ die Menge der aktuell zu betrachtenden Kanten und damit [mm] $X=\{x\}$. [/mm] Nur wollen wir solange es ein [mm] $v\in [/mm] X$ gibt folgendes machen: Entferne $v$ aus $X$ und für jede Kante [mm] $(v,w)\in [/mm] E$ addiere $v$ zu den möglichen Nachfolgern von $w$ und füge $w$ in $X$ hinzu.

Dann hat man die Pfade im Endeffekt indirekt als Nachfolger gegeben. Gestartet in Knoten $y$ kann man sich so nach $x$ "hangeln". Allerdings bietet dies nur eine Teillösung, denn die Längenbeschränkung kann man sozusagen nicht gleichzeitig darauf werfen, dass müsste man dann in einem weiteren Schritt machen. Laufzeittechnisch sollte das per DFS kein Problem geben, da man dann amortisiert nicht mehr Zeit verbraucht als man hätte wenn man diese Einschränkung gleich miteinbindet (jedenfalls soweit wie ich das sehe).

Die eigentliche Laufzeit um die Pfade indirekt aufzubauen ist dann [mm] $O(|E|)\subset O(|V|^2)$. [/mm]

--
Gruß
Matthias

Bezug
                        
Bezug
Verbindungen in Graphen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 07:12 Fr 10.03.2006
Autor: mathiash

Hallo und guten Morgen Matthias und Eisbär,

Matthias, Du baust also via Dijkstra sowas auf wie fuer jeden Knoten eine Liste von Pointern auf Knoten, und
wenn es von u nach v einen Pointer gibt, heisst das, dass es einen Pfad der Laenge hoechstens z (oder was das war)
von u zur Quelle (hieß sie s ?) gibt, der als erste Kante die von u nach v nimmt.

Das geht natuerlich, wenn man sich mit einer solchen Repräsentation begnügt.

Ich denke, damit können wir die Frage auf grün schalten, oder ?

Viele Grüße,

Mathias

Bezug
                                
Bezug
Verbindungen in Graphen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 08:32 Mo 13.03.2006
Autor: kretschmer

Hallo mathiash und Eisbär,

um mathiashs Frage zu beantworten: Ja - so dachte ich mir das. Wenn man alle aufzählen will, ist es nicht unbedingt das geschickteste, weil man dann ja direkt DFS oder sowas machen muss, was man auch gleich auf dem ursprünglichen Graphen hätte machen können.

--
Gruss
Matthias

Bezug
        
Bezug
Verbindungen in Graphen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 12:55 Fr 10.03.2006
Autor: DerKleineEisbaer

Ich denke auch, ich werde mich damit zufrieden geben und das erstmal auf mich einwirken lassen :)

Vielen Dank Euch beiden.

Gruß, Lars

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


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