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

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

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

5.4. Полиномиально разрешимые подклассы интервальных задач на графах

Теорема 5.1 констатирует сведение интервальных задач на графах к 2-критериальным задачам. Как известно [3], задачи оптимизации на графах с ВЦФ весового вида (5.3)-(5.4) являются труднорешаемыми. Существует ряд подходов к тому, чтобы элиминировать проблему труднорешаемости, которая обусловлена свойством полноты (см. определение 5.6). Один из таких подходов состоит в том, чтобы ввести специальные дополнительные условия (ограничения) в математическую постановку рассматриваемой массовой задачи. Например, для ВЦФ вида (5.3)-(5.4) вместо второго минимизируемого (максимизируемого) критерия весового вида ввести критерий вида MINMAX (MAXMIN). В результате такой замены получаем, что максимальная мощность ПМА , ограничена полиномом порядка [3].

По аналогии с 2-критериальными задачами [89] для рассматриваемых интервальных задач на графах представляют интерес такие нетривиальные условия, при которых мощность ПМА для всех ограничена сверху константой или хотя бы полиномом от n "невысокой" степени. В этой связи рассмотрим интервальную задачу покрытия графа звездами при выполнении следующих условий:

1) множество ТГ состоит из одного элемента, который является -вершинной звездой;

2) задача рассматривается на 2-дольных графах , у которых число вершин первой (второй) доли равно (), общее число вершин кратно и ;

3) всякое допустимое решение представляет собой такой остовный подграф графа , у которого каждая из компонент связности является - вершинной звездой, а ее центр – это некоторая вершина ;

4) ребра взвешены интервалами из множества , состоящего из интервалов одинаковой длины, т.е. интервалы из удовлетворяют равенствам

, .(5.14)

Определяемую условиями 1) – 4) задачу покрытия графа звездами с ИЦФ (5.1)-(5.2) будем обозначать символом . Доказательство полиномиальной разрешимости задачи является конструктивным, т.е. оно базируется на описании и обосновании соответствующего полиномиального алгоритма , который состоит из трех этапов.

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

Этап 2. Сначала в графе интервальные веса ребер заменяются на числа . Далее в 1-взвешенном графе с помощью подходящего алгоритма [65] (например, венгерский алгоритм) выделяем оптимальное совершенное паросочетание , где через обозначаем подмножество всех вершин , смежных с дубликатами или с самой вершиной ; мощность , ; . В завершение этапа 2 для каждого ребра числовой вес заменяется на первоначальный интервальный вес .

Этап 3. К полученному совершенному паросочетанию применяется известная операция склеивания вершин графа: для каждого , вершины-дубликаты склеиваются с вершиной ; для полученной после склеивания с вершины оставляем обозначение . Эта вершина является центром полученной -взвешенной звезды, состоящей из ребер таких, что . Результатом работы этапа 3 является остовной подграф исходного графа , его компонентами связности являются - вершинных звезд с центрами в вершинах , , т.е. является допустимым решением задачи .

Обозначим через подмножество 2-дольных графов , удовлетворяющих условиям 1) – 4) задачи .

Теорема 5.4. Для всякого графа с непустым МДР задачи ее ПМА состоит из одного допустимого решения , которое алгоритм находит с вычислительной сложностью .

Доказательство. Рассмотрим индивидуальную задачу [27] с минимизируемой ИЦФ (5.1) на конкретном графе и определим на МДР для интервальных значений его ИЦФ (5.1)-(5.2) бинарное отношение нестрогого предпочтения . Выражение означает выполнение нестрогих неравенств , .

По определению алгоритма на его выходе получаем допустимое решение , на котором достигает минимума значение левого конца ИЦФ (5.1)-(5.2):

(5.15)

Из равенств (5.14) следует, что в представлении (5.2) концов интервала (5.1) значение правого конца определяется выражением

, ,(5.16)

где . Из (5.15) и (5.16) получаем, что для значения ИЦФ выполняется бинарное отношение нестрогого предпочтения по отношению к любому допустимому решению : , . При этом согласно определения этапа 2 вычислительная сложность алгоритма имеет тот же порядок, что и вычислительная сложность задачи о совершенных паросочетаниях на двудольном графе [65]: .

Теорема 5.4 доказана.

Определяемую условиями 1) – 4) полиномиально разрешимую задачу можно расширить, ослабив представленное выше условие 2) следующим образом. Задачу покрытия графа звездами рассматриваем на всех графах , но при условии, что множество ТГ состоит из такой звезды, у которой число вершин

,(5.17)

где – это независимая от константа. В этом случае можно предложить полиномиальный алгоритм , у которого подготовительный этап осуществляет перебор вариантов множества вершин первой доли для индуцируемых в данном графе 2- дольных графов , , . Вычислительная сложность этого перебора определяется числом сочетаний из элементов по , т.е. она ограничена сверху полиномом . Далее, для каждого варианта первой доли осуществляется решение рассмотренной выше индивидуальной задачи на конкретном 2-дольном графе , , . Заметим, что для всякого выполняется неравенство . Таким образом, неравенство (5.17) вместе с условиями 1), 3) и 4) определяют собой еще один подкласс полиноминально разрешимых интервальных задач покрытия графа звездами.