Независимые и доминирующие множества

Число доминирования, число независимости, кликовое число - эти числа и связанные с ними подмножества вершин описывают важные структурные свойства графа и имеют разнообразные непосредственные приложения при ведении проектного планирования исследовательских работ, в кластерном анализе, параллельных вычислениях на ЭВМ, при размещении предприятий обслуживания, а также источников и потребителей в энергосистемах. Ядро - множество вершин, которое является одновременно минимальным доминирующим и максимальным независимым, имеет важное значение в теории игр.

Множество вершин называется независимым (внутренне устойчивым множеством), если никакие две из них не смежны. Например, для графа, изображенного на рис. 4.27, независимыми являются множества вершин: {x₇, x₈, x₂}, {x₃, x₁}, {x₇, x₈, x₂, x₅}. Когда не могут возникнуть недоразумения, эти множества будут называться просто независимыми множествами (вместо независимые множества вершин).

Рис. 4.27

Независимое множество называется максимальным, если нет другого независимого множества, в которое оно бы входило. Для графа, изображенного на рис. 4.27, множество {x₇, x₈, x₂, x₅} является максимальным, а {x₇, x₈, x₂} таковым не является. Следует отметить, что число элементов (вершин) в разных максимальных множествах, как следует из приведенного примера, не обязательно одинаковое.

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

называется числом независимости графа G, а множество S^*, на котором этот максимум достигается, называется наибольшим независимым множеством. Для графа на рис. 4.27 семейство максимальных независимых множеств таково: {x₇, x₈, x₂, x₅}, {x₁, x₃, x₇}, {x₂, x₄, x₈}, {x₆, x₄}, {x₆, x₃},{x₁, x₅, x₇}, {x₁, x₄}, {x₃, x₇, x₈}.

Наибольшее из них множество имеет 4 элемента и, следовательно, . Множество {x₇, x₈, x₂, x₅} является наибольшим независимым множеством.

Пример. Пусть имеется n проектов, которые должны быть выполнены. Допустим, что для выполнения проекта x_i требуется некоторое подмножество R_i наличных ресурсов из множества{1, 2, … , p}. Предположим, что каждый проект, задаваемый совокупностью средств, необходимых для его реализации, может быть выполнен за один и тот же промежуток времени. Построим граф G, каждая вершина которого соответствует некоторому проекту, а ребро (x_i, x_j) – наличию общих средств у проектов x_i и x_j, т. е. условию . Максимальное независимое множество вершин графа G представляет тогда максимальное множество проектов, которое можно выполнить одновременно за один и тот же промежуток времени.

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

Множество ребер называется независимым, если никакие два из них не смежны. Наибольшее число ребер в независимом множестве ребер называется реберным числом независимости и обозначается β₁. Для полного графа с четным числом вершин β₁(К_2n)=n, для полного графа с нечетным числом вершин β₁(К_2n+1)=n–1. Независимое множество ребер называется также паросочетанием.

Независимость тесно связана с понятием доминирования.

Для графа G=(X,V) множество вершин D⊆Х называется доминирующим множеством (внешне устойчивым множеством), если , то есть для каждой вершины x_j∉D существует дуга, идущая из некоторой вершины x_i∈D в x_j.

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

1) Размещение телевизионных или радиопередающих станций на некоторой территории.

2) Размещение центров торговли обслуживающих некоторые районы.

Теорема 4.9.1. Независимое множество вершин является максимальным тогда и только тогда, когда оно является доминирующим.

4.9.1. Нахождение всех максимальных независимых множеств

Задача отыскания экстремальных независимых и покрывающих множеств возникает во многих практических случаях. Например, пусть есть множество процессов, использующих неразделяемые ресурсы. Соединим ребрами вершины, соответствующие процессам, которым требуется один и тот же ресурс. Тогда β₀ будет определять количество возможных параллельных процессов.

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

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

Используем систематический метод перебора Брона и Кэрбоша [2], который позволяет обходить указанные трудности. В этом методе не нужно запоминать генерируемые независимые множества для проверки их на максимальность путем сравнения с ранее сформированными множествами.

Введем необходимые обозначения обоснуем алгоритм нахождения всех максимальных независимых множеств.

В процессе поиска - на некотором этапе k - независимое множество вершин S_k расширяется путем добавления к нему подходящим образом выбранной вершины (чтобы получилось новое независимое множество S_k+1) на этапе k+1, и так поступают до тех пор, пока добавление вершин станет невозможным, а порожденное множество не станет максимально независимым множеством. Пусть Q_k будет на этапе k наибольшим множеством вершин, для которого S_k∩Q_k=Æ, то есть после добавления любой вершины из Q_k в S_k получится независимое множество S_k+1. В некоторый произвольный момент работы алгоритма множество Q_k состоит из вершин двух типов: подмножества Q_k^- тех вершин, которые уже использовались в процессе поиска для расширения множества S_k, и подмножества Q_k⁺ таких вершин, которые еще не использовались. Тогда дальнейшее ветвление в дереве поиска включает процедуру выбора вершины x_ikÎQ_k⁺, добавления ее к S_k

S_k+1 = S_kÈ{x_ik}

и порождения новых множеств:

Q_k^-₊₁ = Q_k^- \ Г(x_ik);

Q_k⁺₊₁ = Q_k⁺ \ (Г(x_ik) È {x_ik}).

Шаг возвращения алгоритма состоит в удалении вершины x_ik из S_k+1, чтобы вернуться к S_k, изъятии x_ik из старого множества Q_k⁺ и добавлении x_ik к старому множеству Q_k^- для формирования новых множеств Q_k^- и Q_k⁺.

Множество S_k является максимально независимым множеством только тогда, когда невозможно его дальнейшее расширение, то есть когда Q_k⁺=Æ. Если Q_k^-¹Æ, то текущее множество S_k было расширено на некотором предшествующем этапе работы алгоритма путем добавления вершины из Q_k^-, и поэтому не является максимальным независимым множеством. Таким образом, необходимым и достаточным условием того, что S_k - максимально независимое множество, является выполнение равенств:

Q_k⁺ = Q_k^- = Æ.

Если очередной этап работы алгоритма наступает тогда, когда существует некоторая вершина xÎQ_k^-, для которой Г(x)ÇQ_k⁺=Æ, то безразлично, какая из вершин, принадлежащих Q_k⁺, использовалась для расширения S_k, и это справедливо при любом числе дальнейших ветвлений. Вершина x не может быть удалена из Q_p^- на любом следующем шаге p > k. Таким образом, существование x, такого что

хÎQ_k^- и Г(x)ÇQ_k⁺ = Æ (4.5)

является достаточным для применения шага возвращения, потому что из S_k при всяком дальнейшем ветвлении уже не получится максимально независимое множество.

Если k=0, то возвращение выполнить невозможно, поэтому при k=0 осуществляется переход на прямой шаг.

Опишем алгоритм нахождения всех максимальных независимых множеств вершин графа.

Начальная установка.

Шаг 1.Пусть S₀ = Q₀^- = Æ, Q₀⁺= X, k=0.

Прямой шаг.

Шаг 2.Выбрать вершину x_ikÎQ_k⁺ и сформировать S_k+1, Q_k^-₊₁ и Q_k⁺₊₁, оставив Q_k^- и Q_k⁺ нетронутыми. Положить k=k+1.

Проверка.

Шаг 3.Если выполняется условие (4.5), то перейти к шагу 5 иначе к шагу 4.

Шаг 4. Если Q_k⁺=Q_k^- =Æ, то напечатать максимальное независимое множество S_k и перейти к шагу 5. Если Q_k⁺=Æ, а Q_k^-¹Æ, то перейти к шагу 5, иначе - к шагу 2.

Шаг возвращения.

Шаг 5.Положить k=k–1. Удалить x_ik из S_k+1, чтобы получить S_k. Исправить Q_k⁺ и Q_k^-, удалив вершину x_ik из Q_k⁺ и добавив ее к Q_k^-. Если k¹0, то перейти к шагу 3, иначе если Q₀⁺=Æ, то остановиться (к этому моменту будут напечатаны все максимальные независимые множества), иначе перейти к шагу 2.

Пример. Найти все максимальные независимые множества графа G.

Матрица смежности графа G:

1. Начальная установка:

S₀ = Ø; Q₀^- = Ø; Q₀⁺ = {x₁, x₂, x₃, x₄, x₅, x₆, x₇}; k=0.

2. Прямой шаг:

x₁; S₁ = {x₁}; Q₁^- = Ø; Q₁⁺ = {x₄, x₅, x₆, x₇}; k = 1.

3. Проверка.

Условие не выполняется, переходим к шагу 4 (→ 4).

4. Условие не выполняется → 2.

2. x₄; S₂ = {x₁, x₄}; Q₂^- = Ø; Q₂⁺ = {x₇}; k = 2.

3. Условие не выполняется → 4.

4. Условие не выполняется → 2.

2. x₇; S₃ = {x₁, x₄, x₇}; Q₃^- = Ø; Q₃⁺ = Ø; k = 3.

3. Условие не выполняется → 4.

4. S₃ = {x₁, x₄, x₇} - максимальное независимое множество → 5.

5. k = 2; S₂ = {x₁, x₄}; Q₂^- = {x₇}; Q₂⁺ = Ø → 3.

3. Условие выполняется → 5.

5. k = 1; S₁ = {x1}; Q₁^- = {x₄}; Q₁⁺ = {x₅, x₆, x₇} → 3.

3. Условие не выполняется → 4.

4. Условие не выполняется → 2.

2. x₅; S₂ = {x₁, x₅}; Q₂^- = Ø; Q₂⁺ = {x₆}; k = 2.

3. Условие не выполняется → 4.

4. Условие не выполняется → 2.

2. x₆; S₃ = {x₁, x₅, x₆}; Q₃^- = Ø; Q₃⁺ = Ø; k = 3.

3. Условие не выполняется → 4.

4. S₃ = {x₁, x₅, x₆} - максимальное независимое множество → 5.

5. k = 2; S₂ = {x₁, x₅}; Q₂^- = {x₆}; Q₂⁺ = Ø → 3.

3. Условие выполняется → 5.

5. k = 1; S₁ = {x₁}; Q₁^- = {x₄, x₅}; Q₁⁺ = {x₆, x₇} → 3.

3. Условие не выполняется → 4.

4. Условие не выполняется → 2.

2. x₆; S₂ = {x₁, x₆}; Q₂^- = {x₅}; Q₂⁺ = Ø; k = 2.

3. Условие выполняется → 5.

5. k = 1; S₁ = {x₁}; Q₁^- = {x₄, x₅, x₆}; Q₁⁺ = {x₇} → 3.

3. Условие выполняется → 5.

5. k = 0; S₀ = Ø; Q₀^- = {x₁}; Q₀⁺ = {x₂, x₃, x₄, x₅, x₆, x₇} → 2.

2. x₂; S₁ = {x₂}; Q₁^- = Ø; Q₁⁺ = {x₃, x₅, x₇}; k = 1.

3. Условие не выполняется → 4.

4. Условие не выполняется → 2.

2. x₃; S₂ = {x₂, x₃}; Q₂^- = Ø; Q₂⁺ = Ø; k = 2.

3. Условие не выполняется → 4.

4. S₂ = {x₂, x₃} — максимальное независимое множество → 5.

5. k = 1; S₁ = {x₂}; Q₁^- = {x₃}; Q₁⁺ = {x₅, x₇} → 3.

3. Условие не выполняется → 4.

4. Условие не выполняется → 2.

2. x₅; S₂ = {x_2, x₅}; Q₂^- = Ø; Q₂⁺ = Ø; k = 2.

3. Условие не выполняется → 4.

4. S₂ = {x₂, x₅} — максимальное независимое множество → 5.

5. k = 1; S₁ = {x₂}; Q₁^- = {x₃, x₅}; Q₁⁺ = {x₇} → 3.

3. Условие не выполняется → 4.

4. Условие не выполняется → 2.

2. x₇; S₂ = {x₂, x₇}; Q₂^- = Ø; Q₂⁺ = Ø; k = 2.

3. Условие не выполняется → 4.

4. S₂ = {x₂, x₇} — максимальное независимое множество → 5.

5. k = 1; S₁ = {x₂}; Q₁^- = {x₃, x₅, x₇}; Q₁⁺ = Ø → 3.

3. Условие выполняется → 5.

5. k = 0; S₀ = Ø; Q₀^- = {x₁, x₂}; Q₀⁺ = {x₃, x₄, x₅, x₆, x₇} → 3.

3. Условие не выполняется → 4.

4. Условие не выполняется → 2.

2. x₃; S₁ = {x₃}; Q₁^- = {x₂}; Q₁⁺ = {x₄, x₆}; k = 1.

3. Условие не выполняется → 4.

4. Условие не выполняется → 2.

2. x₄; S₂ = {x₃, x₄}; Q₂^- = Ø; Q₂⁺ = Ø; k = 2.

3. Условие не выполняется → 4.

4. S₂ = {x₃, x₄} — максимальное независимое множество → 5.

5. k = 1; S₁ = {x₃}; Q₁^- = {x₂, x₄}; Q₁⁺ = {x₆} → 3.

3. Условие не выполняется → 4.

4. Условие не выполняется → 2.

2. x₆; S₂ = {x₃, x₆}; Q₂^- = Ø; Q₂⁺ = Ø; k = 2.

3. Условие не выполняется → 4.

4. S₂ = {x₃, x₆} — максимальное независимое множество → 5.

5. k = 1; S₁ = {x₃}; Q₁^- = {x₂, x₄, x₆}; Q₁⁺ = Ø → 3.

3. Условие выполняется → 5.

5. k = 0; S₀ = Ø; Q₀^- = {x₁, x₂, x₃}; Q₀⁺ = {x₄, x₅, x₆, x₇} → 2.

2. x₄; S₁ = {x₄}; Q₁^- = {x₁, x₃}; Q₁⁺ = {x₇}; k = 1.

3. Условие выполняется → 5.

5. k = 0; S₀ = Ø; Q₀^- = {x₁, x₂, x₃, x₄}; Q₀⁺ = {x₅, x₆, x₇} → 2.

2. x₅; S₁ = {x₅}; Q₁^- = {x₁, x₂}; Q₁⁺ = {x₆}; k = 1.

3. Условие выполняется → 5.

5. k = 0; S₀ = Ø; Q₀^- = {x₁, x₂, x₃, x₄, x₅}; Q₀⁺ = {x₆, x₇} → 2.

2. x₆; S₁ = {x₆}; Q₁^- = {x₁, x₃, x₅}; Q₁⁺ = Ø; k = 1.

3. Условие выполняется → 5.

5. k = 0; S₀ = Ø; Q₀^- = {x₁, x₂, x₃, x₄, x₅, x₆}; Q₀⁺ = {x₇} → 2.

2. x₇; S₁ = {x₇}; Q₁^- = {x₁, x₂, x₄}; Q₁⁺ = Ø; k = 1.

3. Условие выполняется → 5.

5. k = 0; S₀ = Ø; Q₀^- = {x₁, x₂, x₃, x₄, x₅, x₆, x₇}; Q₀⁺ = Ø → останов.

Таким образом, данный граф имеет семь максимальных независимых множеств:

S₁ = {x₁, x₄, x₇}; S₂ = {x₁, x₅, x₆}; S₃ = {x₂, x₃}; S₄ = {x₂, x₅}; S₅ = {x₂, x₇}; S₆ = {x₃, x₄}; S₇ = {x₃, x₆}.

Ядро - множество, которое является одновременно минимальным доминирующим и максимальным независимым.

Утверждение 4.9.1. Конечный граф без петель, не содержащий контуров нечетной длины, обладает ядром.

Понятие, противоположное максимальному независимому множеству, есть максимальный полный подграф. Максимальный полный подграф графа G называется кликой графа. Следовательно, в противоположность максимальному независимому множеству, в котором не могут встретиться две смежные вершины, в клике все вершины попарно смежны. Совершенно очевидно, что максимальное независимое множество графа G соответствует клике графа и наоборот, где – дополнение графа G.

Кликовое число – максимальное число вершин в кликах данного графа.

Утверждение. 4.9.2. Максимальное независимое множество графа G соответствует клике графа `G и наоборот.