Внешняя устойчивость

Пусть G = (V, E) – ориентированный граф. Множество вершин D ⊂ V называется доминирующим, если в каждую вершину, не принадлежащую D, ведет некоторая дуга из вершины, находящейся в D. Иными словами, множество D доминирующее, если D∪G(D) = V. Минимальным доминирующим множеством называется такое доминирующее множество вершин D, никакое собственное подмножество которого не является доминирующим.

Доминирующее множество D является минимальным тогда и только тогда, когда для каждой вершины d ∈ D выполняется одно из следующих двух условий:

1) d∉G(D);

2) имеется дуга, идущая из вершины d в некоторую вершину d′∉D, причем никакая другая дуга с началом в одной из вершин множества D не ведет в d′.

В самом деле, если для вершины d ∈D выполняется одно из

этих двух условий, множество D\{d} не является доминирующим.

Множество вершин U ⊂ V называется внешне устойчивым в графе G, если U является доминирующим в графе G–1. Таким образом, множество вершин U внешне устойчиво, если любая вершина v, не входящая в U, служит началом хотя бы одной дуги, конец которой находится в U.

Пример.Пусть G – граф, изображенный на рис. 2. Любое доминирующее множество графа G должно содержать вершину 2, поскольку в нее не заходит ни одна дуга. Вершина 2 вместе с любой другой вершиной образует минимальное доминирующее множество.

2 3

1 4

Рис. 2

Любое внешне устойчивое множество содержит вершину 4. Эта вершина вместе с любой другой составляет минимальное внешне устойчивое множество вершин графа G.

Пусть G – ориентированный граф. Перенумеровав его вершины, будем считать, что вершинами графа G служат числа

1, 2, …, n. Пусть A = (aij) – матрица смежности графа G. Тогда равенство aij = 1 означает, что на графе G имеется дуга из вершины i в вершину j. Каждому подмножеству U множества вершин графа G сопоставим его характеристический вектор (ui) так, что ui = 1 тогда и только тогда, когда i ∈ U.

Множество вершин U внешне устойчиво тогда и только

тогда, когда для каждого i = 1, 2, …, n выполняется условие: если ui = 0, найдется j ∈ {1, 2,…, n} такое, что uj = 1 и aij = 1. Иными словами, множество вершин U внешне устойчиво,

если булево выражение

ui → (ai1u1 ∨ ai2u2 ∨ …∨ ainun) (1)

принимает значение 1 для всех i = 1, 2, …, n. В равносильной форме (1) можно переписать так:

ui ∨ (

∨

aij 1

u j ) .

Положим

f (U ) 

n

∧(ui ∨(

i 1

∨

aij 1

u j ))

(2)

Множество U внешне устойчиво в том и только том случае,

когда f(U) = 1. Таким образом, булева функция (2) является

характеристической функцией семейства внешне устойчивых множеств в совокупности всех подмножеств множества вершин графа G.

Представим функцию (2) в виде ДНФ. Каждый дизъюнктивный член соответствует внешне устойчивому множеству. Если в ДНФ входит элементарная конъюнкция uiuj…uk, то на множестве вершин U = {i, j, …, k} функция f принимает значение 1 и, значит, множество U внешне устойчиво. Раскрыв в (2) скобки и проведя все сокращения в соответствии с тождествами

xx = x, x ∨ x = x, x ∨ (xy) = x, x(x ∨ y) =x,

мы получим ДНФ, в которой дизъюнктивные члены соответствуют минимальным внешне устойчивым множествам.

Пример. Составим характеристическую функцию внешне устойчивых множеств (2) для графа G, представленного на рис.2:

f = (u1 ∨ u4)(u2 ∨ u1 ∨ u3∨ u5)(u3 ∨ u4)u4(u5 ∨ u1 ∨ u3∨ u4).

После раскрытия скобок и упрощений получаем:

f = u1u4 ∨ u2u4 ∨ u3u4 ∨ u4u5.

Следовательно, граф G обладает следующими минимальными внешне устойчивыми множествами вершин:

{1, 4}, {2, 4}, {3, 4}, {4, 5}.