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

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

Пример.Рассмотрим граф G, изображенный на рис. 2. Поскольку граф не содержит петель, любое множество, содержащее одну вершину, является внутренне устойчивым. Максимальными внутренне устойчивыми являются множества вершин {2, 4}, {1, 3} и {5}.

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

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

тогда, когда для любых i, j = 1, 2, …, n выполняется условие:

если ui = 1 и aij = 1, то uj = 0.

Иными словами, множество вершин U внутренне устойчиво,

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

(ui ∧ aij) → uj (3)

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

ui ∨ aij ∨ uj =1

для всех i, j = 1, 2, …, n. Положим

n

f (U) 

∧(u

∨a

∨u

). (4)

i, j 1 i ij j

Множество U внутренне устойчиво в том и только том случае, когда f(U) = 1. Таким образом, булева функция (4) является характеристической функцией семейства внутренне устойчивых множеств в совокупности всех подмножеств множества вершин графа G. Те множители (конъюнктивные члены), в которых ai,j = 0, обращаются в единицу, поэтому их можно опустить.

С учетом этого получаем:

f (U) 

n

∧(u

∨u ).

i j aij 1

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

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

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

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

f = (u1 ∨ u4)(u2 ∨ u1)(u2 ∨ u3)(u2 ∨ u5)∧

∧(u3 ∨ u4)(u5 ∨ u1)(u5 ∨ u3)(u5 ∨ u4).

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

f = u1u2u3u4 ∨ u1u3u5 ∨ u2u4u5.

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

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