Ich habe relativ kleine (40-80 Knoten) kubische (3-regelmäßige) planare Graphen, und ich muss ihre Hamiltonizität entscheiden. Ich bin mir der Tatsache, dass diese Aufgabe NP-vollständig ist, aber ich hoffe für asymptotisch exponentielle Zeitalgorithmen, die dennoch sehr schnell für die Diagrammgröße, die ich interessiert binFindet Hamilton-Zyklen in kubischen planaren Graphen
40 Knoten machbar scheint. Du wählst 40 von 60 Kanten aus.
Lassen Sie uns eine Tiefensuche durchführen.
Wählen Sie zunächst einen Eckpunkt V aus. Sie müssen genau eine seiner 3 einfallenden Kanten ausschließen. Probieren Sie diese 3 Möglichkeiten einzeln aus. Wenn Sie eine auszuschließende Kante auswählen, erzwingen Sie die Einbeziehung von 4 Kanten. Danach werden wir die Scheitelpunkte der ausgeschlossenen Kante als "used" bezeichnen.
Wenn Sie diesen Vorgang 10 Mal wiederholen könnten, hätten Sie alle 40 Kanten ausgewählt und nur 3^10 (59049) Möglichkeiten gesucht. Natürlich werden Ihnen die "isolierten" Scheitelpunkte ausgehen, nachdem genügend Kanten ermittelt wurden.
Aber wir haben jetzt eine Idee für einen Algorithmus. Probieren Sie bei jedem Schritt einen Eckpunkt mit den wenigsten "verwendeten" Nachbarn aus. Tatsächlich ist es am besten, einen Vertex mit 2 verwendeten Nachbarn auszuwählen, da die verwendete Kante erzwungen wird. Ich bin mir nicht sicher, ob das Auswählen eines Scheitelpunktes mit 1 oder 0 benutzten Nachbarn der nächstbeste ist. Probieren Sie beides aus! (Und 3 verwendete Nachbarn zeigen eine fehlgeschlagene Suche an)
Wenn die Kanten abgeschnitten sind, prüfen Sie, ob sie einen einzelnen Zyklus bilden.
Haben Sie ein paar Beispielgrafiken? Ich könnte eine einfache Implementierung versuchen.
von http://mathworld.wolfram.com/HamiltonianCycle.html. „Rubin (1974) beschreibt eine effiziente Suchprozedur, die einige oder alle Hamilton-Pfade und -Schaltkreise in einem Graphen finden kann, wobei Abzüge verwendet werden, die Rückverfolgung und Ratenbildung stark reduzieren. "
Das Papier ist zu verkaufen hier: http://portal.acm.org/citation.cfm?id=321850.321854