Задача про графы

Доброго времени суток!
Прошу помочь с решением задачки.

Допустим есть граф следующего вида
https://content.foto.my.mail.ru/mail/goblin-puk/579/h-618.jpg

Задача: определить количество возможных путей без петель (фактически гамильтонов граф).
Допустим надо попасть из X1 в X3. Эмпирически подходящие маршруты только Х1 – Х3 и Х1 – Х4.
https://content.foto.my.mail.ru/mail/goblin-puk/579/h-619.jpg

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



Редактировалось 1 раз(а). Последний 09.11.2016 18:27.