ВЫЧИСЛЕНИЕ ВЕРШИН ПОЛИТОПОВ РАЗБИЕНИЙ ЧИСЕЛ
Аннотация
Описывается метод генерирования вершин политопов разбиений чисел, с помощью которого авторами были вычислены все вершины и опорные вершины политопов разбиений всех n ≤ 105 и все рюкзачные разбиения n ≤ 165. Метод не требует построения всех разбиений n. Вершины определяются с помощью достаточных и необходимых условий, в трудных случаях применяется известная программа Polymake. Подробно излагаются алгоритм проверки критерия, характеризующего разбиения, являющиеся выпуклыми комбинациями двух других; методика применения двух комбинаторных операций, преобразующих известные вершины в новые вершины, и способ применения программы Polymake для распознавания небольшого (для малых n) числа разбиений, являющихся выпуклыми комбинациями трех и более разбиений. Представляются результаты вычислений и формулируются новые проблемы, к которым приводят полученные данные о числах вершин и опорных вершин политопов разбиений чисел.
Об авторах
А. С. Врублевский
ИООО «Управляющая компания ”Атлант-М”»
Беларусь
Минск, Шаранговича, 22-А
Беларусь
Минск, Шаранговича, 22-А
В. А. Шлык
Командно-инженерный институт МЧС Республики Беларусь
Беларусь
Минск, Машиностроителей, 25
Беларусь
Минск, Машиностроителей, 25
Список литературы
1. Эндрюс, Г. Теория разбиений / Г. Эндрюс. – М. : Наука, 1982. – 256 с.
2. Эйлер, Л. Введение в анализ бесконечных / Л. Эйлер. – М. : Гос. изд. физ.-мат. лит., 1961. – Т. 1. – 316 с.
3. Dickson, L.E. History of the Theory of Numbers / L.E. Dickson. – Vol. II : Diophantine Analysis. – Washington : Carnegie Inst., 1919. – 520 p.
4. Шлык, В.А. Политопы разбиений чисел / В.А. Шлык // Весці Нац. акад. навук Беларусi. Сер. фiз.-мат. навук. – 1996. – № 3. – С. 89–92.
5. Shlyk, V.A. Polytopes of partitions of numbers / V.A. Shlyk // European J. Combin. – 2005. – Vol. 26, № 8. – P. 1139–1153.
6. Емеличев, В.А. Многогранники, графы, оптимизация (комбинаторная теория многогранников) / В.А. Емеличев, М.М. Ковалев, М.К. Кравцов. – М. : Наука, 1981. – 341 с.
7. Шлык, В.А. Комбинаторные операции порождения вершин политопа разбиений чисел / В.А. Шлык // Докл. Нац. акад. наук Беларуси. – 2009. – Т. 53, № 6. – С. 27–32.
8. Холл, М. Комбинаторика / М. Холл. – М. : Мир, 1970. – 424 с.
9. Gupta, H. Tables of partitions / H. Gupta, C.E. Gwyther, C.P. Winter // Royal society mathematical tables. – Vol. 4. – Cambridge : University Press, 1958. – 132 p.
10. Sloane, N.J.A. a(n) = number of partitions of n (the partition numbers) [Electronic resource] / N.J.A. Sloane. – 2010. – Mode of access : http://oeis.org/A000041. – Date of access : 11.10.2015.
11. Zoghbi, A. Fast algorithms for generating integer partitions / A. Zoghbi, I. Stojmenovic // Intern. J. Computer Math. – 1998. – Vol. 70. – P. 319–332.
12. Рейнгольд, Э. Комбинаторные алгоритмы: теория и практика / Э. Рейнгольд, Ю. Нивергельт, Н. Део. – М. : Мир, 1980. – 476 с.
13. Nijenhius, A. A method and two algorithms on the theory of partitions / A. Nijenhius, H.S. Wilf // J. Comb. Theory A. – 1975. – Vol. 18. – P. 219–222.
14. Riha, W. Efficient algorithms for doubly and multiply restricted partitions / W. Riha, K.R. James // Algorithm 29. Computing. – 1976. – Vol. 16. – P. 163–168.
15. Constant time generation of integer partitions / K. Yamanaka [et al.] // IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. – 2007. – Vol. E90-A, № 5. – P. 888–895.
16. Knuth, D.E. Generating all partitions. Pre-fascicle 3B of The Art of Computer Programming. A draft of sections 7.2.1.4-5 [Electronic resource] / D.E. Knuth. – 2004. – Mode of access : http://www.cs.utsa.edu/~wagner/knuth/fasc3b.pdf. – Date of access : 11.10.2015.
17. Kelleher, J. Generating all partitions: a comparison of two encodings [Electronic resource] / J. Kelleher, В. O'Sullivan. – 2009. – Mode of access : http://arxiv.org/pdf/0909.2331v1.pdf. – Date of access : 11.10.2015.
18. Opdyke, J.D. A unified approach to algorithms generating unrestricted and restricted integer compositions and integer partitions / J.D. Opdyke // J. Math. Model. Algor. – 2010. – Vol. 9, № 1. – P. 53–97.
19. Stojmenovic, I. Generating all and random instances of a combinatorial object / I. Stojmenovic // Handbook of applied algorithms: solving scientific, engineering, and practical problem. – Hoboken : John Wiley&Sons, 2008. – P. 1–38.
20. Shlyk, V.A. Number of vertices of the integer partition polytope [Electronic resource] / V.A. Shlyk. – 2012. – Mode of access : http://oeis.org/A203898. – Date of access : 11.10.2015.
21. Shlyk, V.A. Number of support partitions-vertices [Electronic resource] / V.A. Shlyk. – 2012. – Mode of access : http://oeis.org/A203899. – Date of access : 11.10.2015.
22. Ehrenborg, R. Number of knapsack partitions of n [Electronic resource] / R. Ehrenborg. – 2005. – Mode of access : http://oeis.org/A108917. – Date of access : 11.10.2015.
23. Шлык, В.А. Критерий представления разбиений чисел в виде выпуклой комбинации двух разбиений / В.А. Шлык // Вестник БГУ. Сер. 1. – 2009. – № 2. – С. 109–114.
24. Shlyk, V.A. Integer partitions from the polyhedral point of view / V.A. Shlyk // Electron. Notes Discrete Math. – 2013. – Vol. 43. – P. 319–327.
25. Shlyk, V.A. Polyhedral approach to integer partitions / V.A. Shlyk // Journal of Combinatorial Mathematics and Combinatorial Computing. – 2014. – Vol. 89. – P. 113–128.
26. Gawrilow, E. Polymake: a framework for analyzing convex polytopes / E. Gawrilow, E.M. Joswig // Polytopes – combinatorics and computation. – Basel : Birkhäuser, 2000. – P. 43–73.
27. Шлык, В.А. О вершинах политопов разбиений чисел / В.А. Шлык // Докл. Нац. акад. наук Беларуси. – 2008. – Т. 52, № 3. – С. 5–10.
28. Handbook of Mathematical Functions / M. Abramowitz, I.A. Stegun [eds]. – Applied Math. Series 55. – Washington : Government Printing Office, 1972. – 1046 p.
29. Barvinok, A.I. Polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed / A.I. Barvinok // Math. Oper. Res. – 1994. – Vol. 19. – P. 769–779.
30. Effective lattice point counting in rational convex polytopes / J.A. De Loera [et al.] // Journal of Symbolic Computation. – 2004. – Vol. 38, № 4. – P. 1273–1302.
31. Ehrenborg, R. The Möbius function of partitions with restricted block sizes / R. Ehrenborg, M.A. Readdy // Adv. in Appl. Math. – 2007. – Vol. 39, № 3. – P. 283–292.
Рецензия
Для цитирования:
Врублевский А.С., Шлык В.А. ВЫЧИСЛЕНИЕ ВЕРШИН ПОЛИТОПОВ РАЗБИЕНИЙ ЧИСЕЛ. Информатика. 2015;(4):34-48.
For citation:
Vroublevski A.S., Shlyk V.A. COMPUTING VERTICES OF INTEGER PARTITION POLYTOPES. Informatics. 2015;(4):34-48. (In Russ.)
Просмотров: 887
Послать статью по эл. почте 