Остовное дерево в делимом кратном графе

В статье рассматриваются неориентированные кратные графы произвольной натуральной кратности $k>1$. Кратный граф содержит ребра трех типов: обычные, кратные и мультиребра. Ребра последних двух типов представляют собой объединение $k$ связанных ребер, которые соединяют $2$ или $k+1$ вершину соответственно. Связанные ребра могут использоваться только согласованно. Если вершина инцидентна кратному ребру, то она может быть инцидентна другим кратным ребрам, а также она может быть общим концом $k$ связанных ребер мультиребра. Если вершина является общим концом мультиребра, то она не может быть общим концом никакого другого мультиребра.
Особое внимание уделяется классу делимых кратных графов, которые отличаются возможностью выделения $k$ частей, согласованных на всех связанных ребрах и не содержащих общих ребер. Каждая из частей является обычным графом.
Вводится понятие кратного дерева, определяются его основные свойства. В отличие от обычных деревьев количество ребер в кратных деревьях не фиксировано. Для делимых деревьев в работе приводится и обосновывается оценка минимального и максимального количества ребер.
Далее определяются понятия остовного дерева и полного остовного дерева. Для делимых графов доказывается критерий полноты остовного дерева. Также доказано, что полное остовное дерево всегда существует в делимом графе.
Если кратный граф является взвешенным, то для него можно поставить задачу о минимальном остовном дереве, а также о минимальном полном остовном дереве. В работе предложен эвристический алгоритм поиска минимального полного остовного дерева в делимом графе.