|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Вычислительные методы в дискретной математике
Взаимно-рекуррентные формулы для перечисления разбиений прямоугольника
А. М. Магомедовa, Т. А. Магомедовb, С. А. Лавренченкоc a Дагестанский государственный университет, г. Махачкала, Россия
b Uber, г. Амстердам, Нидерланды
c Российский государственный университет туризма и сервиса, г. Москва, Россия
Аннотация:
Задача перечисления разбиений прямоугольника заданных целочисленных размеров $h\times w$ на прямоугольники ${1\times 2}$ рассматривалась рядом авторов в связи с вопросами термодинамики потоков жидкости и проблемой перечисления совершенных паросочетаний плоского графа за полиномиальное время.
В данной работе методами теории графов разработан алгоритм, компьютерное воплощение которого способно генерировать систему взаимно-рекуррентных формул для искомого перечисления разбиений прямоугольника произвольных целочисленных размеров. Решены вопросы инициализации рекуррентных формул; показано, что решение задачи организации вычислений в соответствии с системой формул, сгенерированных компьютером, сводится к топологической сортировке ациклического орграфа; сформулированы открытые задачи.
Ключевые слова:
перечисление разбиений прямоугольника, рекуррентные формулы.
Образец цитирования:
А. М. Магомедов, Т. А. Магомедов, С. А. Лавренченко, “Взаимно-рекуррентные формулы для перечисления разбиений прямоугольника”, ПДМ, 2019, № 46, 108–121
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdm688 https://www.mathnet.ru/rus/pdm/y2019/i4/p108
|
Статистика просмотров: |
Страница аннотации: | 220 | PDF полного текста: | 117 | Список литературы: | 22 |
|