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

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

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

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

Следовательно, для графа, приведенного на рис. 3.1, множество является максимальным, а не является таковым. Множества и также являются максимальными независимыми множествами, и, значит, в данном графе больше одного независимого множества. Следует также отметить, что число элементов (вершин) в разных максимальных множествах, как следует из приведенного выше примера, не обязательно одинаковое.

Рис. 3.1.

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

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

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

Наибольшее из этих множеств имеет 4 элемента и, следовательно, Множество является наибольшим независимым множеством.

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

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

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