Внешне устойчивое множество

Внешне устойчивым множеством Т вершин графа G называется такое множество его вершин, что для каждой вершины x_i, не входящей в множество Т, существует дуга, исходящая из некоторой вершины множества Т и заходящая в вершину x_i.

К задачам, которые решаются с помощью внешней устойчивости, относятся задачи о покрытиях: пусть имеется множество объектов. На этом множестве определить минимальное по мощности подмножество, которое держит под контролем все остальные элементы множества.

Задан граф. Определите все возможные внешне устойчивые подмножества вершин графа:

T ₁ = {X₁, X₄, X₆}

T₂ = {X₁, X₄}

T₃ = {X₃, X₅, X₆}

Внешне устойчивое множество вершин графа называется минимальным, если оно не содержит в качестве подмножеств другое внешне устойчивое множество.

Число внешней устойчивости графа

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

- число внешней устойчивости графа.

- это минимальная мощность минимальных внешне устойчивых подмножеств вершин графа.

Ядро графа

Ядром графа называется такое подмножество его вершин, которое одновременно и внутренне, и внешне устойчивое.

Метод Магу определения числа внутренней устойчивости графа

Формула определяет внутренне устойчивое множество вершин графа

– внутренне устойчивое множество

– отображение вершин, входящих в это множество

Если множество S внутренне устойчиво, то для произвольной пары вершин из этого множества <x_i, x_j>, если і ≠ j, отображение S не должно пересекаться с S. Действительно, если вершина x_i является отображением x_j, или есть дуга, которая выходит из x_i и входит в x_j, то одна из вершин, x_i или x_j, не должна принадлежать S:

(1)

Это – формулировка внутренней устойчивости вершин графа.

Для того, чтобы произвольные вершины x_k, x_p принадлежали внутренне устойчивому множеству вершин графа S, должно выполняться:

(2)

Возьмем конъюнкцию левых и правых частей выражений (1) и (2)

(3)

Геометрический смысл выражения (3):

							=
=

В выражении (3)перебираются всевозможные способы исключения вершин x_i, x_j, x_k, x_p из множества S так, чтобы оно было внутренне устойчивым.

Тогда можно составить следующий алгоритм:

Алгоритм поиска всех максимальных внутренне устойчивых множеств:

1. Для каждой пары (x_i, x_j) графа выписывается выражение (1).

2. Берется конъюнкция всех полученных выражений (для всех пар), раскрываются скобки, и производится поглощение ( ).

3. В полученной записи для каждой конъюнкции выписываются все вершины графа, которые в нее (конъюнкцию) не вошли. Они и образуют максимальные внутренне устойчивые множества вершин графа.

На практике выражение (1) используют в более формализованном виде:

Тогда выражение (1) будет иметь вид:

Д обавим конъюнкции слева и справа . Получим:

Для всех вершин графа

Пример. Дана матрица смежности графа.

		1	2	3	4	5
	1		1		1	1
	2			1
R=	3		1			1
	4
	5		1		1

Запишем выражение (1) для всех вершин графа (для всех пар):

v v ∙ =1  v =1

v v ∙ =1  v v 1=1  1≡1, т.е. эта строка нам далее не нужна

v v ∙ =1  v =1

v v ∙ =1  v =1

v v ∙ =1  v =1

v v ∙ =1  v v 1=1  1≡1, т.е. эта строка нам далее не нужна

v v ∙ =1  v =1

v v ∙ =1  v v 1=1  1≡1, т.е. эта строка нам далее не нужна

v v ∙ =1  v =1

v v ∙ =1  v =1

( v )( v )( v )( v )( v )( v )( v ) = 1

( v )( v )( v ) = 1

( v )( v v v ) =1

v v v v v =

Процесс определения внутренне устойчивых множеств можно формализовать – вместо будем пользоваться только индексом i