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

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

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) будет равно количеству вершин, вошедших в максимальное независимое множество вершин.