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

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

Множество вершин называется независимым (внутренне устойчивым множеством), если никакие две из них не смежны. Например, для графа, изображенного на рис. 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:

А =		x1	x2	x3	x4	x5	x6	x7
x1
x2
x3
x4
x5
x6
x7

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 ₁ = { x 1}; 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 и наоборот.

Дата добавления: 2014-12-27