NP-полнота задачи о минимальном остовном дереве в кратном графе кратности $k \geqslant 3$

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