Число Гамильтоновых циклов

Привет, подскажите как найти Число Гамильтоновых циклов, не через алгоритмы.. а просто зная количество вершин, ребер и связности... Возможно через матрицу смежности?

Привет, подскажите как найти Число Гамильтоновых циклов, не через алгоритмы.. а просто зная количество вершин, ребер и связности... Возможно через матрицу смежности?

Ну что значит не через алгоритмы? Вопрос лишен смысла.

А через алгоритм - да запросто, берешь и запускаешь рекурсивный перебор. Если вопрос заключается в том, можно ли как-то быстрее, без перебора, отвечаю: есть подозрение что это #P-полная задача (ну, как минимум не легче NP-полные задачи), так что как это сделать быстро (за полином от размера матрицы) пока никто не знает, возможно что вообще невозможно.

Мне препод сказал что должна быть какая то формула. Ну судя по всему придется с ней спорить)

Есть формула (и даже не одна) для n-го простого числа - http://en.wikipedia.org/wiki/Formula...oor_functi on
Но их никто не использует, они не практичны. Даже в теории. Что, легче стало, от этого факта?

Впрочем, что-то вроде формулы Миллса (см. ссылку выше), для твоей задачи, думаю, наверняка можно придумать

Может в каком то плане это поможет
http://www.mathnet.ru/php/getFT.phtm...ion_ lang=rus
но здесь даются нижние оценки для определенного типа графа

[maxal]

Возможно через матрицу смежности?

Возможно, если привлечь принцип включений-исключений. Вот здесь есть реализация этой формулы на PARI/GP: http://www.cse.sc.edu/~maxal/gpscripts/

Если граф сильно связан то есть полный то число циклов равно |V|! вроде

Ребята а вообще если постановку переформулировать вот так:
Дан неориентированный граф не полный но связанный
то каково количество Гамильтоновых путей в нем?

ну еще стоит добавить для уточнения что дано, количество вершин, количество ребер и как эти ребра соединены, как подсчитать количество путей за не экспоненциальное время? желательно по формуле за О(1)?

при этом сами пути выводить не нужно!

Если граф сильно связан то есть полный то число циклов равно |V|! вроде

в полном да, но сильно-связный - не значит полный

Ребята а вообще если постановку переформулировать вот так:
Дан неориентированный граф не полный но связанный
то каково количество Гамильтоновых путей в нем?

ну еще стоит добавить для уточнения что дано, количество вершин, количество ребер и как эти ребра соединены, как подсчитать количество путей за не экспоненциальное время? желательно по формуле за О(1)?

при этом сами пути выводить не нужно!

Задача - опрделить, есть ли хотя бы один гамильтоновый путь или нет, является классическим примером NP-сложной задачи. Делайте выводы.