Рандомизирующий гамильтонов путь

Question

Как рандомизировать заданный путь, найденный FindHamiltonianPath?

FindHamiltonianPath выводит только один из возможных гамильтоновых путей.

Вы можете просто указать начальную и конечную точки, но при этом для каждой пары точек будет указан только один путь.

Есть ли какая-нибудь функция, которая принимает выходные данные FindHamiltonianPathи преобразует их случайным образом, но сохраняет их гамильтоновость?

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

Обновлять:

Например, для приведенного выше "Dodecahedron"у нас есть эти гамильтоновы пути (все начинаются в вершине 13и заканчиваются в вершине 17):

Answer 1

Вы можете найти все гамильтоновы циклы графа, которые включают все гамильтоновы пути, и выбрать один из путей наугад.

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

Для графа с начальной и конечной вершинами мы должны удалить пути, которые не включают две вершины в качестве конечных точек ребра, а затем удалить ребро. Мы можем нарисовать 20 графов, начиная с вершины 13 и заканчивая вершиной 17:

{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

Поскольку вы говорите, что вам не нужно какое-то конкретное распределение, вы можете попробовать использовать трюк рандомизации представления графа.

Брать

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

и найти пути или циклы g2. Алгоритм вернет другой, просто потому, что он работает с другим представлением того же графа.

В больших графах может быть слишком много гамильтоновых циклов, чтобы разрешить перебор грубой силы, как в другом ответе @credihne. В этих случаях трюк рандомизации может быть полезен, чтобы получить еще несколько путей, которые существенно не пересекаются с оригиналом.

Однако помните, что конкретное представление некоторых встроенных графов может позволить гамильтонову поисковику пути очень быстро вернуть результат. Как только мы рандомизируем его, он FindHamiltonianPathможет стать непривычно медленным. Вот что, кажется, происходит с этим графиком:

g = GraphData["GreatRhombicosidodecahedralLineGraph"]

Поэтому может оказаться более практичным перечислять не все, а некоторые циклы / пути и выбирать из них случайным образом.