Number of physical connectivity states in transfer matrix method for enumeration of Hamiltonian circuits in rectangular lattice
Автор: Karavaev A.M.
Журнал: Ученые записки Петрозаводского государственного университета @uchzap-petrsu
Рубрика: Физико-математические науки
Статья в выпуске: 8 (129) т.2, 2012 года.
Бесплатный доступ
We obtained a formula for the exact number of physical connectivity states, which are constructed by the transfer matrix method for the enumeration of Hamiltonian circuits’ number in a P m x P n lattice. We prove that the number of physical states is asymptotically square root of m times smaller than the Motzkin number. The obtained formulae allowed us to get a better understanding the complexity of the problem.
Transfer matrix method, hamiltonian circuits, circuits in a lattice
Короткий адрес: https://sciup.org/14750284
IDR: 14750284
Список литературы Number of physical connectivity states in transfer matrix method for enumeration of Hamiltonian circuits in rectangular lattice
- Караваев А. М. Кодирование состояний в методе матрицы переноса для подсчета гамильтоновых циклов на прямоугольных решетках, цилиндрах и торах//Информационные процессы. 2011. Т. 11. № 4. С. 476-499.
- Cloizeaux J., Jannink G. Polymers in Solution: Their Modelling and Structure. Oxford: Clarendon Press, 1990. 928 p.
- Hamilton cycles@FlowProblem web-project [Electronic resource]. Access mode: http://flowproblem.ru/cycles/hamilton-cycles
- Kloczkowski A., Jernigan R. L. Transfer matrix method for enumeration and generation of compact self-avoiding walks. I. square lattices//Journal of Chemical Physics. 1998. Vol. 109. P. 5134-5146.
Статья научная
