Полиэдральные графы задач об остовных деревьях при дополнительных ограничениях

Исследуются полиэдральные графы двух задач о минимальном остовном дереве при дополнительных ограничениях. В первой задаче речь идет об отыскании дерева с минимальной суммой весов ребер среди всех остовных деревьев, количество висячих вершин которых не превосходит заданную величину. Во второй задаче дополнительное ограничение заключается в предположении о том, что степени всех вершин искомого дерева не превосходят заданную величину. Обе рассматриваемые задачи в варианте распознавания являются NP-полными.
В работе изучаются многогранники указанных задач и их графы. Устанавливается, что в обоих случаях распознавание смежности вершин этих графов представляет собой NP-полную задачу. Несмотря на это, удается получить сверхполиномиальные нижние оценки плотности (кликового числа) этих графов, которые характеризуют временную трудоемкость в широком классе алгоритмов, использующих линейные сравнения. Приведенные результаты свидетельствуют о принципиальном отличии комбинаторно–геометрических свойств рассматриваемых задач от классической задачи о минимальном остовном дереве.