Graphentheorie: Pfad über alle Knoten

Neue Frage »

bladiblub Auf diesen Beitrag antworten »
Graphentheorie: Pfad über alle Knoten
Meine Frage:
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.
lgrizu Auf diesen Beitrag antworten »
RE: Graphentheorie: Pfad über alle Knoten
Schau mal hier:

Klick
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?
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
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
papahuhn Auf diesen Beitrag antworten »

Da nicht jeder Graph einen Hamiltonpfad besitzt, gibt es so einen Algorithmus nicht.
 
 
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.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »