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

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

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

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

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

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

табл. а)

табл. с)

b) Внешняя устойчивость. Для этого также удобно использовать списки отображений для каждой вершины x_i: h_xi= {x_a}ÍX и дополнить их списками несмежных  вершин: ùh_xi={x_b}ÍX (см. табл. а). Если для вершины x_i найдутся несмежные вершины x_j, x_k,.. x_tÎ{x_b}, то сформировать двухэлементные подмножества из всего множества вершин графа. Для каждой пары вершин найти списки отображений {h_xi,xj} и дополнить их списками несмежных  вершин {ùh_xi,xj}. Если хотя бы одна пара вершин ùh_xi,xj =Æ, то конец иначе сформировать трёхэлементные подмножества из всего множества вершин графа и вновь искать {h_xi,xj,xs} и {ùh_xi,xj,xs}. Если хотя бы для одного набора ùh_xi,xj,xs=Æ, то конец иначе формировать четырёхэлементные подмножества и т. д. Таких подмножеств T_i={x_i, x_j, x_k,...} может быть несколько. Наименьшее число вершин, смежных с оставшимися вершинами графа G=<X; r> есть число внешней устройчивости, т. е. f(G)=min{|T_i|}.