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

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) определяют собой еще один подкласс полиноминально разрешимых интервальных задач покрытия графа звездами.


Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074