Elementarer Weg im ungerichteten Graphen

Neue Frage »

DanZ Auf diesen Beitrag antworten »
Elementarer Weg im ungerichteten Graphen
Hallo,

ich habe folgendes Problem:
Gegeben ist ein ungerichteter, zusammenhängender Graph, sowie eine echte Teilmenge T der Eckenmenge V.(Außerdem existiert mindestens ein elementarer Kreis, mit allen Ecken V/T)

Gesucht ist ein elementarer Weg, der alle Ecken Element T enthält, wobei nicht gesichert ist, dass dieser existieren muss.

Ich suche nun einen möglichst effizienten Algorithmus, der mir, falls vorhanden, einen solchen Weg ermitteln kann.

Hat vielleicht irgendjemand eine Idee

Vielen Dank im Voraus

MfG
DanZ
Tobias Auf diesen Beitrag antworten »

Man kann das Problem "Hamiltonpfad" auf dein Problem reduzieren. Wie du vielleicht weißt, ist Hamitonpfad NP-vollständig. Also gibt es (bisher) keinen effizienten Algorithmus.
Neue Frage »
Antworten »



Verwandte Themen

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