3.4.1.7. Поиск устойчивости графа

Для поиска внутренней и внешней устройчивости графа удобно использовать списки смежных вершин для каждой вершины x_i, т. е. найти X={h(x_i)}X, и дополнить их списками несмежных вершин X_={h(x_i)}X.

Поиск внутренней устройчивости. Если существуют элементы, принедлежащие X_={h(x_i)}X, то сформировать из вершин x_iX и каждой вершины множества X_ двухэлементные множества:

S₁={{x_i, h(x_i)}}(XX).

Для каждой пары {x_i, h(x_i)} найти множество несмежных вершин

X_2={{h(x_i, q(x_i))}}X.

Если существуют элементы X_2, то сформировать из вершин, принадлежащих {x_i, h(x_i)}, и каждой вершины множества X_2 трехэлементные множества:

S₂={{x_i, h(x_i), h(x_i, h(x_i}))}(XXX).

Для каждой тройки попарно несмежных вершин {x_i, h(x_i) h(x_i, h(x_i))} найти множество несмежных вершин

X_3={{h(x_i, h(x_i), h(x_i, h(x_i)))}}X.

Если существуют элементы X_3, то сформировать из вершин, принадлежащих {x_i, h(x_i), h(x_i, h(x_i))}, и каждой вершины множества X_3 четырехэлементные множества:

S₃={{x_i, h(x_i), h(x_i, h(x_i)), h(x_i, h(x_i), h(x_i, h(x_i)))}}(XXXX).

Для каждой четверки попарно несмежных вершин {x_i, h(x_i) h(x_i, h(x_i)), h(x_i, h(x_i), h(x_i, h(x_i)))} найти множество несмежных вершин.

X_4={{h(x_i, h(x_i) h(x_i, h(x_i)), h(x_i, h(x_i), h(x_i, h(x_i))))}}X.

Процедуру продолжать до тех пор пока для всех подмножеств S_i={{x_i, h(x_i) h(x_i, h(x_i)), h(x_i, h(x_i), h(x_i, h(x_i)))....}} не будет выполнено_..условие:

h({x_i, h(x_i) h(x_i, h(x_i)), h(x_i, h(x_i), h(x_i, h(x_i)))...})={}

Таких подмножеств может быть несколько. Наибольшее число попарно несмежных вершин есть число внутренней устройчивости графа, т. е. (G)=max{|S_i|}.

Пример: на рис. 3.16 дан граф. Определить его внутреннюю устойчивость.

Д ля графа сформируем списки смежных h(x_i) и несмежных h(x_i) вершин (см. таблицу а). Так как в таблице есть несмежные вершины, то сформируем подмножества попарно несмежных вершин {x_i, h(x_i)} и найдем списки смежных h(x_i, h(x_i)) и несмежныx вершин - h(x_i, h(x_i)) (см. таблицу b). Поскольку для некоторых пар вершин {x_i, h(x_i)} есть несмежные вершины h(x_i,h(x_i)), то сформируем трехэлементные множества несмежных вершин {(x_i, h(x_i), (h(x_i, h(x_i)))} и найдем списки смежных h((x_i, h(x_i), (h(x_i, h(x_i)))) и несмежныx вершин h((x_i, h(x_i), (h(x_i, h(x_i)))) (см. табл. c).

В таблице для всех (x_i, h(x_i), (h(x_i, h(x_i))) значение h(x_i, h(x_i), h(x_i, h(x_i)))=.

Таблица а)
xi	h(xi)	h(xi)
x1	x2, x3, x4	x5, x6, x7
x2	x1, x3, x5	x4, x6, x7
x3	x1, x2, x4, x5, x6	x7
x4	x1, x3, x6	x2, x5, x7
x5	x2, x3, x7	x1, x4, x6
x6	x3, x4, x7	x1, x2,x5
x7	x5, x6		x1,x2, x3, x4

Таблица b)
(xi, h(xi)	h(xi, h(xi))	h(xi,h(xi))
x1, x5	x2, x3, x4, x7	x6
x1, x6	x2, x3, x4, x7	x5
x1, x7	x2, x3, x4, x5, x6	
x2, x4	x1, x3, x5, x6,	x7
x2, x6	x1, x3, x4, x5, x7	
x2, x7	x1, x3, x5, x7	x4
x3, x7	x1, x2, x4, x5, x6	
x4, x5	x1, x2, x3, x5, x6	
x4, x7	x1, x3, x5, x6	x2,
x5, x6	2, x3, x4, x7	x1

Таблица c)
{xi, h(xi), h(xi,h(xi))}	h(xi, h(xi), h(xi,h(xi)))	h(xi, h(xi), h(xi, h(xi)))
x1;x5;x6	x2;x3;x4;x7	
x2;x4;x7	x1;x3;x5;x6	

Следовательно, подмножества, содержащие наибольшее число попарно несмежных вершин, есть S={{x₁, x₅, x₆}; {x₂, x₄, x₇}}, т. е. число внутренней устойчивости графа (G)=max_i{|S_i|}=3.

Поиск внешней устойчивости. Для этого также удобно использовать списки смежных X_={h(x_i)}X и несмежных вершин X_={h(x_i)}X.

Если существуют элементы xX_, то из пары элементов x_i, x_jX при ij сформировать двухэлементные множества:

{x_i, x_j}(XX).

Для каждой пары {x_i, x_j) найти несмежные вершины:

X_2={h(x_i, x_j))}X.

Если существуют xX_2, то из трех элементов x_i, x_j, x_kX при ijk сформировать трехэлементные множества:

{x_i, x_j, x_k}(XXX).

Для каждой тройки {x_i, x_j, x_k} найти несмежных вершин:

X_3={h(x_i, x_j, x_k }X.

Процедуру продолжать до тех пор пока хотя бы для одного подмножества T_i={x_i, x_j, x_k...}(XXX...) не будет выполнено_. усло- вие:

h(x_i, x_j, x_k...)=.

Таких подмножеств T_i может быть несколько. Наименьшее число вершин множества Т_i есть число внешней устройчивости, т. е

(G)=min{|T_i|}.

Пример: На рис. 3.16 дан граф. Определить его внешнюю устойчивость.

Сформируем, как и для внутренней устойчивости, списки смежных h(x_i) и несмежных h(x_i) вершин (см. таблицу а).

Так как в таблице для всех значений x_i есть несмежные вершины, то сформируем двухэлементные подмножества множества X и найдем списки смежных h(x_i, x_j) и несмежных вершин h(x_i,, x_j) (см. таблицу b).

Таблица а)
xi	h(xi)	h(xi)
x1	x2, x3, x4	x5, x6, x7
x2	x1, x3, x5	x4, x6, x7
x3	x1, x2, x4, x5, x6	x7
x4	x1, x3, x6	x2, x5, x7
x5	x2, x3, x7	x1, x4, x6
x6	x3, x4, x7	x1, x2,x5
x7	x5, x6	x1,x2, x3, x4

Анализ таблицы пока- зывает, что существуют двух- элементные подмножества, смежные со всеми оставши- мися вершинами графа G. Следовательно, множества, содержащие наименьшее число вершин, смежных со всеми оставшимися вершинами графа, есть T={{x₁, x₇}; {x₂, x₆}; {x₃, x₅}; {x₃, x₆}; {x₃, x₇}; {x₄, x₅}}, т. е. число внешней устойчивости графа (G)=min_i{|T_i|}=2.

таблица b) продолжение таблицы b)
{xi, xj}	h{xi, xj}	h{xi, xj}		{xi, xj}	h{xi, xj}	h{xi, xj}
x1, x2	x3, x4, x5	x6, x7		x3, x4	x1, x2, x5, x6	x7
x1, x3	x2, x4, x5, x6	x7		x3, x5	x1, x2, x4, x6, x7	
x1, x4	x2, x3, x6	x5, x7		x3, x6	x1, x2, x4, x5, x7	
x1, x5	x2, x3, x4, x7	x6		x3, x7	x1, x2, x4, x5, x6	
x1, x6	x2, x3, x4, x7	X5		x4, x5	x1, x2, x3, x6, x7	
x1, x7	x2, x3, x4, x5, x6			x4, x6	x1, x4, x7	x2, x5
x2, x3	x1, x4, x5, x6	x7		x4, x7	x1, x3, x5, x6	x2
x2, x4	x1, x3, x5, x6	x7		x5, x6	x2, x3, x4, x7	x1
x2, x5	x1, x3, x7	x4, x6		x5, x7	x2, x3, x6	x1, x4
x2, x6	x1, x3, x4, x5, x7			x6, x7	x3, x4, x5	x1, x2
x2, x7	x1, x3, x5, x6	x4