21.2.1 Внешне устойчивые множества вершин графа

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

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

Мощность минимального ДМВ обозначается β(G) и называется числом внешней устойчивости графа.

Для нахождения ДМВ образуем матрицу

A’ = E v A,

где Е– единичная матрица,А– матрица смежности.

МатрицаЕвводится для учета изолированных вершин.

Найдем в матрице A’ минимальное множество строк, единицы в которых покрывают все столбцы. Множество вершин, соответствующее этому множеству строк, и есть ДМВ.

Пример.Для графа, показанного на рис. 21.1, получаем

A’ = E v A = v = .

Рисунок 21.1

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

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

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

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

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

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

Поскольку нам необходимо покрыть строками и столбец 1, и столбец 2, и столбец 3, и столбец 4, то для покрытия всех столбцов, заменив союз И символом конъюнкции, можно записать

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

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

v₁v₂v₃v₁v₃v₄.

Каждое из множеств {v₁,v₂,v₃} и {v₁,v₃,v₄} является доминирующим множеством вершин.

число внешней устойчивости данного графа β(G) равно 3.