Randomizando caminho hamiltoniano

Question

Como randomizar determinado caminho encontrado por FindHamiltonianPath?

FindHamiltonianPath produz apenas um dos caminhos hamiltonianos possíveis.

Você pode simplesmente especificar os pontos inicial e final, mas ainda apenas um caminho para cada par de pontos é fornecido.

Existe alguma função que pega a saída de FindHamiltonianPathe a transforma aleatoriamente, mas preservando-a como hamiltoniana?

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

Atualizar:

Por exemplo, para o acima "Dodecahedron", temos estes caminhos hamiltonianos (todos começam no vértice 13e terminam no vértice 17):

Answer 1

Você pode encontrar todos os ciclos hamiltonianos de um gráfico, que incluem todos os caminhos hamiltonianos, e selecionar um dos caminhos aleatoriamente.

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

Para um gráfico com vértices iniciais e finais, devemos remover os caminhos que não incluem os dois vértices como pontos finais de uma aresta e, em seguida, remover a aresta. Podemos desenhar os 20 gráficos começando no vértice 13 e terminando no vértice 17 por:

{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

Como você diz que não precisa de nenhuma distribuição específica, pode tentar usar o truque de randomizar a representação do gráfico.

Levar

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

e encontrar caminhos ou ciclos g2. O algoritmo retornará um diferente simplesmente porque está trabalhando com uma representação diferente do mesmo gráfico.

Em gráficos maiores, pode haver muitos ciclos hamiltonianos para permitir a enumeração de força bruta, como na outra resposta de @credihne. Nesses casos, o truque de randomização pode ser útil para obter mais alguns caminhos que não se sobreponham significativamente ao original.

Porém, tenha cuidado, pois a representação particular de alguns dos gráficos integrados pode permitir que o localizador de caminho hamiltoniano retorne um resultado muito rapidamente. Depois de randomizá-lo, ele FindHamiltonianPathpode se tornar excessivamente lento. Isso é o que parece acontecer com este gráfico:

g = GraphData["GreatRhombicosidodecahedralLineGraph"]

Portanto, pode ser ainda mais prático enumerar não todos, mas alguns ciclos / caminhos e escolhê-los aleatoriamente.