Научная электронная библиотека
Монографии, изданные в издательстве Российской Академии Естествознания
Дискретная оптимизация и моделирование в условиях неопределенности данных
Перепелица В. А., Тебуева Ф. Б.,
3.5.2. Вычислительная сложность 1-критериальных задач
Рассмотрим сначала 1-критериальные, т.е. оптимизационные постановки задачи об остовном дереве. В случае весовой целевой функции (3.9) данная задача имеет полиномиальную вычислительную сложность. Этот факт получил обоснование в предыдущем п. 3.4.
Для задачи с целевой функцией MINMAX вида (3.10) полиномиальный алгоритм состоит из двух этапов. На первом этапе все ребра 
упорядочиваются и нумеруются вдоль последовательности убывания их весов:
, 
.(3.13)
Далее ребра 
, 
последовательно вдоль (3.13) удаляются из графа 
до тех пор, пока ещё сохраняется связность остающегося подграфа 
. Пусть эта связность нарушается при удалении ребра 
, вес которого 
. Является справедливым следующее очевидное
Примечание 3.5. Если 
– это множество всех остовных деревьев подграфа 
, то всякое 
содержит ребро , и в силу определения последовательности (3.13) и вычислительной схемы первого этапа для целевой функции MINMAX (3.10), её значение равно 
для всех . Причем, если в последовательности (3.13), имеет место строгое неравенство 
, то множество 
не содержит остовного дерева, оптимального по целевой функции MINMAX (3.10).
Если в подграфе количество его ребер равно 
, то на втором этапе из него удаляется 
ребер в произвольном подходящем порядке так, что после каждого удаления оставшийся подграф является связным. Оставшиеся, т.е. не удаленные 
ребер образуют остовное дерево данного графа . В силу примечания 3.5 это остовное дерево является оптимальным по целевой функции MINMAX (3.10), обозначим его 
.
Оценивая вычислительную сложность представленного выше 2-этапного алгоритма 
, отметим, что верхняя оценка для неё получается путём 
- кратного применения алгоритма проверки на связность очередного подграфа 
. Если получается как результат удаления из подграфа 
ребра 
, то связность 
можно проверить с помощью алгоритма Дийкстры, осуществляя попытку найти цепь 
. По определению подграф является связным и, следовательно, связность сохраняется, если эта цепь существует. Поскольку 
и трудоёмкость алгоритма Дийкстры не превосходит 
, то для суммарной вычислительной сложности проверок на связность справедлива следующая верхняя оценка:
.(3.14)
Правая часть выражения (3.14) является верхней оценкой вычислительной сложности рассматриваемого 2-этапного алгоритма потому, что трудоёмкость построения последовательности (3.13) ограничена сверху величиной 
[26], [91].
Приведенные выше рассуждения, включая описание 2-х этапного алгоритма, представляют собой конструктивное доказательство следующей теоремы.
Теорема 3.1. Двухэтапный алгоритм 
находит оптимальное по целевой функции MINMAX (3.10) остовное дерево с верхней оценкой вычислительной сложности 
.
В контексте анализа сложности задач с комбинаторными критериями (3.11) и (3.12) можно сформулировать следующее
Примечание 3.6. Задача об остовном дереве с целевой функцией минимизируемой степени или максимизируемого диаметра является NP-трудной. Обоснование этого факта см. в [27] (приложение А 2.1). Здесь же отмечено свойство NP-полноты для «остова ограниченного диаметра», т.е. нахождение остовного дерева с минимизируемой целевой функцией диаметра (3.12) также является NP-трудной задачей.
Неизвестно, существуют ли труднорешаемые 1- критериальные задачи об остовном дереве.