Научная электронная библиотека

Монографии, изданные в издательстве Российской Академии Естествознания

Дискретная оптимизация и моделирование в условиях неопределенности данных

Перепелица В. А., Тебуева Ф. Б.,

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- критериальные задачи об остовном дереве.