1.2. Определение чисел ε0(g), π0(g), π1(g).
По определению ε0(G) равно максимальной мощности пустого графа, т.е.
ε0(G) = miax |Ei|, где Ei – пустые подграфы.
Cледовательно, для заданного графа G нужно выделить все пустые подграфы. Выделение пустых подграфов сводится к построению ориентированного дерева, в котором каждый путь между висячей вершиной (s (v) = 1) и концом дуги, исходящей из корня, состоит из вершин, которые образуют пустой подграф. Корень – это вершина, не являющаяся концом ни одной из дуг.
Алгоритм выделения пустых подграфов.
Сопоставляем корню синтезируемого дерева заданный граф G.
Фиксируем в графе вершину v0 с минимальной степенью, сопоставив ее концу дуги, исходящей из корня. Строим дуги, исходящие из корня, число которых равно
|Гv0|, и конец каждой из них взаимно однозначно сопоставляем вершине окрестности G (v0).
Каждый конец vα построенных дуг взвешиваем неокрестностью (vα) вершины графа, сопоставленного рассматриваемому корню.
Считаем конец vα построенного яруса корнем нового дерева.
Устанавливаем, взвешена ли вершина vα символом Ø. Если «нет», то переходим к п.2, если «да» то к п.6.
Пути между концами дуг, исходящих из корня синтезированного дерева, и висячими вершинами однозначно определяют пустые подграфы заданного графа.
Закон поглощения. Если в k-ом ярусе дерева вершины vi и vj не смежны, поддерево с корнем vi построено и если в поддереве с корнем vj появляется дуга с вершиной vi, то соответствующая ветвь не строится.
Закон поглощения используется для того, чтобы в дереве не было одинаковых ветвей. Ветви дерева строятся слева направо. Если при построении некоторой ветви получается ветвь, которая слева уже была построена, то эта ветвь не строится.
Определив ε0(G), можно, используя т.1.1, определить π0(G):
π0(G) = | V | - ε0(G).
П ример 3. Определить ε0(G), π0(G) для графа G, изображенного на рис. 1.1. Показать множество вершин графа G, соответствующих найденному числу π0(G).
Воспользуемся алгоритмом выделения пустых графов. Выполнение первого пункта алгоритма заключается в том, что под заданным графиком рисуется корень, т.е. вершина, из которой дуги только исходят.
Переходим ко второму пункту алгоритма. Выбираем вершину с минимальной степенью. Таких вершин три: s(1) = s(3) = s(5) = 2. Выбираем любую из них. Пусть для этого будет вершина 1. Сопоставляем эту вершину концу дуги, исходящей из корня.
| Г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. | Г3 | = |{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.
1
2 6
3 5
4
4
3 5 5 3
5
Ø Ø Ø
Е2= {1,4} Е3= {2,5} Е4= {3,6}
Ø
Е1= {1,3,5}
Рис. 1.5
Получим пустые подграфы: Е1= {1,3,5}, Е2= {1,4}, Е3= {2,5},
Е4= {3,6}. Каждый пустой подграф состоит из попарно несмежных вершин заданного графа.
Согласно определению ε0(G) = miax |Ei| = |E1| = |{1,3,5}| = 3.
Далее π0(G) = | V | - ε0(G) = = |{1,2,3,4,5,6}| - 3 = 6 – 3 = 3.
Найденное значение π0(G) означает (по определению π0(G) ), что наименьшее число вершин, покрывающих все ребра заданного графа G, равно 3. Такими вершинами могут быть вершины 2,4,6, т.е.
π0(G) = |{2,4,6}| = 3.
Отметим, что закон поглощения не был использован. ■
Пример 4. Определить ε0(G), π0(G) для графа G (рис. 1.6). Показать множество вершин, соответствующих найденному числу π0(G).
8
1
6
2 7
7
3
4 5
G
Рис. 1.6
Используя алгоритм выделения пустых подграфов, построим дерево
(рис. 1.7).
1
8
6
2 7
3 5
4
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 Ø
Е2 Е3 Е4 Е5 Е6 Е7 Е8
Ø
Е1
Рис. 1.7
При построении дерева был использован закон поглощения. Так ветвь с корнем в вершине 8 должна состоять из множеств вершин {8,2,4} и {8,2,5}, а такая ветвь уже построена с корнем в вершине 2.
Заданный граф G имеет восемь пустых подграфов:
Е1= {1,7,3,5}, Е2= {1,7,4}, Е3= {1,6,3}, Е4= {1,6,4}, Е5= {2,8,4},
Е6= {2,8,5}, Е7= {2,6,4}, Е8= {8,3,5}.
ε0(G) = |E1| = |{1,7,3,5}| = 4,
π0(G) = | V | - ε0(G) = 8 – 4 = 4.
Множеством вершин, соответствующих найденному значению π0(G) = 4, будет множество {2,4,6,8}, т.е.
π0(G) = |{2,4,6,8}| = 4. ■
Для определения реберного числа независимости ε1(G) графа G можно воспользоваться алгоритмом выделения пустых подграфов, если вместо вершин в нем рассматривать ребра, т.е. выделять реберно пустые подграфы (тогда сам алгоритм выделения пустых подграфов для вершин можно назвать алгоритмом выделения вершинно пустых подграфов).
Аналогично используется закон поглощения.
Определив ε1(G), можно, используя т. 1.1, определить π1(G):
π1(G) = | V | - ε1(G).
Пример 5. Определить ε1(G), π1(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)}. Показать множество ребер, соответствующих найденому числу
π1(G).
Сопоставим корню дерева заданный граф G, предварительно обозначив ребра буквами, и определив ребро, смежное с минимальным количеством ребер (рис. 1.8). Такими ребрами будут ребра a, b, d, g, k, n. Каждое из них смежно с четырьмя ребрами. Для определенности возьмем ребро a – оно смежно с ребрами b,с, d,е. Сопоставим ребра а, b,с, d,е концам исходящих из корня дуг и взвесим каждую вершину построенного яруса подграфом, каждое ребро которого не смежно с ребром, сопоставленным этой вершине (рис. 1.8).
Другими словами, зафиксировав ребро заданного графа, сопоставим ему и его окрестности вершины яруса дерева, каждую из которых взвешиваем неокрестностью соответствующего ребра. Повторяя такое разложение графа до получения неокрестностей, равных Ø, выделяем все реберно независимые множества (реберно пустые подграфы) (рис. 1.8).
1
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
Ø Ø Ø
Ø Ø Ø Ø Ø Ø
Е2 Е3 Е5 Е6 Е7 Е8 Е9 Е10 Е11
Ø Ø
Е1 Е4
Рис. 1.8
При построении был использован закон поглощения.
Получили реберно пустые подграфы:
E1 = {a,k,g}, E2 = {a,n}, E3 = {a,f}, E4 = {b,n,d}, E5 = {b,k},
E6 = {b,e}, E7 = {c,n}, E8 = {c,k}, E9 = {e,g}, E10 = {d,g}, E11 = {d,f}.
Так как ε1(G) равно максимальному числу попарно несмежных ребер графа G, то
ε1(G) = |E1| = |E4| = | {a,k,g}| = | {b,n,d} | = 3.
Тогда число реберного покрытия π1(G):
π1(G) = | V | - ε1(G) = 6 - 3 = 3.
Множеством ребер, соответствующих найденному значению π1(G) = 3, может быть множество {a,g, k}, т.е.
π1(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}. ■