Randomisierung des Hamilton-Pfades

Question

Wie kann man einen bestimmten Pfad, der von gefunden wurde, randomisieren FindHamiltonianPath?

FindHamiltonianPath gibt nur einen der möglichen Hamilton-Pfade aus.

Sie können lediglich Start- und Endpunkte angeben, es wird jedoch immer noch nur ein Pfad für jedes Punktepaar angegeben.

Gibt es eine Funktion, die die Ausgabe von nimmt FindHamiltonianPathund sie zufällig transformiert, aber sie als Hamilton-Operator beibehält?

HighlightGraph[#, 
   PathGraph[FindHamiltonianPath[#]]] & /@ {PolyhedronData[
   "Dodecahedron", "Skeleton"], 
  PolyhedronData[PolyhedronData["Chiral"][[1]], "Skeleton"], 
  PolyhedronData[PolyhedronData["Chiral"][[8]], "Skeleton"]}

Aktualisieren:

Zum Beispiel "Dodecahedron"haben wir für das Obige diese Hamilton-Pfade (alle beginnen am Scheitelpunkt 13und enden am Scheitelpunkt 17):

Answer 1

Sie können alle Hamilton-Zyklen eines Diagramms finden, die alle Hamilton-Pfade enthalten, und einen der Pfade nach dem Zufallsprinzip auswählen.

g = PolyhedronData["Dodecahedron", "Skeleton"];
hc = FindHamiltonianCycle[g, All];
HighlightGraph[g, RandomChoice[hc]](*draw a random Hamiltonian path*)

Für ein Diagramm mit Start- und Endscheitelpunkten müssen wir die Pfade entfernen, die die beiden Scheitelpunkte nicht als Endpunkte einer Kante enthalten, und dann die Kante entfernen. Wir können die 20 Graphen zeichnen, die am Scheitelpunkt 13 beginnen und am Scheitelpunkt 17 enden, indem wir:

{s, t} = {13, 17};
hps2t = Select[hc, MemberQ[(s | t) \[UndirectedEdge] (s | t)]];
GraphicsGrid[
 Partition[
  Table[HighlightGraph[g, 
    DeleteCases[p, (s | t) \[UndirectedEdge] (s | t)], 
    GraphHighlightStyle -> "Thick"], {p, hps2t}], 5]]

Answer 2

Da Sie sagen, dass Sie keine bestimmte Verteilung benötigen, können Sie versuchen, den Trick der Randomisierung der Diagrammdarstellung zu verwenden.

Nehmen

g2 = Graph[RandomSample@VertexList[g], RandomSample@EdgeList[g]]

und finden Sie Pfade oder Zyklen in g2. Der Algorithmus gibt einen anderen zurück, einfach weil er mit einer anderen Darstellung desselben Graphen arbeitet.

In größeren Diagrammen gibt es möglicherweise zu viele Hamilton-Zyklen, um eine Brute-Force-Aufzählung zu ermöglichen, wie in der anderen Antwort von @credihne. In diesen Fällen kann der Randomisierungstrick hilfreich sein, um einige weitere Pfade zu erhalten, die sich nicht wesentlich mit dem Original überschneiden.

Beachten Sie jedoch, dass der Hamilton-Pfadfinder aufgrund der speziellen Darstellung einiger integrierter Diagramme möglicherweise sehr schnell ein Ergebnis zurückgeben kann. Sobald wir es randomisieren, FindHamiltonianPathkann es ungewöhnlich langsam werden. Dies scheint mit dieser Grafik zu geschehen:

g = GraphData["GreatRhombicosidodecahedralLineGraph"]

Daher ist es möglicherweise noch praktischer, nicht alle, sondern einige Zyklen / Pfade aufzulisten und zufällig auszuwählen.