Алгоритмы построения максимальных графических разбиений, доминирующих заданное графическое разбиение : магистерская диссертация

Abstract

В работе рассмотрены разбиения целых неотрицательных чисел и изучены некоторые детали строения решеток разбиений. Решетка разбиений задается отношением доминирования, которое определяется как покомпонентное доминирование соответственных частичных сумм разбиений. Особое внимание уделено графическим разбиениям. Графическим называется разбиение, которые составлено из степеней вершин графа с добавлением нулей. Проведено исследование множества максимальных графических разбиений, доминирующих заданное графическое разбиение. Для исследования написана компьютерная программа на языке Python, позволяющая проверять гипотезы для разбиений небольших чисел. Основной результат работы – алгоритм построения всех максимальных графических разбиений, доминирующих заданное разбиение и имеющих такой же вес. Этот алгоритм базируется на основной теореме, которая описывает точное строение множества таких максимальных графических разбиений. Приведена программная реализация найденного алгоритма.

The work examines partitions of non-negative integers and studies some details of the structure of partition lattices. The lattice of partitions is given by a dominance relation, which is defined as the component-wise dominance of the corresponding partial sums of partitions. Particular attention is paid to graphical divisions. A graphical partition is a partition that is composed of the degrees of the vertices of the graph with the addition of zeros. A study of the set of maximal graphical partitions that dominate a given graphical partition has been carried out. For the study, a computer program was written in Python, which allows testing hypotheses for partitions of small numbers. The main result of the work is an algorithm for constructing all maximal graphical partitions that dominate a given partition and have the same weight. This algorithm is based on a fundamental theorem that describes the exact structure of the set of such maximal graphical partitions. A software implementation of the found algorithm is given.