Алгоритм выделения пустых подграфов.

1. Сопоставляем корню синтезируемого дерева заданный граф G.

2. Фиксируем в графе вершину v₀ с минимальной степенью, сопоставив ее концу дуги, исходящей из корня. Строим дуги, исходящие из корня, число которых равно

|Гv₀|, и конец каждой из них взаимно однозначно сопоставляем вершине окрестности G (v₀).

3. Каждый конец v_α построенных дуг взвешиваем неокрестностью (v_α) вершины графа, сопоставленного рассматриваемому корню.

4. Считаем конец v_α построенного яруса корнем нового дерева.

5. Устанавливаем, взвешена ли вершина v_α символом Ø. Если «нет», то переходим к п.2, если «да» то к п.6.

6. Пути между концами дуг, исходящих из корня синтезированного дерева, и висячими вершинами однозначно определяют пустые подграфы заданного графа.

Закон поглощения. Если в k-ом ярусе дерева вершины v_i и v_j не смежны, поддерево с корнем v_i построено и если в поддереве с корнем v_j появляется дуга с вершиной v_i, то соответствующая ветвь не строится.

Закон поглощения используется для того, чтобы в дереве не было одинаковых ветвей. Ветви дерева строятся слева направо. Если при построении некоторой ветви получается ветвь, которая слева уже была построена, то эта ветвь не строится.

Определив ε₀(G), можно, используя т.1.1, определить π₀(G):

π₀(G) = | V | - ε₀(G).

Пример 3. Определить ε₀(G), π₀(G) для графа G, изображенного на рис. 1.1. Показать множество вершин графа G, соответствующих найденному числу π₀(G).

Воспользуемся алгоритмом выделения пустых графов. Выполнение первого пункта алгоритма заключается в том, что под заданным графиком рисуется корень, т.е. вершина, из которой дуги только исходят.

Переходим ко второму пункту алгоритма. Выбираем вершину с минимальной степенью. Таких вершин три: s(1) = s(3) = s(5) = 2. Выбираем любую из них. Пусть для этого будет вершина 1. Сопоставляем эту вершину концу дуги, исходящей из корня.

| Г₁ | = | {2,6}| = 2, значит, рисуем две дуги, исходящие из корня. Эти дуги располагаем правее первой дуги. Каждому концу взаимно однозначно сопоставляем вершину из окрестности G(1). Такими вершинами являются вершина 2 и вершина 6.

Согласно третьему пункту алгоритма каждый конец 1,2,6, взвешиваем соответственно неокрестностью (1), (2), (3).

Считаем концы 1,2,6 постоянного яруса корнями нового дерева. Это означает, что вершина 1 является корнем для графа, которым является (1),

вершина 2 – корнем графа (2), вершина 6 – корнем графа (6).

Так как вершины 1,2,6 не взвешены символом Ø, то переходим ко второму пункту алгоритма. Начинаем с нового корня 1. В сопоставленному корню 1 графе (1) вершины 3 и 5 имеют минимальную степень

(s(3) = s(5) = 1). Для определения возьмем вершину 3 и сопоставим ее концу дуги исходящей из корня 1. | Г₃ | = |{4}| = 1, значит, строим одну дугу, исходящую из корня 1. Располагаем ее правее построенной дуги. Концу дуги взаимно однозначно сопоставляем вершину из окрестности графа G(3) графа (1). Такой вершиной является вершина 4.

Согласно третьему пункту алгоритма каждый конец 3 и 4 взвешиваем соответственно неокрестностью (3) и (4) графа (1). Для вершины 3 это будет вершина 5, а для вершины 4 – пустое множество Ø. Для этой ветви построение закончилось.

Считаем конец 3 корнем нового дерева и переходим ко второму пункту алгоритма. Граф, сопоставленный корню 3, состоит из одной вершины 5. Значит, строим дугу, исходящую из корня 3, и сопоставим ее концу вершину 5. Так как | Г5 | = 0, (5) = Ø, то построение этой ветви закончено (рис. 1.5).

Двигаясь вправо, аналогично строим остальные ветви дерева. При построении этих ветвей следует помнить закон поглощения, чтобы не появились одинаковые ветви. Построение дерева показано на рис. 1.5.

2 6

3 5

4

 

4

3 5 5 3

5 Ø Ø Ø

Е₂= {1,4} Е₃= {2,5} Е₄= {3,6}

Ø

 

Е₁= {1,3,5}

Рис. 1.5

 

Получим пустые подграфы: Е₁= {1,3,5}, Е₂= {1,4}, Е₃= {2,5},

Е₄= {3,6}. Каждый пустой подграф состоит из попарно несмежных вершин заданного графа.

Согласно определению ε₀(G) = m_iax |E_i| = |E₁| = |{1,3,5}| = 3.

Далее π₀(G) = | V | - ε₀(G) = = |{1,2,3,4,5,6}| - 3 = 6 – 3 = 3.

Найденное значение π₀(G) означает (по определению π₀(G)), что наименьшее число вершин, покрывающих все ребра заданного графа G, равно 3. Такими вершинами могут быть вершины 2,4,6, т.е.

π₀(G) = |{2,4,6}| = 3.

Отметим, что закон поглощения не был использован. ■

Пример 4. Определить ε₀(G), π₀(G) для графа G (рис. 1.6). Показать множество вершин, соответствующих найденному числу π₀(G).

 

8

1 6

2 7

7

3

4 5

G

Рис. 1.6

Используя алгоритм выделения пустых подграфов, построим дерево

(рис. 1.7).

1 8 6

2 7

 

3 5

6

7 8

5 6

3 4 2

4 5 4 5

3 4 4 5 3 4 5

3 4 5 4 5

Ø Ø Ø Ø Ø Ø

5 Ø

Е₂ Е₃ Е₄ Е₅ Е₆ Е₇ Е₈

Ø

 

Е₁

Рис. 1.7

 

При построении дерева был использован закон поглощения. Так ветвь с корнем в вершине 8 должна состоять из множеств вершин {8,2,4} и {8,2,5}, а такая ветвь уже построена с корнем в вершине 2.

Заданный граф G имеет восемь пустых подграфов:

Е₁= {1,7,3,5}, Е₂= {1,7,4}, Е₃= {1,6,3}, Е₄= {1,6,4}, Е₅= {2,8,4},

Е₆= {2,8,5}, Е₇= {2,6,4}, Е₈= {8,3,5}.

ε₀(G) = |E₁| = |{1,7,3,5}| = 4,

π₀(G) = | V | - ε₀(G) = 8 – 4 = 4.

Множеством вершин, соответствующих найденному значению π₀(G) = 4, будет множество {2,4,6,8}, т.е.

π₀(G) = |{2,4,6,8}| = 4. ■

Для определения реберного числа независимости ε₁(G) графа G можно воспользоваться алгоритмом выделения пустых подграфов, если вместо вершин в нем рассматривать ребра, т.е. выделять реберно пустые подграфы (тогда сам алгоритм выделения пустых подграфов для вершин можно назвать алгоритмом выделения вершинно пустых подграфов).

Аналогично используется закон поглощения.

Определив ε₁(G), можно, используя т. 1.1, определить π₁(G):

π₁(G) = | V | - ε₁(G).

Пример 5. Определить ε₁(G), π₁(G) для графа G = < V, U >,

у котрого V = {1,2,3,4,5,6}, U = {(1,2), (1,6), (2,3), (2,4), (2,6), (3,4), (4,5), (4,6), (5,6)}. Показать множество ребер, соответствующих найденому числу

π₁(G).

Сопоставим корню дерева заданный граф G, предварительно обозначив ребра буквами, и определив ребро, смежное с минимальным количеством ребер (рис. 1.8). Такими ребрами будут ребра a, b, d, g, k, n. Каждое из них смежно с четырьмя ребрами. Для определенности возьмем ребро a – оно смежно с ребрами b,с, d,е. Сопоставим ребра а, b,с, d,е концам исходящих из корня дуг и взвесим каждую вершину построенного яруса подграфом, каждое ребро которого не смежно с ребром, сопоставленным этой вершине (рис. 1.8).

Другими словами, зафиксировав ребро заданного графа, сопоставим ему и его окрестности вершины яруса дерева, каждую из которых взвешиваем неокрестностью соответствующего ребра. Повторяя такое разложение графа до получения неокрестностей, равных Ø, выделяем все реберно независимые множества (реберно пустые подграфы) (рис. 1.8).

a b

2 6

c

d e f g

3 5

k 4 n

 

 

e b

f g f g

d e g

k n n

k n k n

g

d n

Ø Ø Ø Ø Ø Ø Ø Ø Ø

Е₂ Е₃ Е₅ Е₆ Е₇ Е₈ Е₉ Е₁₀ Е₁₁

 

Ø Ø

 

Е₁ Е₄

 

Рис. 1.8

При построении был использован закон поглощения.

Получили реберно пустые подграфы:

E₁ = {a,k,g}, E₂ = {a,n}, E₃ = {a,f}, E₄ = {b,n,d}, E₅ = {b,k},

E₆ = {b,e}, E₇ = {c,n}, E₈ = {c,k}, E₉ = {e,g}, E₁₀ = {d,g}, E₁₁ = {d,f}.

Так как ε₁(G) равно максимальному числу попарно несмежных ребер графа G, то

ε₁(G) = |E₁| = |E₄| = | {a,k,g}| = | {b,n,d} | = 3.

Тогда число реберного покрытия π₁(G):

π₁(G) = | V | - ε₁(G) = 6 - 3 = 3.

Множеством ребер, соответствующих найденному значению π₁(G) = 3, может быть множество {a,g, k}, т.е.

π₁(G) = |{a,g, k}| = 3.

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

Пример 6. Определить паросочетания и наибольшее паросочетание для графа G, рассмотренного в примере 5.

Используя решение примера 5, и определение паросочетания, можно сделать вывод, что паросочетаниями графа G будут множества ребер:

{a,g, k}, {a,n}, {a,f}, {b,n,d}, {b,k}, {b,e}, {c,n}, {c,k}, {d,g}, {d,f}.

Так, как в наибольшим паросочетании число ребер равно ε_1, то наибольших паросочетаний будет два: {a,k,g } и {b,n,d}. ■

1.3. Определение чисел β₀(G), β₁(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₁