Randomiser le chemin hamiltonien

Question

Comment randomiser un chemin donné trouvé par FindHamiltonianPath?

FindHamiltonianPath produit un seul des chemins hamiltoniens possibles.

Vous pouvez simplement spécifier les points de départ et d'arrivée, mais un seul chemin pour chaque paire de points est donné.

Y a-t-il une fonction qui prend la sortie de FindHamiltonianPathet la transforme au hasard, tout en la préservant d'être hamiltonienne?

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

Mettre à jour:

Par exemple, pour ce qui précède, "Dodecahedron"nous avons ces chemins hamiltoniens (tous commencent au sommet 13et se terminent au sommet 17):

Answer 1

Vous pouvez trouver tous les cycles hamiltoniens d'un graphique, qui incluent tous les chemins hamiltoniens, et sélectionner l'un des chemins au hasard.

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

Pour un graphe avec des sommets de début et de fin, nous devons supprimer les chemins qui n'incluent pas les deux sommets comme points d'extrémité d'une arête, puis supprimer l'arête. Nous pouvons dessiner les 20 graphes commençant au sommet 13 et se terminant au sommet 17 par:

{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

Puisque vous dites que vous n'avez besoin d'aucune distribution particulière, vous pouvez essayer d'utiliser l'astuce consistant à randomiser la représentation graphique.

Prendre

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

et trouvez des chemins ou des cycles g2. L'algorithme en renverra un autre simplement parce qu'il travaille avec une représentation différente du même graphe.

Dans les graphes plus grands, il peut y avoir trop de cycles hamiltoniens pour permettre une énumération par force brute, comme dans l'autre réponse de @credihne. Dans ces cas, l'astuce de randomisation peut être utile pour obtenir quelques chemins supplémentaires qui ne se chevauchent pas significativement avec l'original.

Attention cependant, la représentation particulière de certains des graphiques intégrés peut permettre au chercheur de chemin hamiltonien de renvoyer un résultat très rapidement. Une fois que nous l'avons randomisé, cela FindHamiltonianPathpeut devenir anormalement lent. C'est ce qui semble se produire avec ce graphique:

g = GraphData["GreatRhombicosidodecahedralLineGraph"]

Par conséquent, il peut être encore plus pratique d'énumérer non pas tous, mais certains cycles / chemins et de les choisir au hasard.