Hallo,
ich versuche momentan gerade, in einem (gerichteten) Graphen die Kreise zu finden.
Momentan ist mein Ansatz der, dass ich rekursiv Knoten aus dem Graph entferne und überprüfe, ob der resultierende Teilgraph ein Kreis ist. Die Überprüfung der Kreiseigenschaft nehme ich durch eine beschränkte Tiefensuche vor, die durch n = Anzahl der Knoten im Graph beschränkt ist. Wenn der Walker nach n+1 Schritten alle Knoten besucht hat und wieder beim Ursprung ankommt, dann ist ein Kreis gefunden.
Dabei gibt es zwei Probleme:
ich versuche momentan gerade, in einem (gerichteten) Graphen die Kreise zu finden.
Momentan ist mein Ansatz der, dass ich rekursiv Knoten aus dem Graph entferne und überprüfe, ob der resultierende Teilgraph ein Kreis ist. Die Überprüfung der Kreiseigenschaft nehme ich durch eine beschränkte Tiefensuche vor, die durch n = Anzahl der Knoten im Graph beschränkt ist. Wenn der Walker nach n+1 Schritten alle Knoten besucht hat und wieder beim Ursprung ankommt, dann ist ein Kreis gefunden.
Dabei gibt es zwei Probleme:
- Zum einen hat ein Graph mit n Knoten 2^n Teilgraphen (wenn man die Kanten außer Acht lässt), was zunächst sehr viel ist. Man kann es dadurch verringern, dass bei einem Teilgraph, der ein Kreis ist, die Rekursion nicht weiter betrachtet werden muss (das ist sinnvoll, wenn man nicht alle Kreise, sondern nur die größtmöglichen finden will). Das ändert aber nichts am worst-case-Verhalten.
- Zum anderen ist das Überprüfen, ob ein Graph ein Hamiltonkreis ist, bekanntermaßen ein NP-vollständiges Problem. D.h., die Frage lässt sich auch nicht in polynomieller Laufzeit lösen.