Научный журнал
Международный журнал прикладных и фундаментальных исследований

ISSN 1996-3955
ИФ РИНЦ = 0,686

МЕТОД ПОСТРОЕНИЯ МАКСИМАЛЬНОГО НЕЗАВИСИМОГО МНОЖЕСТВА НАИБОЛЬШЕЙ МОЩНОСТИ

Дудов М.Х. 1
1 Северо-Кавказская государственная гуманитарно-технологическая академия
В статье предлагается метод построения максимального независимого множества наибольшей мощности, вычислительная сложность которого не превышает O(n7). Задачу о максимальном независимом множестве наибольшей мощности принято относить к классу NP-полных в области теории графов. Одним из известных способов решения является применение симплекс-метода к «ослабленной» задаче, т.е. без требования целочисленности, и если полученное решение целочисленно, то оно является решением и исходной задачи. Но, как и во многих других графовых задачах, представленных в виде задачи линейного программирования, наличие на графе циклов нечётной длины обуславливает возможность получения нецелочисленного оптимального решения. Показано, что для рассматриваемой задачи отсечение Гомори совпадает с ограничением, соответствующим одному из циклов нечётной длины. Предлагаемый алгоритм и особенности рассматриваемой задачи, отличающие её от общей задачи линейного программирования, позволяют оценить вычислительную сложность применения симплекс-метода к «ослабленной» задаче величиной O(n5), а поскольку количество отсечений, соответствующих последовательно выделяемым циклам нечётной длины, не больше количества ребер графа, то для решения задачи предлагаемым методом требуется не более чем O(m)-кратное применение алгоритма к последовательности «ослабленных» задач.
графы
независимое множество наибольшей мощности
вычислительная сложность
1. Гери М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – М.: Мир, 1982.
2. Пападимитриу Х.Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. – М.: Мир, 1984.
3. Свами М., Тхуласираман К. Графы, сети и алгоритмы. – М.: Мир, 1984.
4. Ху Т. Целочисленное программирование и потоки в сетях. – М.: Мир, 1974.
5. Н. Кристофидис. Теория графов. Алгоритмический подход. – М.: Мир, 1978.
6. Kuhn H. W. Class Notes, Princeton University, 1976.
7. Хачиян Л.Г. Сложность задач линейного программирования. – М.: Знание, 1987.
8. Ашманов С.А. Линейное программирование. – М.: Наука, 1981.

Множество вершин графа называется независимым, если никакие две вершины этого множества не соединены ребром. Задача распознавания: существует ли в заданном графе независимое множество размера не меньше K? Соответствующая ей оптимизационная задача, она же задача о независимом множестве, формулируется следующим образом: в заданном графе требуется найти независимое множество максимального размера. В задаче о максимальном независимом множестве входом служит неориентированный граф, а выходом – максимальное независимое множество в этом графе. Если существует несколько таких множеств, достаточно найти одно.

1. Постановка задачи

Рассмотрим следующую задачу [1, ТГ1]:

Заданы граф duduv1.wmf, duduv2.wmf и целое положительное число duduv3.wmf. Существует ли на G независимое множество вершин мощностью не менее K или, иначе говоря, существует ли подмножество duduv4.wmf, такое, что duduv5.wmf и никакие две вершины из duduv6.wmf не соединены ребром из E?

Пусть duduv7.wmf, если вершина duduv8.wmf, и duduv9.wmf, если duduv10.wmf. Сопоставим каждому ребру графа номер duduv11.wmf.

Тогда, следуя методологии [2], рассматриваемую задачу можно представить в виде целочисленной задачи линейного программирования (1):

duduv12.wmf; (1.1)

duduv13.wmf; (1.2)

duduv14.wmf; (1.3)

duduv15.wmf; (1.4)

duduv16.wmf; (1.5)

duduv17.wmf, (1.6)

где F – целевая функция, равная количеству вершин максимального независимого множества наибольшей мощности; duduv18.wmf, duduv19.wmf, – переменные, соответствующие вершинам исходного графа G; duduv20.wmf, duduv21.wmf, – переменные, соответствующие рёбрам графа G.

Представим задачу в виде обычной задачи линейного программирования, исключив условие целочисленности (2):

duduv22.wmf; (2.1)

duduv23.wmf; (2.2)

duduv24.wmf; (2.3)

duduv25.wmf; (2.4)

duduv26.wmf. (2.5)

Одним из известных способов решения задачи (1) является применение симплекс-метода к задаче (2) и если полученное оптимальное решение целочисленно, то оно является решением и задачи (1). Но, как и во многих других графовых задачах [2-4], представленных в виде ЗЛП, наличие на исходном графе циклов нечётной длины обуславливает, в общем случае, нецелочисленность оптимального решения. В таком случае по последней симплекс-таблице формируют дополнительное ограничение так, чтобы полученное нецелочисленное решение стало недопустимым при сохранении допустимости всех возможных целочисленных решений. Такого рода дополнительные ограничения называются правильными отсечениями, например, отсечение Гомори.

2. Отсечения Гомори для задачи (1)

Пусть на графе G существует цикл C длины k, причем k – нечетное. Тогда в максимальное независимое множество наибольшей мощности duduv27.wmf могут войти не более duduv28.wmf вершин цикла C, поскольку никакие две вершины из duduv29.wmf не соединены ребром по определению.

Между тем, применение симплекс-метода к (2) может дать оптимальное решение, компоненты которого, соответствующие циклу C, нецелочисленные, поскольку вклад переменных duduv30.wmf в целевую функцию задачи (2) равен duduv31.wmf, если переменные нецелочисленные, и duduv32.wmf, если переменные целочисленные. При нечётных k справедливо duduv33.wmf, и при отсутствии каких-либо дополнительных ограничений на эти переменные симплекс-метод может найти именно это оптимальное нецелочисленное решение. Например, если в результате иттераций в базис введены переменные, соответствующие вершинам цикла C, и выведены переменные, соответствующие рёбрам этого же цикла.

Поэтому с целью исключения нецелочисленного решения можно выделить все циклы нечётной длины и для каждого явно указать, что

duduv34.wmf, (3)

дополнив (2) соответствующими ограничениями (3).

Покажем, что неравенства типа (3) являются для данной задачи отсечениями Гомори.

Ограничения задачи (2), соответствующие циклу C (рисунок), имеют следующий вид:

duduv38.wmf;

duduv39.wmf;

duduv40.wmf;

…………………

duduv41.wmf;

duduv42.wmf.

dud1.tif

Цикл длины k, xi, duduv35.wmf, – переменные, соответствующие вершинам C; duduv36.wmf, duduv37.wmf, – переменные, соответствующие рёбрам C

Отсечение Гомори формируется по одной из нецелочисленных строк симплекс-таблицы, пусть это строка, соответствующая переменной duduv43.wmf.

Пусть базисными переменными оптимальной симплекс-таблицы являются duduv44.wmf, выразим duduv45.wmf через свободные переменные, подставив в последнее уравнение вместо базисных переменных их выражения через свободные:

duduv46.wmf

duduv47.wmf,

duduv48.wmf.

Сформируем отсечение Гомори:

duduv49.wmf,

где duduv50.wmf – дробная часть а,

duduv52.wmf,

с учётом исходной системы ограничений имеем

duduv53.wmf,

duduv54.wmf,

в итоге

duduv55.wmf.

А так как k – нечётное, то

duduv57.wmf,

что полностью соответствует (3).

4. Метод решения задачи (1)

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

5. Вычислительная сложность метода

Вычислительная сложность обычного применения симплекс-метода с отсечениями Гомори для задачи (1) определяется вычислительной сложностью собственно симплекс-метода на задачах типа (2) и возможным количеством отсечений.

Известно [7,8], что для общей задачи линейного программирования вычислительная сложность симплекс-метода неполиномиальна по двум причинам.

Во-первых, существует возможность «зацикливания» алгоритма, т.е. многократно повторяемый ввод и вывод из базиса одних и тех же переменных, причём без изменения целевой функции. Во-вторых, коэффициенты при переменных в исходной системе ограничений могут быть таковы, что до получения оптимального решения придётся перебрать все возможные допустимые решения, причём приращения целевой функции на каждой такой иттерации положительны.

Применение стандартных приемов [2-8] позволяет избежать зацикливания алгоритма симплекс-метода, поэтому принципиальное значение имеет вторая причина неполиномиальности симплекс-метода для общей задачи линейного программирования.

Особенностью задачи (2) является то, что максимально возможное значение целевой функции известно заранее и равно n, поскольку мощность любого независимого множества вершин на графе не больше количества вершин этого графа.

С другой стороны, поскольку при получении первого же нецелочисленного допустимого решения работа алгоритма симплекс-метода останавливается, то ненулевые приращения целевой функции задачи (2) в ходе иттераций не менее чем «1». Известно [2, 6], что если алгоритм Блэнда обнаруживает цикл, то при выходе из цикла целевая функция получает положительное приращение. Поэтому нулевые приращения целевой функции при использовании алгоритма Блэнда для рассматриваемой задачи возможны лишь при проведении иттераций с переменными, соответствующими вершинам и рёбрам некоторого дерева. Следовательно, каждое ненулевое приращение будет получено после не более чем O(n) иттераций с нулевым приращением целевой функции.

Таким образом, особенности задачи (2), отличающие её от общей задачи линейного программирования, позволяют оценить вычислительную сложность применения симплекс-метода величиной duduv58.wmf, т.е. не больше duduv59.wmf.

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

Таким образом, в качестве оценки вычислительной сложности задачи (1) имеем:

duduv60.wmf.

Следовательно, вычислительная сложность предлагаемого способа решения задачи (1) «в худшем случае» не превышает duduv61.wmf, то есть полиномиальна.


Библиографическая ссылка

Дудов М.Х. МЕТОД ПОСТРОЕНИЯ МАКСИМАЛЬНОГО НЕЗАВИСИМОГО МНОЖЕСТВА НАИБОЛЬШЕЙ МОЩНОСТИ // Международный журнал прикладных и фундаментальных исследований. – 2016. – № 11-5. – С. 868-871;
URL: http://applied-research.ru/ru/article/view?id=10547 (дата обращения: 21.05.2019).

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

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