Оптимальные эйлеровы конгруэнции бинарных неориентированных деревьев

        Общая постановка задачи формулируется следующим образом.  Пусть К – некоторый класс графов, а G – граф, не принадлежащий К. Требуется произвести те или иные изменения в структуре графа G, чтобы полученный граф G/ оказался К-графом (см. [4]). Очевидное требование, чтобы все вышеперечисленные изменения были оптимальными в том или ином смысле.
       В данной работе в качества класса К рассматривается класс эйлеровых графов. Класс эйлеровых графов является одним из важнейших классов, используемых в приложениях. В качества класса G рассматривается класс бинарных неориентированных деревьев. Класс бинарных неориентированных деревьев представляет собой большой теоретический интерес в силу того, что широко используются в качестве «базиса» для различных структур данных, таких как двоичная куча, красно-черное дерево, фибоначчиева куча и т. п.
       В работе решена задача нахождения оптимальных эйлеровых конгруэнций бинарных неориентированных деревьев. Получен конструктивный алгоритм решения задачи, имеющий полиномиальную асимптотическую сложность. Уточним, что в эйлеровых графах, являющихся ответом на поставленную задачу, допускается наличие петель, в силу того, что существуют бинарные неориентированные деревья, для которых любой факторграф по оптимальной эйлеровой конгруэнции содержит петли (к примеру, цепи P2 и P3).