Дискретная математика: Учебное пособие. Часть 3 - Основы теории графов, страница 10

Поиск устойчивости графаG=<X; r>. Для этого удобно использовать списки отображений для каждой вершины xi: hxi= {xa}ÍX и дополнить их списками несмежных  вершин: ùhxi={xb}ÍX.

a)  Внутренняя устройчивость. Если для вершины xi найдутся несмежные вершины xj, xk,.. xtÎ{xb}, то сформировать двухэлементные множества из вершины xi и несмежных вершин {xb}. Для каждой пары вершин найти списки отображений: hxi,xj, hxi,xk, hxi,xt и дополнить их списками несмежных  вершин: ùhxi,xj, ùhxi,xk, ùhxi,xt. Если найдутся элементы xsÎX, принадлежащие ùhxi,xj, то сформировать трёхэлементные множества из вершин, принадлежащих {xi, xj}, {xi, xk} или {xi, xt} и xsÎùhxi,xj. Вновь найти {hxi,xj,xs} и {ùhxi,xj,xs}. Если найдутся элементы  xmÎùhxi,xj,xk, то сформировать четырёхэлементные множества и т. д. до тех пор пока не будет выполнено для всех подмножеств {xi,xj,xk..}..условие ùhxi,xj,xk,..=Æ. Подмножеств Si={{xi, xj, xk,...}} может быть несколько. Наибольшее число несмежных элементов графа G=<X; r> есть число внутренней устройчивости графа, т. е. j(G)=max{|Si|}.

          Пример: На рис.22 дан граф. Определить его внутреннюю устойчивость. Для графа сформируем списки смежных (hxi) и несмежных (ùhxi) вершин (табл. а)). Так как в таблице есть несмежные вершины, то сформируем подмножества попарно несмежных вершин {xi, xj} и списки смежныx с ними  (hxi,xj) и несмежныx (ùhxi,xj) вершин (см. табл. b)., Так как есть несмежные вершины, то сформируем трехэлементные множества несмежных вершин {xi, xj, xk} и списки смежныx с ними (hxi,xj,xk) и несмежныx (ùhxi,xj,xk) вершин (см. табл. c). В табл. с) имеем {ùhxi,xj,xk}=Æ.

Рис. 22 Устойчивость граф

Следовательно, подмножества, содержащие наибольшее число попарно несмежных вершин, есть S={{x1, x5, x6};{x2, x4,x7}}, т. е. число  внутренней устойчивости графа j(G)=maxi{|Si|}=3                          

табл. b)

{xi;xj}

h(xi;xj)

ùh(xi;xj)

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;x6

x4

x3;x7

x1;x2;x4;x5;x6

Æ

x4;x5

x1;x2;x3;x6;x7

Æ

x4;x7

x1;x3;x5;x6

x2

x5;x6

x2;x3;x4;x7

x1

табл. а)

xi

hXi

ùhXi

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

табл. с)

{xi;xj;xk}

h(xi;xj;xk)

ùh(xi;xj;xk)

x1;x5;x6

x2;x3;x4;x7

Æ

x2;x4;x7

x1;x3;x5;x6

Æ

b) Внешняя устойчивость. Для этого также удобно использовать списки отображений для каждой вершины xi: hxi= {xa}ÍX и дополнить их списками несмежных  вершин: ùhxi={xb}ÍX (см. табл. а). Если для вершины xi найдутся несмежные вершины xj, xk,.. xtÎ{xb}, то сформировать двухэлементные подмножества из всего множества вершин графа. Для каждой пары вершин найти списки отображений {hxi,xj} и дополнить их списками несмежных  вершин {ùhxi,xj}. Если хотя бы одна пара вершин ùhxi,xj =Æ, то конец иначе сформировать трёхэлементные подмножества из всего множества вершин графа и вновь искать {hxi,xj,xs} и {ùhxi,xj,xs}. Если хотя бы для одного набора ùhxi,xj,xs=Æ, то конец иначе формировать четырёхэлементные подмножества и т. д. Таких подмножеств Ti={xi, xj, xk,...} может быть несколько. Наименьшее число вершин, смежных с оставшимися вершинами графа G=<X; r> есть число внешней устройчивости, т. е. f(G)=min{|Ti|}.