Глава 3

НЕЗАВИСИМЫЕ И ДОМИНИРУЮЩИЕ

МНОЖЕСТВА. ЗАДАЧА О ПОКРЫВАЮЩИХ МНОЖЕСТВАХ

1. Введение

Пусть дан граф G = {X, Г). Довольно часто возникает задача поиска таких подмножеств множества вершин X графа G, которые обладают определенным, наперед заданным свойством. Например, какова максимально возможная мощность такого подмножества S X, для которого порожденный подграф {S) является полным? Или какова максимальная мощность подмножества S, такого, что граф {S)-вполне несвязный? Ответ на первый вопрос дает так называемое кликовое число графа G, а на второй - число независимости 1). Еще одна задача. Она состоит в нахождении минимально возможной мощности таких подмножеств S множества X, что любая вершина из X - S достижима из 5 с помощью путей единичной длины. Решение этой задачи дается так называемым числом доминирования графа G.

Эти числа и связанные с ними подмножества вершин описывают важные структурные свойства графа и имеют разнообразные непосредственные приложения при ведении проектного планирования исследовательских работ [3], в кластерном анализе и численных методах таксономии [36, 2], параллельных вычислениях на ЭВМ [17], при размещении предприятий обслуживания, а также источников и потребителей в энергосистемах [66, 56].

В настоящей главе приводятся алгоритмы определения указанных выше чисел и обсуждаются некоторые их приложения. Кроме того, рассматривается задача о наименьшем покрытии, которая является обобщением задачи о нахождении числа доминирования графа, и излагается некоторый метод ее решения. Последняя задача очень важна не только потому, что она имеет большое число прямых приложений, но и в связи с тем, что она часто возникает как подзадача в ряде разделов теории графов, которые затронуты в этой книге. В частности, большую роль она играет при вычислении хроматических чисел (гл. 4), нахождении центров графа (гл. 5) и паросочетаний (гл. 12).

) Применяются также п другие названия: вершинное число независимости и число внутренней устойчивости .- Прим. ред.

2. Независимые множества

Рассмотрим неориентированный граф G = {X, Г). Независимое множество вершин (известное также как внутренне устойчивое множество [11]) есть множество вершин графа G, такое, что любые две вершины в нем не смежны, т. е. никакая пара вершин не соединена ребром. Следовательно, любое множество 5 с= Z, которое удовлетворяет условию

S(]r{S) = 0, (3.1)

является независимым множеством вершин. Например, для графа, приведенного на рис. 3.1, множества вершин {7, Xg, х^}, {х^, xJ, {хт, Xg, х^, х^} - независимые. Когда не могут возникнуть недоразумения, эти множества будут называться просто независимыми множествами (вместо независимые множества вершин).

Независимое множество называется максимальным, когда нет другого независимого множества, в которое оно бы входило. Таким образом, множество S является максимальным независимым множеством, если оно удовлетворяет условию (3.1) и еще такому условию:

Н[]Г{Н)Ф0 VЯ=55. (3.2)

Следовательно, для графа, приведенного на рис. 3.1, множество {x-j, Xs, х^, Xs) является максимальным, а {х-;, Xg, х^} не является таковым. Множества {xi, х^, х-;) и {х;, х^ также являются максимальными независимыми множествами, и, значит, в данном графе больше одного независимого множества. Следует также отметить, что число элементов (вершин) в разных максимальных множествах, как следует из приведенного выше примера, не обязательно одинаковое.

Рис. 3.1.

Если Q является семейством всех независимых множеств графа G, то число

a[G] = maxl5 (З.З)

s£Q

называется числом независимости графа G, а множество S*, на котором этот максимум достигается, называется наибольшим независимым множеством.

Для графа, приведенного на рис. 3.1, семейство максимальных независимых множеств таково:

{х&, 7, Хз}, {xi, Хз, x}, {х^, 4, Xs}, {хе, х^},

{хе, Xs}, {x, Х5, Xi}, {xi, Xi}, {xs, x, Xg}.

Наибольшее из этих множеств имеет 4 элемента и, следовательно, [G] = 4. Множество {xg, Х7, Xg, х^} является наибольшим независимым множеством.

2.1. Пример: выбор проекта

Имеется п проектов, которые должны быть выполнены, и допустим, что для выполнения проекта Х; требуется некоторое подмножество Rj наличных ресурсов из множества {1, . . ., р}. Далее предположим, что каждый проект, задаваемый совокупностью средств, необходимых для его реализации, может быть выполнен за один и тот же промежуток времени. Построим граф G, каждая вершина которого соответствует некоторому проекту, а ребро (xj, Xj) - наличию общих средств обеспечения у проектов Xi и Xj, т. е. условию R fl 0- Максимальное независимое множество графа G представляет тогда максимальное множество проектов, которое можно выполнить одновременно за один и тот же промежуток времени.

В динамической системе происходит постоянное обновление проектов через определенный промежуток времени, так что каждый раз нужно заново повторять процедуру построения максимального независимого множества в соответствующем графе G. В практических ситуациях бывает весьма не просто выполнить множество проектов, соответствующих максимальному независимому множеству на данном отрезке времени, поскольку исполнение некоторых проектов может быть по каким-то причинам отложено. Тогда лучший способ действия состоит в присвоении каждому проекту (вершине) х; некоторого штрафа Pj, который увеличивается с ростом времени отсрочки в исполнении проекта, и в каждый расчетный момент времени надо выбирать из семейства максимальных независимых множеств такое множество, которое максимизирует некоторую функцию штрафов на вершинах, содержащихся в выбранном множестве.