Взаимно-рекуррентные формулы для перечисления разбиений прямоугольника

Магомедов, Абдулкарим Магомедович; Магомедов, Тагир Абдулкаримович; Лавренченко, Сергей Александрович

Взаимно-рекуррентные формулы для перечисления разбиений прямоугольника

Магомедов, Абдулкарим Магомедович, Магомедов, Тагир Абдулкаримович, Лавренченко, Сергей Александрович

Дата публикации: 2019

Дата публикации в реестре: 2020-03-14T00:29:12Z

Аннотация:

Задача перечисления разбиений прямоугольника заданных целочисленных размеров h × w на прямоугольники 1 × 2 рассматривалась рядом авторов в связи с вопросами термодинамики потоков жидкости и проблемой перечисления совершенных паросочетаний плоского графа за полиномиальное время. В данной работе методами теории графов разработан алгоритм, компьютерное воплощение которого способно генерировать систему взаимно-рекуррентных формул для искомого перечисления разбиений прямоугольника произвольных целочисленных размеров. Решены вопросы инициализации рекуррентных формул; показано, что решение задачи организации вычислений в соответствии с системой формул, сгенерированных компьютером, сводится к топологической сортировке ациклического орграфа; сформулированы открытые задачи.

Ключевые слова:
перечисление разбиений прямоугольника, рекуррентные формулы

Тип: статьи в журналах

Источник: Прикладная дискретная математика. 2019. № 46. С. 108-121