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

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

Сформируем, как и для внутренней устойчивости, списки смежных (h_xi) и несмежных (ùh_xi) вершин (см. табл. a) предыдущего примера).

Так как в табл. a) есть несмежные вершины, то сформируем подмножества всех вершин графа {x_i, x_j}ÍX и списки смежныx (h_xi,xj) и несмежныx (ùh_xi,xj) им вершин (см. табл. d). Анализ табл. d) показывает, что существуют двухэлементные подмножества, смежные со всеми оставшимися вершинами графа G.  

табл. d)                                                продолжение табл. d)

{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

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

3.3.2. Бинарные операции.

При исполнении операций над двумя графами G₁=<X₁; r₁> и G₂=<X₂; r₂> следует обратить внимание на наличие общих элементов для X₁ и X₂ и/или r₁ и r₂. Этот анализ позволяет выделить три конструктивных объекта:

1.  вершины и рёбра (дуги) не имеют общих элементов, т.е. (X₁ÇX₂)=Æ и (r₁Çr₂)=Æ;

2.  вершины имеют общие элементы, а рёбра (дуги) - нет, т.е. (X₁ÇX₂)¹Æ и (r₁Çr₂)=Æ;

3.  вершины и рёбра (дуги) имеют общие элементы, т.е. (X₁ÇX₂)¹Æ и (r₁Çr₂)¹Æ.

Исполнение операций для каждого из них порождает принципиально иной объект.

         Объединение графов G₁=<X₁; r₁> и G₂=<X₂; r₂> есть граф G=G₁ÈG₂), для которого X=(X₁ÈX₂) и r=(r₁Èr₂).  рис. 23 дан результат этой операции. Для вычисления смежности вер- шин формируемого графа сле­дует использо­вать матрицы смежности по формуле: r_i,j=r_i,j⁽¹⁾Ú r_i,j⁽²⁾. Матрица смежности для графа G=<X; r> будет иметь число строк и столбцов равным |X|=|X₁|+|X₂|.

          Пересечение графовG₁=<X₁; r₁> и G₂=<X₂; r₂> есть граф G=(G₁ÇG₂), для которого X=(X₁ÇX₂) и r=(r₁Çr₂). На рис. 24 дан результат исполнения этой операции. Матрица смежности графа имеет число строк и столбцов равным |X|=|X₁ÇX₂|. Для вычисления смежности вершин формируемого графа следует воспользоваться формулой: r_i,j=r_i,j⁽¹⁾× r_i,j⁽²⁾.

          Композиция графовG₁=<X₁;r₁> и G₂=<X₂;r₂>  есть граф G=<X, r>=(G_1°G₂), для которого XÍ(X₁ÈX₂), а r_i,jÎr существует тогда и только тогда, когда есть хотя бы одна вершина x_k, принадлежащая множествам X₁ и X₂, что обеспечивает маршрут через вершину x_k , с началом в x_i ⁽¹⁾ÎX₁ и концом в x_j ⁽²⁾ÎX₂. На рис. 25 дан результат исполнения этой операции. Для вычисления смежности вершин формируемого графа следует воспользоваться формулой r_i,j= _k=1Úⁿ(r_i,k⁽¹⁾×r_k,j⁽²⁾).