Материал: Дискретная математика. учебное пособие. Собенина О.В

Шаг 1. G  данный граф. Для G найти все сильные компоненты.

Шаг 2. Построить конденсацию G* графа G.

Шаг 3. Определить антибазу В* конденсации G*, включив вВ* те вершины G*, полустепени исхода которых равны 0.

Шаг 4. Построить антибазу графа G из В*, взяв по одной вершине из сильных компонент, входящих вВ*. Останов.

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

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

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

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

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