2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Формула для количества гамильтовых циклов в графе
Сообщение09.10.2022, 23:43 
Аватара пользователя
Здравствуйте. Я нашел формулу для подсчета количества гамильтоновых циклов в графе. Я ее проверил, на практике работает верно. Можете, пожалуйста, взглянуть на неё и сказать, что вы о ней думаете. Я первый раз оформлял работу в LaTeX, поэтому полностью открыт для конструктивной критики.
https://drive.google.com/file/d/1h4S-HUDDSQ4bfsfTrQ9xPH6ra_4qOTKw/view?usp=sharing
Работает формула в худшем случае за $O(n!)$
Для сравнения привожу формулу русских ученых, которая работает медленнее.
https://journals.rudn.ru/miph/article/view/8653/8104
Можете, пожалуйста, также сказать в чем преимущество этой формулы относительное моей.

 
 
 
 Re: Формула для количества гамильтовых циклов в графе
Сообщение10.10.2022, 02:43 
Аватара пользователя
Euler-Maskerony в сообщении #1566374 писал(а):
Работает формула в худшем случае за $O(n!)$
А «формула русских учёных» работает ещё медленнее? ;-D

 
 
 
 Re: Формула для количества гамильтовых циклов в графе
Сообщение10.10.2022, 08:44 
Аватара пользователя
Aritaborian в сообщении #1566378 писал(а):
А «формула русских учёных» работает ещё медленнее? ;-D

Если я правильно понял, там написано, что за $O(n^nlog(n))$

 
 
 
 Re: Формула для количества гамильтовых циклов в графе
Сообщение10.10.2022, 11:06 
Аватара пользователя
Просто перебор всех перестановок работает за $O(n!)$ (переход к следующей перестановке амортизированно работает за $O(1)$). И вроде бы это вы и делаете, только проверку перестановки расписываете через перемножение матриц.
Впрочем полезности "формулы русских ученых" я тоже не очень понимаю.

 
 
 
 Re: Формула для количества гамильтовых циклов в графе
Сообщение10.10.2022, 14:46 
Аватара пользователя
mihaild в сообщении #1566387 писал(а):
Просто перебор всех перестановок работает за $O(n!)$ (переход к следующей перестановке амортизированно работает за $O(1)$). И вроде бы это вы и делаете, только проверку перестановки расписываете через перемножение матриц.

Да. В этом суть, но мне подумалось, что отсюда можно что-нибудь извлечь. То есть 0/10 формула, получается?

 
 
 
 Re: Формула для количества гамильтовых циклов в графе
Сообщение10.10.2022, 15:55 
Аватара пользователя
Euler-Maskerony в сообщении #1566380 писал(а):
Если я правильно понял, там написано, что за $O(n^nlog(n))$
В преамбуле вроде бы иное написано.

 
 
 
 Re: Формула для количества гамильтовых циклов в графе
Сообщение11.10.2022, 18:34 
Аватара пользователя
Aritaborian в сообщении #1566417 писал(а):
В преамбуле вроде бы иное написано.

Там написано $O(n^klog(n))$ где $k$ - длина цикла.

 
 
 
 Re: Формула для количества гамильтовых циклов в графе
Сообщение11.10.2022, 23:32 
Аватара пользователя
Ну так это же не то же самое, что $O(n^nlog(n))$?

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group