2015-05-14
3075
Множество вершин, такое, что вершины графа G принадлежат этому множеству или смежны хотя бы с одной вершиной этого множества, называется внешне устойчивым или доминирующим множеством вершин (ДМВ).
Если это множество не содержит подмножеств с таким же свойством, то оно минимально.
Мощность минимального ДМВ обозначается β(G) и называется числом внешней устойчивости графа.
Для нахождения ДМВ образуем матрицу
A ’ = E v A,
где Е – единичная матрица, А – матрица смежности.
Матрица Е вводится для учета изолированных вершин.
Найдем в матрице A ’ минимальное множество строк, единицы в которых покрывают все столбцы. Множество вершин, соответствующее этому множеству строк, и есть ДМВ.
Для графа, показанного на рис. 2.33 получаем
A ’ = E v A = 
v 
= 
.
Рисунок 2.33
Для нахождения всех внешне устойчивых множеств вершин графа поступим следующим образом.
Анализируя матрицу A ’, замечаем, что
- для покрытия столбца 1 нужна строка 1 (v 1),
- для покрытия столбца 2 нужна строка 1 (v 1), или строка 2 (v 2), или строка 3 (v 3), что можно записать так (v 1 
v 2 v 3),
|
|
|
- для покрытия столбца 3 нужна строка 3 (v 3),
- для покрытия столбца 4 нужна строка 2 (v 2) или строка 4 (v 4), что можно записать (v 2 v 4).
Поскольку нам необходимо покрыть строками и столбец 1, и столбец 2, и столбец 3, и столбец 4, то для покрытия всех столбцов, заменив союз И символом конъюнкции, можно записать
v 1 
(v 1 v 2 v 3) v 3 (v 2 v 4).
Раскрыв скобки и проведя преобразования, получаем
v 1 v 2 v 3 v 1 v 3 v 4.
Каждое из множеств { v 1, v 2, v 3} и { v 1, v 3, v 4} является доминирующим множеством вершин.
число внешней устойчивости данного графа β(G) равно 3.
