Graphentheorie: Pfad über alle Knoten |
16.11.2012, 17:58 | bladiblub | Auf diesen Beitrag antworten » |
Graphentheorie: Pfad über alle Knoten Hallo, ich suche einen Algorithmus der mir zu einem (zusammenhängendem, ungerichteten) Graph einen Pfad ermittelt der alle Knoten enthält. Wichtig für den Pfad ist eigentlich nur, dass ein Knoten maximal einmal besucht werden darf und der Pfad möglichst wenige Teilungen hat, am besten keine (aber das ist nicht bei jedem Graph möglich). Existiert ein solcher Algorithmus? Existiert ein solches Problem in der Graphentheorie überhaupt? Wäre super wenn mir jemand Tipps geben könnte. MFG Meine Ideen: Meine bisherigen Ideen waren das Problem des Handlungsreisenden, aber das funktioniert auch nur mit gewichten Graphen. Die DFS und BFS durchlaufen zwar alle Knoten, haben aber meist zuviele Teilungen im Pfad. |
||
16.11.2012, 18:07 | lgrizu | Auf diesen Beitrag antworten » |
RE: Graphentheorie: Pfad über alle Knoten Schau mal hier: Klick |
||
16.11.2012, 20:28 | bladiblub | Auf diesen Beitrag antworten » |
Passt meiner Meinung nach nicht auf mein Problem, da ich nicht alle Pfade, sondern alle Knoten durchlaufen möchte. Oder kannst du mir näher erklären wie ich damit nun auf eine Lösung für mein Problem komme? |
||
16.11.2012, 22:30 | Huy | Auf diesen Beitrag antworten » |
Solche Pfade nennt man auch Hamilton-Pfade. Kenne mich mit Graphentheorie leider nur extrem oberflächlich aus, wenn du mehr wissen willst, bist du mit Eigeninitiative also besser aufgehoben. Ich hoffe, das Stichwort hilft dir dennoch. MfG |
||
17.11.2012, 14:01 | bladiblub | Auf diesen Beitrag antworten » |
vielen Dank Huy, das geht schon in die richtige Richtung. Leider ist es nicht genau das Problemen das ich suche. Wenn noch jemand einen Algorithmus kennt der einem Pfad mit allen Knoten für jeden Graph (mit möglichst wenig Teilungen) würde ich mich sehr über eine Antwort freuen. MFG |
||
17.11.2012, 17:35 | papahuhn | Auf diesen Beitrag antworten » |
Da nicht jeder Graph einen Hamiltonpfad besitzt, gibt es so einen Algorithmus nicht. |
||
Anzeige | ||
|
||
05.02.2014, 15:31 | Christopher x 3,141 | Auf diesen Beitrag antworten » |
Auch wenn das Thema schon älter ist: Ich war auf der Suche nach etwas sehr ähnlichem, daher für diejenigen, die das selbe suchen, hier was ich herausgefunden habe: Da der Fragesteller von "möglichst wenigen Teilungen" redet, sucht er nicht zwingend einen Weg ("Pfad"). Ein Weg hat nie Teilungen und daher existiert nicht immer einer der alle Knoten enthält. (Da ein Weg auch keine Wiederholungen zulässt - im Gegensatz zu einem Kantenzug). Was dagegen gesucht wird ist ein sog. (minimaler) Spannbaum. Dies ist ein Teilgraph (Baum), der Verzweigungen ("Teilungen") haben kann und der jeden Knoten im Graphen enthält/aufspannt. Wenn der Graph zusammenhängend ist, dann gibt es auch immer einen Spannbaum. Algorithmen dazu wären: Minimaler Spannbaum: - Algorithmus von Kruskal - Algorithmus von Prim Einfache Algorithmen (nicht minimal): Breitensuche / Tiefensuche Auch wenn es dem ursprünglichen Fragesteller wohl nicht mehr interessieren dürfte hoffe ich das hilft irgendjemandem. |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |