Программа построения взвешенного двоичного дерева для перечисления разбиений прямоугольника
разбиение прямоугольник плитки граф паросочетание
Предназначение. Программа предназначена для подсчета T(w,h)   - количества всевозможных разбиений заданного прямоугольника M w×h на плитки 1×2. 
Актуальность. Задача имеет тесные связи с проблемой перечисления всех совершенных паросочетаний в решёточном графе. В отличие от известных трудоёмких решений наш алгоритм (и программа) использует только операции сложения целых чисел, поэтому программа обладает высоким быстродействием. 
Базовый алгоритм. Программа базируется на процессе построения двоичного дерева, корень v_0 которого соответствует пустому разбиению; вершине v_0 присваивается вес, равный единице. Потомок любой вершины v_i - частичного разбиения – создаётся покрытием горизонтальной и/или вертикальной плиткой клетки M, первой в упорядочении «слева-направо», «сверху-вниз» ещё непокрытых клеток. Полным разбиениям соответствуют листья дерева, количество листьев последнего уровня дерева и равно искомому T(w,h). Вновь созданной вершине v_k присваивается структурированная метка, включающая: 1) k - номер вершины, 2) номер её родителя, 3) вес (который наследуется от родителя, но впоследствии может быть изменён), 4) уровень, 5) идентификатор из w чисел, j-е из которых равно количеству клеток, покрытых в j-м столбце частичного разбиения, соответствующего вершине v_k. После создания вершины дерева её метка, как правило, заносится в список L. Последовательно просматриваются вершины дерева и создаются их потомки; алгоритм завершается, когда просмотрены все вершины с метками, занесёнными в L. При таком подходе дерево и список меток получаются громоздкими, занимают много памяти и времени.  
Новизна: если при создании вершины v_k (с некоторым унаследованным весом F и идентификатором D) в списке L уже имеется её близнец – вершина с идентификатором, равным D в обычной или реверсной записи, - то v_k не заносится в L, её вес добавляется к весу F близнеца, после чего вершина v_k далее в построении дерева не участвует («метод близнецов»). Сумма весов листьев последнего уровня и равно T(w,h). Если, например, при w=6,h=10 на вычисление значений T(w,h),h=1,2,…,10 при использовании базового алгоритма понадобились 1365 сек., а двоичное дерево содержало 16968987 вершин, то при использовании метода близнецов – 0, 468 сек. и 382 соответственно.
Дополнительные возможности. Кроме значений T(w,h), программа выводит информативный рисунок дерева, который представляет ценный для исследователя наглядный материал; все вершины снабжены метками, размещение вершин исключает пересечение ребер дерева. Рисунок интерактивный: предусмотрены выбор и перемещение вершин вручную курсором мыши, масштабирование и сохранение рисунка в файле.
а) В перечислительной комбинаторике для вычисления совершенных паросочетаний в решёточных графах; б) на лекциях по дискретной математике – в качестве иллюстрированного презентационного материала.
Абдулкарим
Магомедов
Магомедович
Заведующий кафедрой
Доктор физико-математических наук
Профессор
AHE-13894-2022
7005785836
5008
0000-0002-2482-1239
РОССИЯ
Муртазали
Рабаданов
Хулатаевич
Ректор
РОССИЯ
20.01.45
Преподавание информатики
27.45.17
Теория графов
01.02.EW
COMPUTER SCIENCE, SOFTWARE ENGINEERING
Абдулкарим
Магомедов
Магомедович
Разработка программы
РОССИЯ
ДГУ
Федеральное государственное бюджетное образовательное учреждение высшего  образования "Дагестанский государственный университет"
1020502631621
Организация
Министерство науки и высшего образования Российской Федерации
Федеральные государственные бюджетные учреждения
ДГУ
Федеральное государственное бюджетное образовательное учреждение высшего  образования "Дагестанский государственный университет"
1020502631621
Организация
Министерство науки и высшего образования Российской Федерации
Федеральные государственные бюджетные учреждения