Дискретная математика:
логика, группы, графы, фракталыАкимов О.Е.
3.2. Морфология графа
Реберные и вершинные покрытия
Часто ребра снабжены какой-либо весовой характеристикой, и покрывающее дерево требуется выбрать из оптимальных соображений: минимального или максимального веса покрывающего дерева. Для нахождения, например, остова минимального веса поступают следующим образом. Из всех предложенных ребер выбирают ребро с наименьшим весом. Затем на каждом следующем шаге из оставшегося числа рассматривается наименьшее по весу ребро. Если оно не образует цикла с ранее выбранными ветвями графа, то вводится в остов. Построение прекращается после n – 1 шага. Все остовы графов Г, Г1, Г2, Г3, Г4 из предыдущего подраздела выбраны как раз по этому алгоритму, при этом номер ребра принимался за его вес.
Покрывающее дерево графа Г нужно отличать от его реберного покрытия. Реберным покрытием графа Г(V, E) называется такое подмножество E' из E, которое инцидентно всему множеству вершин V. Наряду с реберным покрытием, вводят понятие независимого подмножества ребер: подмножество E" из E попарно несмежных ребер называется независимым (или паросочетанием). Аналогичная пара понятий существует для вершин. Подмножество вершин V' графа Г(V, E) называется независимым, если никакие две вершины из этого множества не смежны. Если подмножество вершин V' из V независимо, то порожденный этими вершинами подграф Г '(V', 0) является пустым. Упомянем попутно, антиподом независимого множества является понятие клики. Подмножество вершин называется кликой, если любые две входящие в него вершины смежны, т.е. когда порождаемый этим подмножеством подграф будет полным. И последнее понятие в этом ряду: подмножество вершин V" называется вершинным покрытием, если V" покрывает все ребра графа Г.
Оптимальные значения введенных характеристик обозначим следующим образом:
a0 — максимальное число независимых вершин,
b0 — минимальное вершинное покрытие,
a1 — максимальное число независимых ребер,
b1 — минимальное реберное покрытие.Для любого графа Г выполняется условие: a0 + b0 = a1 + b1 = n.
Двудольные графы Гд выделяются среди прочих тем, что для них выполняется дополнительное условие: a0 = b1, a1 = b0.
Поэтому для Гд имеет место расширенное условие:
a0 + b0 = a1 + b1 = a0 + a1 = b0 + b1 = n.
Кроме того, независимое множество ребер графа Г находится во взаимно однозначном соответствии с независимым множеством вершин реберного графа Гp, поэтому a1(Г) = a0(Гp).
Рис. 3.26
Теперь рассмотрим конкретный двудольный граф Гд, изображенный на рис. 3.26. Рядом с ним построим соответствующий ему реберный граф Гp. Для построения Гд(V, E) сначала было найдено общее число ребер в Гp — m', а затем матрица смежности — A(Гp):
Гд(V, E) = {e1, e2, e3, e4} = {{v1, v4, v5}, {v1}, {v2, v3, v4}, {v2, v4}},
m' = (1/2)(32 + 12 + 32 + 22 + 22 + 22 + 12 + 32 + 12) – 9 = 12,
A(Гp) =
.
В соответствии с определением составим пять максимальных паросочетаний с числом a1(Гд) = 4:
1) e1 — v4, e2 — v1, e3 — v3, e4 — v2, 2) e1 — v5, e2 — v1, e3 — v3, e4 — v2, 3) e1 — v5, e2 — v1, e3 — v3, e4 — v4, 4) e1 — v5, e2 — v1, e3 — v2, e4 — v4, 5) e1 — v5, e2 — v1, e3 — v4, e4 — v2.Имеется четыре минимальных реберных покрытия с числом b1(Гд) = 5:
1) e1 — v5, e2 — v1, e3 — v3, e3 — v2, e4 — v4, 2) e1 — v5, e2 — v1, e3 — v3, e4 — v2, e4 — v4, 3) e1 — v5, e2 — v1, e3 — v3, e3 — v4, e4 — v2, 4) e1 — v5, e2 — v1, e3 — v3, e4 — v4, e4 — v2.Каждое из этих покрытий определяется минимальным числом единиц, которые покрывают все строки и столбцы матрицы инцидентности (эти покрывающие единицы заменены звездочками):
,
,
,
.
Множество независимых вершин в графе Гp отвечает множеству независимых ребер в графе Гд , отсюда a1(Гд) = a0(Гp) = 4:
{1, 3, 7, 9}, {1, 4, 5, 7}, {1, 3, 6, 8}, {1, 3, 5, 7}, {1, 3, 5, 8}.
Для реберного графа Гp можно указать и три максимальных клики: {2, 3, 4}, {4, 8, 9} и {5, 6, 9}. Наконец, выпишем минимальные множества вершинных покрытий для графа Гp , которые получаются как дополнения к максимальным множествам независимых вершин:{2, 4, 5, 6, 8}, {2, 3, 6, 8, 9}, {2, 4, 5, 7, 9}, {2, 4, 6, 8, 9}, {2, 4, 6, 7, 9},
Для поиска подмножества независимых вершин и вершинных покрытий пользуются методом булевых функций [126]. С этой целью запишем граф Гp в конъюнктивной нормальной форме (КНФ), при этом сами символы конъюнкции опустим, оставив только символы дизъюнкции ( v ):f (Гp) = (2 v 1)(2 v 3)(2 v 4)(9 v 4)(9 v 5)(9 v 6)(9 v 8)(7 v 8)(7 v 6)(5 v 6)(4 v 8)(4 v 3).
Пользуясь только законами поглощения —
a v (ab) = a, a(a v b) = a,
переведем нашу булеву функцию f (Гp) в минимальную дизъюнктивную нормальную форму (ДНФ). На практике удобно использовать законы поглощения не после полного раскрытия скобок, а в процессе их последовательного перемножения:
f (Гp) = (2 v 134)(9 v 4568)(7 v 68)(5 v 6)(4 v 38) =
= (29 v 24568 v 1349 v 134568)(457 v 467 v 468 v 368 v 3578) =
= 24579 v 24679 v 24689 v 23689 v 24568 v 235789 v 134579 v 134679 v 134689 v 134568.Подчеркнутые конъюнкты образуют известные нам пять минимальных вершинных покрытий. Их дополнениями являются максимальные множества независимых вершин.
Чтобы проверить правильность нахождения всех вершинных покрытий, необходимо воспользоваться принципом двойственности, который действует в рамках логики Буля. Для этого результирующее выражение запишем в КНФ и с помощью того же закона поглощения приведем его к ДНФ:f (Гp) = (2 v 4 v 5 v 7 v 9)(2 v 4 v 6 v 7 v 9) ... (1 v 3 v 4 v 5 v 6 v 8) =
= 21 v 23 v 24 v 94 v 95 v 96 v 98 v 78 v 76 v 56 v 48 v 43.В конъюнктах этой дизъюнктивной формы узнаются ребра исходного графа Гp. Значит, минимальные покрытия найдены верно.
|
|
