1.3. Определение чисел β0(g), β1(g).

Мидифицированной матрицей смежности (G) графа G называется дизъюнкция матриц смежности S(G) и единичной диагональной матрицы {1,1…,1}:

(G) = S(G) v {1,1…,1}.

Определение вершинного числа внешней устойчивости β₀(G) сводится к построению модифицированной смежности матрицы смежности и выделению покрытия с минимальным числом элементов. Другими словами, β₀(G) равно числу элементов в минимальном покрытии.

При выделении минимального покрытия могут быть использованы следующие законы операций дизъюнкции и конъюнкции:

1. идемпотентности

а + а = а, а . а = а;

2. коммутативности

а + в = в + а, а . в = в . а;

3. ассоциативности

а + (в + с) = (а + в) + с, а . (вс) = (ав) . с;

4. дистрибутивности

а . (в + с) = а . в + а . с, а + в . с = (а + в) . (а + с);

5. поглощения

а + а . в = а, а . (а + в) = а.

Здесь под знаком сложения понимается операция дизъюнкции, а под знаком умножения – операция конъюнкции.

Пример 7. Определить β₀(G) графа G (рис. 1.9). выписать все минимальные покрытия, соответствующие значению β₀(G).

a

b c

f d

e

G

Рис. 1.9

а b

c d

e

G

Рис. 1.10

Находим модифицированную матрицу смежности (G) заданного графа G:

а b c d e f

0 1 1 0 0 0 a 1 0 0 0 0 0 1 1 1 0 0 0

1 0 1 0 1 1 b 0 1 0 0 0 0 1 1 1 0 1 1

= SV{1,1,…1}= 1 1 0 1 1 0 c V 0 0 1 0 0 0 = 1 1 1 1 1 0

0 0 1 0 1 0 d 0 0 0 1 0 0 0 0 1 1 1 0

0 1 1 1 0 1 e 0 0 0 0 1 0 0 1 1 1 1 1

0 1 0 0 1 0 f 0 0 0 0 0 1 0 1 0 0 1 1

Покрываем строки столбцами или столбцы строками модифицированной матрицы смежности, что равнозначно в силу ее симметричности относительно главной диагонали. Рассмотрим покрытие столбцов строками. Применим алгоритм Петрика, который заключается в следующем: для каждого столбца матрицы определяется дизъюнкция строк, покрывающих этот столбец. Далее записывается конъюнкция найденных дизъюнкций (аналогично при покрытии строк столбцами). Используя алгоритм Петрика и законы операций дизъюнкции и конъюнкции, получим:

( a + b + c) (a + b + c + e + f) (a + b + c + d + e) (c + d + e) ( b + c + d + e + f) (b + e + f) =

1 2 3 4 5 6

1, 2, 3: а + b + c = A, A(A+B)=A

= 2: e + f = B, = A(A + B) (A + C) E (E + F)(e + F) = A(A+C)=A =

3: d + e = C, E(E+F)=E

4,5 : c + d + e = E.

5,6: b + f = F

1: c + d = A

= A . E . (e+F)= (a + b + c) (c + d + e) (e + b + f) = 2: f + b = B =(a + b + c).(е+А). (е+В)=

1. 2

= |(е+А)(е+В)=е+А.В | = (a + b + c).(е+(с+d)(f+b)) = (a + b + c).(e + cf+cb+df+db) = ae+acf+

bbc=bc, bbd=bd,

+acb+ adf+adb+be+bcf+bbc+ bdf+bbd+ce+ccf+ccb+cdf+cdb= ccb=cb, ccf=cf, =

cb+bc=bc,

= ae + be + ce + adf + bc + abc + bcf + dcd + cf + cfa + cfd + bd + bdf + bda =

dc = A :A +Aa=A, A + Af=A, A + Ad = A;

= cf = B:B+Ba=B, B+BD=B; = ae +be + ce + adf + bc + cf + bd.

bd=C:C+Cf=C, C+Ca=C.

Минимальными покрытиями являются покрытия, содержащие по два элемента. Любое из минимальных покрытий является решением, т.е.

β₀(G) = |{a,e}| = |{b,e}|= |{c,e}| = |{b,c}|= |{c,f}| = |{b,d}| = 2.

Для проверки рассмотрим, например, вершины а и е: вершина а в графе G покрывает вершины в и с, вершина е покрывает вершины f, b, c, d. Так как вершина а и е покрывают сами себя, то все вершины заданного графа покрыты двумя вершинами а и е. Аналогично можно проверить и другие минимальные покрытия.

Если по условию задачи не требуется определять все минимальные покрытия, то решение можно упростить: достаточно в модифицированной матрице смежности найти минимальное число строк, покрывающих все столбцы (или минимальное число столбцов, покрывающих все строки матрицы). в нашем примере такими строками являются , например, строки в и с. Значит

β₀(G) = |{в,с}| = 2.

Проверка вершин в и с на покрытие всех вершин графа G подтверждает правильность такого решения: вершина в покрывает себя вершины а, с, е, f, а вершина с покрывает себя и вершины a,b,e,d, т.е. все вершины заданного графа G покрыты. ■

Аналогично определяется β₁(G).

Модифицированной матрицей смежности ребер _p(G) графа G называется

_p = S_p(G) v {1,1,…1},

где S_p(G) – матрица смежности ребер, {1,1,…1} – единичная диагональная матрица.

Пример 8. Определить β₁(G) графа G (рис. 1.10). Выписать все минимальные покрытия, соответствующие значению β₁(G).

Строим модифицированную матрицу смежности _p(G) заданного графа G:

а b c d e

0 1 1 0 0 a 1 0 0 0 0 1 1 1 0 0

1 0 0 1 0 b 0 1 0 0 0 1 1 0 1 0

=S _pV{1,1,1} = 1 0 0 0 1 c V 0 0 1 0 0 = 1 0 1 0 1

0 1 0 0 1 d 0 0 0 1 0 0 1 0 1 1

0 0 1 1 0 e 0 0 0 0 1 0 0 1 1 1

Покрываем строки столбцами. Используя алгоритм Петрика и законы операций дизъюнкции и конъюнкции, получим:

1, 2: а + b = A,

( a + b + c) (a + b + d) (a + c + e) (b + d + e) (c + d + e) = 3,4: d + e = B, =

1 2 3 4

(A+c)(A+d)=A+cd,

= (A+c)(A+d)(a+c+e)(B+b)(B+c)= (B+b)(B+c)=B+bc = (a + b + cd)(a+c+e)(d+e+bc)=

1 2

1:b+cd=A,

= 2:c+e=B = (a + A) (a + B)(d+e+bc) = (a+AB)(d+e+bc)= (a+(b+cd)(c+e))(d+e+bc)=

ccd=cd,

= (a+bc+be+ccd+cde)(d+e+bc)= cd=A = (a + bc + be +A + Ae)(d + e + bc = |A +AE=A| =

a + be + cd = A,

= (a + bc + be + cd)(d + e + bc) = d + e = B = (bc + A) (dc + B)= bc + AB = bc +

bee = be, be + bed=be;

+ad+ ae +bed + bee + cdd+ cde = cdd = cd. cd + cde = cd = dc + ad + ae + be + cd.

Все покрытия имеют одинаковую мощность, значит,

β₁(G) = |{b,c}| = |{a,d}|= |{a,e}| = |{b,e}|= |{c,d}| = 2.

Любое из этих покрытий является решением.

Если нет необходимости определять все минимальные покрытия, то решение можно найти сразу из матрицы _p(G). Одой строки, которая покрывала бы все столбцы матрицы, нет. Две строки, которые покрывали бы все столбцы, имеются. Например, строки b и с.

Значит,

β₁(G) = |{b,c}| = 2.

Это минимальное число ребер, покрывающих все ребра заданного графа G:

ребро b покрывает себя и ребра a и d, ребро с покрывает себя и ребра а и е. ■

1.4. Определение чисел β₀⁺(G), β₀^-(G).

В случае ориентированного графа G кроме вершинного числа внешней устойчивости β₀(G) различают положительное β₀⁺(G) и отрицательное β₀^-(G) вершинные числа внешней устойчивости.

Положительным вершинным числом внешней устойчивости β₀⁺(G)

графа G = < V, Г > называется минимальная мощность множества вершин V⁺= {v_i⁺} такого, что

{v_i⁺} {Гv_i⁺} = V, (1.2)

и при удалении хотя бы одной вершины из V⁺ указанное соотношение не выполняется.

Это число определяет минимальное количество вершин, из которых «наблюдается» (достижимы за один шаг) все вершины графа.

Отрицательным вершинным числом внешней устойчивости β₀^-(G)

графа G = < V, Г > называется минимальная мощность множества вершин

V^-= {v_i^-} такого, что

{v_i^-} {Г ^-1v_i^-} = V, (1.3)

и при удалении хотя бы одной вершины из множества V^- указанное соотношение не выполняется.

Это число равно минимальному количеству вершин, которые «наблюдаются» всеми вершинами графа.

Пример 9. Найти V⁺, V^-, Гv_i⁺, Гv_i^- в ориентированном графе G (рис. 1.11).

v₁

v₄ v₂

v₃

G

Рис. 1.10

Заданный граф G имеет множество вершин V= {v_1, v_2, v_3, v₄}. Определим V⁺.

Множество вершин V⁺ состоит из вершин графа G, из которых исходят дуги, т.е. состоит из вершин, из которых «наблюдаются» другие вершины графа. Значит

V⁺= {v_1, v_2, v₄}.

Найдем Гv_i⁺ для этих вершин.

Гv₁= { v_2, v₄}, т.е. окрестность Гv₁ состоит из вершин, в которые входят дуги из вершины v₁. Аналогично

Гv₂= { v₃}, Гv₄= { v₃}.

Проверим соотношение (1.2):

{v_1, v_2, v_3, } { v_2, v₄} { v₃ } { v₃ } = {v_1, v_2, v_3, v₄} = V.

Определим V^-.

Множество вершин V^-состоит из вершин графа G, в которые входят дуги, т.е. состоит из вершин, которые «наблюдаются» из других вершин графа. Значит,

V^-= { v_2, v_3, v₄}.

Найдем Г ^-1v_i^- для этих вершин.

Г ^-1v₂ = {v₁}, т.е. окрестность Г ^-1v₂ состоит из вершины, из которой исходит дуга в вершину v₂.

Аналогично Г ^-1v₃ = {v_2, v₄}, Г ^-1v₄ = { v₁}.

Проверим соотношение (1.3):

{v_2, v_3, v_4, } { v₁} { v_2, v₄ } { v₁ } = {v_1, v_2, v_3, v₄} = V■

Число β₀⁺(G) вычисляется как минимальная мощность покрытия столбцов строками, а число β₀^-(G) – как минимальная мощность покрытия строк столбцами в модифицированной матрице смежности S(G) графа G.

а

f b

e c

d

G

Рис. 1.12

Пример 10. Для ориентированного графа G (рис. 1.12) определить числа β₀⁺(G) и β₀^-(G). Выписать все минимальные покрытия, соответствующие значениям β₀⁺(G) и β₀^-(G).

Находим модифицированную матрицу смежности (G) заданного графа G:

а b c d e f

0 0 0 0 0 1 a 1 0 0 0 0 0 1 0 0 0 0 1

0 0 0 0 0 1 b 0 1 0 0 0 0 0 1 0 0 0 1

= SV{1,1,…1} = 1 1 0 1 1 0 c V 0 0 1 0 0 0 = 1 1 1 1 1 0

0 1 0 0 0 0 d 0 0 0 1 0 0 0 1 0 1 0 0

0 0 0 0 0 1 e 0 0 0 0 1 0 0 0 0 0 1 1

0 0 0 1 0 0 f 0 0 0 0 0 1 0 0 0 1 0 1

Найдем β₀⁺(G). Для этого рассмотрим покрытие столбцов строками в S. Используя алгоритм Петрика и законы операций дизъюнкции и конъюнкции, получим:

(a + c) (b + c + d) c (c ++ d + f) (c + e) (a + b + e + f)=

c(c + d + f)= c, c(c + e) = c,

= c(c + b + d)=c, c(c + a) = c = c (a + b + e + f) = ca + cb + ce + cf.

Следовательно,

β₀(G) = |{a,c}| = |{b,c}|= |{c,e}| = |{c,f}| = 2.

Проверим, например, вершины а и с. Из вершины а «наблюдается» вершина f, из вершины с «наблюдаются» вершины a,b,d,e . То есть из вершин а и с «наблюдаются» все вершины графа G.

Найдем β₀^-(G). Для этого рассмотрим покрытие строк столбцами в . Используя алгоритм Петрика и законы операций дизъюнкции и конъюнкции, получим:

(a + f) (b + f) c (a + b + c + d + e) (b + d) ( e + f) (d + f) =

(b + d) ((b + d) + (a + c + e)) = b + d,

(f + a) (f + b) = f + ab,

= (f + ab)(f + e) = f + abe, =(b + d)(f + abde) = fb+babde+df+

(f + abe)(f + d) = f + abde

+ dabde= bf+df+abde+abde= bf+df+abde.

Следовательно, β₀(G) = |{b,f}| = |{d,f}| = 2.

Проверим, например, вершины b,f. Вершина f «наблюдается» из вершин a, b, e; вершина b «наблюдается» всеми вершинами графа G. ■