Алгоритмы на графах. Независимые и доминирующие множества (стр. 1 из 2)
Курсовая работа
"Алгоритмы на графах. Независимые и доминирующие множества"
Определим граф как конечное множество вершин V и набор E неупорядоченных и упорядоченных пар вершин и обозначим G=(V, E). Мощности множеств V и E будем обозначать буквами N и M. Неупорядоченная пара вершин называется ребром, а упорядоченная пара – дугой. Граф, содержащий только ребра, называется неориентированным; граф, содержащий только дуги, – ориентированным, или орграфом. Вершины, соединенные ребром, называются смежными. Ребра, имеющие общую вершину, также называются смежными. Ребро и любая из его двух вершин называются инцидентными. Говорят, что ребро (u, v) соединяет вершины u и v. Каждый граф можно представить на плоскости множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими ребрам. В трехмерном пространстве любой граф можно представить таким образом, что линии (ребра) не будут пересекаться.
Способы описания. Выбор соответствующей структуры данных для представления графа имеет принципиальное значение при разработке эффективных алгоритмов. При решении задач используются следующие четыре основных способа описания графа: матрица инциденций; матрица смежности; списки связи и перечни ребер. Мы будем использовать только два: матрицу смежности и перечень ребер.
Матрица смежности – это двумерный массив размерности N*N.
A [i, j]=
Для хранения перечня ребер необходим двумерный массив R размерности M*2. Строка массива описывает ребро.
Задача поиска подмножеств множества вершин V графа G, удовлетворяющих определенным условиям, свойствам, возникает достаточно часто.
Дан неориентированный граф G=(V, E). Независимое множество вершин есть множество вершин графа G, такое, что любые две вершины в нем не смежны, то есть никакая пара вершин не соединена ребром. Следовательно, любое подмножество S, содержащееся в V, и такое, что пересечение S с множеством вершин смежных с S пусто, является независимым множеством вершин.
Пример.
Множества вершин (1, 2), (3, 4, 5), (4, 7), (5, 6) – независимые. Независимое множество называется максимальным, когда нет другого независимого множества, в которое оно бы входило. Если Q является семейством всех независимых множеств графа G, то число
a[G]=max½S½
SÎQ
называется числом независимости графа G, а множество S*, на котором этот максимум достигается, называется наибольшим независимым множеством. Для нашего примера a[G]=3, а S* есть (3, 4, 5).
Понятие, противоположное максимальному независимому множеству, есть максимальный полный подграф (клика). В максимальном независимом множестве нет смежных вершин, в клике все вершины попарно смежны. Максимальное независимое множество графа G соответствует клике графа G’, где G’ – дополнение графа G.
Для нашего примера дополнение G’ приведено на следующем рисунке, клика графа G’ соответствует максимальному независимому множеству графа G. Число независимости графа G’ равно 4, максимальное независимое множество (2, 5, 7, 8), ему соответствует клика графа G.
2. Метод генерации всех максимальных независимых множеств графа
Задача решается перебором вариантов. «Изюминкой» является отсутствие необходимости запоминать генерируемые множества с целью проверки их на максимальность путем сравнения с ранее сформированными множествами. Идея заключается в последовательном расширении текущего независимого множества (k – номер шага или номер итерации в процессе построения). Очевидно, что если мы не можем расширить текущее решение, то найдено максимальное независимое множество. Выведем его и продолжим процесс поиска. Будем хранить текущее решение в массиве Ss (Ss:array [1..N] of integer), его первые k элементов определяют текущее решение. Логикавывода.
procedure Print (k:integer);
var i:byte;
begin
writeln; for i:=1 to k do write (Ss[i], ’ ‘);
end;
В процессе решения нам придется многократно рассматривать вершины графа, смежные с данной. При описании графа матрицей смежности – это просмотр соответствующей строки, при описании списками связи – просмотр списка. Упростим нахождение смежных вершин за счет использования нового способа описания графа. Используем множественный тип данных. Введем тип данных:
type Sset=set of 1..N; и переменную
var A:array [1..N] of Sset;.
Итак, чтобы определить вершины графа, смежные с вершиной i, необходимо просто вызвать соответствующий элемент массива A.
Пример.
Основная сложность алгоритма в выборе очередной вершины графа. Введем переменную Gg для хранения номеров вершин – кандидатов на расширение текущего решения. Значение переменной формируется на каждом шаге k. Что является исходной информацией для формирования Gg? Очевидно, что некоторое множество вершин, свое для каждого шага (итерации) алгоритма. Логически правомерно разбить это множество вершин на не использованные ранее (Qp) и использованные ранее (Qm). Изменение значений Qp и Qm происходит при возврате на выбор k-го элемента максимального независимого множества. Мы выбирали на k шаге, например, вершину с номером i, и естественно исключение ее из Qp и Qm при поиске следующего максимального независимого множества. Кроме того, при переходе к шагу с номером (k+1) из текущих множеств Qp и Qm для следующего шага необходимо исключить вершины, смежные с вершиной i, выбранной на данном шаге (из определения независимого множества) и, разумется, саму вершину i. Итак, общая логика.
procedure Find (k:integer; Qp, Qm: Sset);
var Gg: Sset;
i:byte;
begin
if (Qp=[]) and (Qm=[]) then begin Print(k); exit end;
{черный ящик А}
<формирование множества кандидатов Gg для расширения текущего решения (k элементов в массиве Ss) по значениям Qp и Qm>;
i:=1;
while i<=N do begin
if i in Gg then begin
Ss[k]:=i;
Find (k+1, Qp-A[i] – [i], Qm-A[i] – [i]);
{черный ящик Б}
<изменение Qp, Qm для этого уровня (значения k) и, соответственно, изменение множества кандидатов Gg>;
end;
Inc(i);
end; {while}
end; {Find}
Продолжим уточнение логики. Нам потребуется простая функция подсчета количества элементов в переменных типа Sset.
function Number (A: Sset):byte;
var i, cnt:byte;
begin
cnt:=0; for i:=1 to N do if i in A then Inc(cnt); Number:=cnt;
end;
Используем метод трассировки для того, чтобы найти дальнейшую логику уточнения решения. Будем делать разрывы таблицы для внесения пояснений в работу черных ящиков.
| k | Qp | Qm | Gg | Ss | Примечания |
| 1 | [1..5] | [] | [1..5] | (1) | Выбираем первую вершину |
| 2 | [4,5] | [] | [4,5] | (1,4) | Итак, первое уточнение черного ящика А. |
if Qm<>[] then <черныйящикАА >
else Gg:=Qp;
Его суть в том, что если выбирать из ранее использованных вершин нечего, то множество кандидатов совпадает со значением Qp, и далее по логике мы «тупо» выбираем первую вершину из Qp. Переходим к следующему вызову процедуры Find.
| 3 | [] | [] | [] | (1,4) | Вывод первого максимального независимого множества и выход в предыдущую копию Find. |
| 2 | [5] | [4] | [5] | (1,5) | Исключаем вершину 4 из Qp и включаем ее в Qm. |
Продолжает работу цикл while процедуры Find. Выбираем следующую вершину – это вершина 5. И вызываем процедуры Find с другими значениями параметров.
| 3 | [] | [] | [] | (1,5) | Вывод второго максимального независимого множества. |
| 2 | [] | [4,5] | [] | Цикл while закончен, выход в предыдущую копию процедуры Find. |
Уточнение черного ящика Б. Первое: необходимо исключить вершину i из Qp и включить ее в Qm. Второе: следует откорректировать множество Gg. Выбор на этом шаге вершин, не смежных с i, приведет к генерации повторяющихся максимальных независимых множеств, поэтому следует выбирать вершины из пересечения множеств Qp и A[i]. Итак, черный ящик Б.
Qp:=Qp – [i]; Qm:=Qm+[i];
if Number (Qp*A[i])<Number(Gg) then Gg:=Qp*A[i]⋙ Следующийшаг– выходвпредыдущуюверсиюFind, при этом значение k равно 1.
| 1 | [2..5] | [1] | [1..5] | Однако после работы черного ящика Б имеем следующие значения переменных |
| 1 | [2..5] | [1] | [2..3] | (2) |
| 2 | [3,5] | [] | [3,5] | (2,3) |
| 3 | [5] | [] | [5] | (2,3,5) |
| 4 | [] | [] | [] | Вывод третьего максимального независимого множества. |
| 3 | [] | [5] | [] | |
| 2 | [5] | [3] | [] | Согласно логике черного ящика Б множество кандидатов Gg становится пустым. |
| 1 | [3..5] | [1,2] | [2,3] | (3) |
| 2 | [5] | [2] | Итак, мы первый раз попадаем в процедуру Find, и множество Gm при этом не пусто. |
Должна работать логика черного ящика АА. Замечание 1. Если существует вершина j, принадлежащая Qm, такая, что пересечение A[j] и Qp пусто, то дальнейшее построение максимального независимого множества бессмысленно – вершины из A[j] не попадут в него. Замечание 2. Если нет вершин из Qm, удовлетворяющих первому замечанию, то какую вершину из Qp следует выбирать? Ответ: вершину iÎ(QpÇA[j]) для некоторого значения jÎQm, причем мощность пересечения множеств A[j] и Qp минимальна. Данный выбор позволяет сократить перебор. Итак, логика черного ящика АА.
begin
delt:=N+1;
for j:=1 to N do if j in Qm then if Number (A[j]*Qp)<delt then
begin i:=j; delt:=Number (A[j]*Qp); end;
Gg:=Qp*A[i];
end
Закончим трассировку примера.
| 2 | [5] | [2] | [] | |
| 1 | [5] | [1,2,3] | [] | Выход в основную программу. |
Мы нашли все максимальные независимые множества.
3. Доминирующие множества
Для графа G=(V, E) доминирующее множество вершин есть множество вершин SÌV, такое, что для каждой вершины j, не входящей в S, существует ребро, идущее из некоторой вершины множества S в вершину j. Доминирующее множество называется минимальным, если нет другого доминирующего множества, содержащегося в нем.