Генерация графов только с одним действительным гамильтоновым циклом

Question

Я ищу несколько советов / указаний в правильном направлении.

Мое требование состоит в том, чтобы сгенерировать график, а не решать один для решения.

Я ищу реализовать алгоритм для генерации графа (сетка NxN) только с 1 гамильтоновым циклом. Обратите внимание, что только одно уникальное решение имеет ключевое значение. График будет NxN сеткой узлов, каждый из которых имеет только 4 соседних узла, то есть верхний, правый, нижний, левый. Узлы можно посетить только один раз. Помимо этого, могут быть некоторые специальные узлы.

1. Мертвые узлы, т.е. они не имеют краевых соединений
2. Фиксированный узел входа и выхода, т.е. узлы входа и выхода уже определены, и никакой другой узел не может соединиться с данным узлом. Это может быть. смежные узлы б. прямые узлы

Некоторые примеры:

@ - means that nodes can be connected with adjacent nodes (top,right,bottom,left)
$ - indicated dead end (no connections with adjacent nodes)

Graph 1 =>
@-@-@
@-$-@
@-@-@

Solution 1 =>
1-2-3
8-$-4
7-6-5

here the solution of the graph is 1->2->3->4->5->6->7->8->1. Notice how the $ node was not included in the final solution.

---

Мой подход:

Я беру сетку * n и начинаю с размещения случайных мертвых узлов на графике. После этого я размещаю случайные специальные узлы. Затем я запускаю поиск dfs, который просматривает всю сетку, чтобы увидеть, является ли действительный цикл представлением, который удовлетворяет специальным критериям узла и посещает каждый узел только один раз (за исключением начального узла) и заканчивается на начальном узле, что делает его полным циклом.

Мои вопросы:

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

Как бы вы идеально подошли к этой проблеме?

Answer 1

Почему бы просто не соединить внешние узлы в круг и пометить все внутренние узлы как "мертвые узлы"?

Например, заимствуя вашу запись сверху...

График 3х3

@@@
@$@
@@@

График 4х4

@@@@
@$$@
@$$@
@@@@

График 5х5

@@@@@
@$$$@
@$$$@
@$$$@
@@@@@

Всегда будет только одно решение, и легко генерировать графики произвольного размера.

Answer 2

Сначала я хотел бы отметить, что я еще не нашел полное решение.

То, что я хотел бы сделать, это сгенерировать цикл в сетке и сохранить это "решение", а затем добавить тупик на все пропущенные квадраты, что делает сгенерированный цикл гамильтонианом. тогда я следовал бы вашему подходу, итеративно добавляя "вынужденные ребра" и проверяя, существует ли второй (читай: "более одного") гамильтонов цикл.

эта проверка может быть сформулирована как следующий вопрос: "Как вы проверяете, содержит ли данный планарный граф более одного гамильтонова цикла, если вы его знаете?".

причина, по которой я использую "планар", легко объяснима. Ваша начальная сетка является плоской, и удаление узлов или вынужденных ребер не делает ее неплоской. Это связано с тем, что принудительный фронт AB может быть преобразован в AXB, где X является новым узлом и, следовательно, должен посещаться любым гамильтоновым циклом, который приводит к посещению принудительного края.

Один способ, которым я пытался преобразовать один гамильтонов цикл в другой, приведен ниже:

Если вы берете два плоских гамильтоновых цикла и берете все ребра там, где они не совпадают, они образуют цикл (который может посещать узлы более одного раза). Этот цикл имеет свойство чередования ребер между одним гамильтоновым циклом и другим. Я не мог найти способ полностью изменить этот процесс.