Elementarer Weg im ungerichteten Graphen |
01.05.2008, 20:11 | DanZ | Auf diesen Beitrag antworten » |
Elementarer Weg im ungerichteten Graphen 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 |
||
05.05.2008, 19:31 | 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. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|