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

Автор темы nlegion01 
ОбъявленияПоследний пост
ОбъявлениеПравила и принципы форума «Высшая математика»28.10.2009 15:17
ОбъявлениеВакансия: Разработчик WebCrawler и аналитик данных16.11.2015 10:19
ОбъявлениеАспирантура в Норвегии и Германии07.12.2015 14:00
09.11.2016 18:26
Задача про графы
Доброго времени суток!
Прошу помочь с решением задачки.

Допустим есть граф следующего вида
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.
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти