Подсчет количества путей через граф

Question

Я ищу количество уникальных путей длиной x в графе, начинающемся с определенного узла.

Однако у меня есть ограничение, что ни один узел не посещается более одного раза на любом пути.

---

Например, возьмите следующий график:

Если я после числа трех путей длины, начинающихся с 5.

ответ будет 9.

5 -> 2 -> 1 -> 3
5 -> 2 -> 4 -> 3
5 -> 2 -> 4 -> 7
5 -> 4 -> 2 -> 1
5 -> 4 -> 3 -> 1
5 -> 4 -> 7 -> 6
5 -> 6 -> 7 -> 4
5 -> 7 -> 4 -> 2
5 -> 7 -> 4 -> 3

Примечание. Я согласен только с ответом (9) , а не с конкретными путями .

---

Я пытался использовать Матрица смежности в степени x , чтобы дать число путей, но я не могу понять, как учитывать ограничение уникальных узлов.

Я также пытался использовать поиск в глубину , но количество узлов и размер x делают это неосуществимым.

---

РЕДАКТИРОВАТЬ: Confused DFS с BFS (спасибо Nylon SmileИ Никита Рыбак).

Answer 1

Это NP-Hard.

Сокращение от гамильтонова пути.

Учитывая граф, существование Гамильтонова Пути которого мы должны проверить ...

Запустите ваш алгоритм для каждой вершины с длиной пути n-1. Любой ненулевой возврат соответствует гамильтонову пути и наоборот.

Таким образом, в принципе, если вы найдете алгоритм полиномиального времени для решения вашей проблемы, то у вас есть алгоритм полиномиального времени для решения задачи о гамильтоновом пути, эффективно доказывающий P = NP!

Примечание. Предполагается, что x является вводом.

Если вы зафиксировали x (т. Е. Независимо от количества вершин в графе), то у вас есть O (n ^ x) временных алгоритмов, которые есть в P, но все же довольно непрактично для среднего размера x.

Answer 2

Эта проблема является проблемой подсчета в #P (количество решений) вместо проблемы решения в NP (да или нет).

Сокращение Морон все еще работает, чтобы доказать проблему # P-Complete , потому что Hamilton Paths также # P-complete.