Алгоритм определения внешне устойчивых множеств вершин

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

1) Получить матрицу A ’ = E v A.

2) Обозначить вершины графа логическими переменными, например, x ₁, x ₂, x ₃,…, x_n, где x_i = 1, если вершина принадлежит какому либо внешне устойчивому множеству, и x_i = 0 в противном случае.

3) Для каждой вершины графа, используя матрицу A ’, записать выражение

где – x_i вершина, соответствующая выбранной строке,

x_k, x_l,…, x_q – вершины, смежные ей.

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

4) Сформировать логическое выражение в виде произведения полученных сумм

П = C_i C_j … C_k.

5) Провести преобразования логического выражения П для получения минимальной дизъюнктивной нормальной формы (МДНФ).

6) Каждая конъюнкция полученной МДНФ будет являться доминирующим множеством вершин графа, а количество переменных в минимальной из них будет числом внешней устойчивости данного графа β(G). В совокупности получим семейство из всех внешне устойчивых множеств графа.

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

Для нахождения вершинной базы необходимо сформировать матрицу

A” = E v A v…v A ^{n -1},

где Е – единичная матрица размера n n, А,…, A ^{n –1} – степени матрицы смежности графа, от 1 до n –1.

Затем надо найти в матрице A” множество строк, единицы в которых покрывают все столбцы, – множество вершин, соответствующее этому множеству строк, и есть вершинная база.

В качестве примера найдем вершинную базу графа, показанного на рис. 2.33

Составим матрицу смежности графа

A = .

Определим необходимые степени матрицы смежности

A²= * = ,

A³ = * = .

Определим матрицу A”

A”= E v A v A² v A³ = .

Для определения вершинной базы необходимо найти вершины, строки которых покрывают все столбцы матрицы A ”.

Анализируя матрицу A ”, замечаем, что

- для покрытия столбца 1 нужна строка 1 (v ₁),

- для покрытия столбца 2 нужна строка 1 (v ₁), или строка 2 (v ₂), или строка 3 (v ₃), что можно записать так (v ₁ v ₂ v ₃),

- для покрытия столбца 3 нужна строка 3 (v ₃),

- для покрытия столбца 4 нужна или строка 1 (v ₁), или строка 2 (v ₂), или строка 3 (v ₃), или строка 4 (v ₄), что можно записать так

(v ₁ v ₂ v ₃ v ₄).

Поскольку надо покрыть единицами и первый столбец, и второй столбец, и третий столбец, и четвертый столбец, то, заменив союз И символом конъюнкции, запишем

v ₁ (v ₁ v ₂ v ₃) v ₃ (v ₁ v ₂ v ₃ v ₄).

Раскрыв скобки и проведя преобразования, получаем

v ₁ v ₃.

Множество вершин { v ₁, v ₃} и есть вершинная база графа.

Множество вершин графа, среди которых нет смежных, называется независимым множеством вершин (НМВ) или внутренне устойчивым множеством вершин.

Если такое множество не является подмножеством другого множества с таким свойством, то оно максимально.

Мощность максимального независимого множества вершин (МНМВ) α(G) – называется числом внутренней устойчивости графа.

С помощью приведенного ниже алгоритма можно выделить семейство всех независимых множеств вершин произвольного графа.

Алгоритм определения внутренне устойчивых множеств вершин:

1) Составить матрицу смежности графа.

2) Обозначить вершины графа логическими переменными, например, x ₁, x ₂, x ₃,…, x_n, где x_i = 0, если вершина принадлежит какому либо внутренне устойчивому множеству, и x_i = 1 в противном случае.

Обратите внимание на отличие значений x_i от значений этой переменной в алгоритме определения внешне устойчивых множеств вершин графа.

3) В матрице смежности выбрать строку с максимальным числом ненулевых элементов. Если таких строк несколько, то берется любая из них.

4) Для выбранной строки записывается выражение

где x_i – вершина, соответствующая выбранной строке, x_k, x_l,…, x_q – вершины, смежные ей.

Трактовать это выражение можно так – во внутренне устойчивое множество вершин графа не должна входить вершина x_i или ни одна из вершин, смежных с ней.

5) После этого в строке и столбце матрицы смежности с индексом i единицы заменить нулями (строку и столбец с индексом i можно удалить).

6) В полученной матрице смежности снова выбрать строку с наибольшим числом ненулевых элементов (например, строку j) и записать выражение

7) Строка и столбец с индексом j обнуляются.

8) Процесс повторяется, пока все строки матрицы смежности не станут пустыми (одни нули).

В строках изолированных и тупиковых вершин первоначальной матрицы смежности стоят только 0, поэтому для них не будут составлены выражения C_i. Изолированные вершины обязательно войдут в любое из внутренне устойчивых множеств и будут учтены в п. 10 алгоритма. поэтому их можно сразу исключить из матрицы смежности, упростив тем самым решение задачи. Тупиковые вершины будут учтены в выражениях для вершин, смежных с ними.

9) Из полученных выражений C_i, C_j,, C_k составить произведение

П = C_i C_j … C_k,

в котором надо раскрыть скобки и провести минимизацию.

10) После минимизации для каждой конъюнкции найти не вошедшие в нее вершины графа, которые и образуют независимое множество.

В совокупности получим семейство из всех независимых множеств.

11) Число внутренней устойчивости графа α(G) будет равно количеству вершин, вошедших в максимальное независимое множество вершин.