Алгоритмы на графах. Независимые и доминирующие множества

Алгоритмы на графах. Независимые и доминирующие множества

Курсовая работа

"Алгоритмы на графах. Независимые и доминирующие множества"

Введение

Для графа G=(V, E) доминирующее множество вершин есть множество вершин SV, такое, что для каждой вершины j, не входящей в S, существует ребро, идущее из некоторой вершины множества S в вершину j. Доминирующее множество называется минимальным, если нет другого доминирующего множества, содержащегося в нем.

Пример.

Доминирующие множества (1, 2, 3), (4, 5, 6, 7, 8, 9), (1, 2, 3, 8, 9), (1,2, 3, 7) и т.д. Множества (1, 2, 3), (4, 5, 6, 7, 8, 9) являются минимальными. Если Q - семейство всех минимальных доминирующих множеств графа, то число [G]=minS

SQ

называется числом доминирования графа, а множество S*, на котором этот минимум достигается, называется наименьшим доминирующим множеством. Для нашего примера [G]=3.

Задача. Пусть город можно изобразить как квадрат, разделенный на 16 районов. Считается, что опорный пункт милиции, расположенный в каком-либо районе, может контролировать не только этот район, но и граничащие с ним районы. Требуется найти наименьшее количество пунктов милиции и места их размещения, такие, чтобы контролировался весь город.

Представим каждый район вершиной графа и ребрами соединим только те вершины, которые соответствуют соседним районам. Нам необходимо найти число доминирования графа и хотя бы одно наименьшее доминирующее множество. Для данной задачи [G]=4, и одно из наименьших множеств есть (3, 5, 12, 14). Эти вершины выделены на рисунке.

4. Задача о наименьшем покрытии

Рассмотрим граф. На рисунке показана его матрица смежности А и транспонированная матрица смежности с единичными диагональными элементами А*. Задача определения доминирующего множества графа G эквивалентна задаче нахождения такого наименьшего множества столбцов в

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

Замечание. 1. Если некоторая строка матрицы А* имеет единицу в единственном столбце, то есть больше нет столбцов, содержащих единицу в этой строке, то данный столбец следует включать в любое решение. 2. Рассмотрим множество столбцов матрицы А*, имеющих единицы в конкретной строке. Для нашего примера: U1=(1, 6, 7, 8), U2=(1, 2, 5, 8), U3=(2, 3, 5), U4=(3, 4), U5=(2, 3, 4, 5), U6=(5, 6), U7=(6, 7), U8=(7,8). Видим, что U4U5. Из этого следует, что 5-ю строку можно не рассматривать, поскольку любое множество столбцов, покрывающее 4-ю строку, должно покрывать и 5-ю. Четвертая строка доминирует над пятой.

5. Метод решения задачи о наименьшем разбиении

Попытаемся осознать метод решения задачи, рассматривая, как обычно, пример. У нас есть ориентированный граф, его матрица смежности и транспонированная матрица смежности с единичными диагональными элементами. Исследуем структуру матрицы А*. Нас интересует, какие столбцы содержат единицу в первой строке, какие столбцы содержат единицу во второй строке и не содержат в первой и так далее. С этой целью можно было бы переставлять столбцы в матрице А*, но оставим ее «в покое». Будем использовать дополнительную матрицу Bl, ее тип:

type Pr=array [1..MaxN, 1..MaxN+1] of integer;

var Bl: Pr; , где MaxN - максимальная размерность задачи. Почему плюс единица (технический прием - «барьер»), будет ясно из последующего изложения (процедура Press).

При инициализации матрица Bl должна иметь вид:

в первой строке - [1 2 3. №0];

все остальные элементы равны нулю.

То есть наше исходное предположение заключается в том, что все столбцы матрицы А* имеют единицы в первой строке. Проверим его. Будем просматривать элементы очередной строки (i) матрицы Bl. Если Bl [i, j]<>0, то со значением Bl [i, j], как номером столбца матрицы A*, проверим соответствующий элемент А*. При его неравенстве нулю элемент Bl остается на своем месте, иначе он переписывается в следующую строку матрицы Bl, а элементы текущей строки Bl сдвигаются вправо, сжимаются (Press). Итак, для N-1 строки матрицы Bl. Для нашего примера матрица Bl после этого преобразования будет иметь вид:

 4 3 6 1 0… 0

5 7 2 0… 0

Bl= 0 0

….

0 … 0

В нашей задаче определены стоимости вершин графа или стоимости столбцов матрицы А*, и необходимо найти разбиение наименьшей стоимости. Пусть стоимости описываются в массиве Price (Price:array [1..MaxN] of integer) и для примера на рисунке имеют значения [15 13 4 3 8 9 10]. Осталась чисто техническая деталь - отсортировать элементы каждой строки матрицы Bl по возрастанию стоимости соответствующих столбцов матрицы А. Логика формирования приведена ниже по тексту (Blocs).

procedure Blocs; {выделения блоков}

{Bl - глобальная переменная}

procedure Sort;

{Price и Bl - глобальные переменные}

begin

…

end;

procedure Press (i, j:integer); {Сдвигаем элементы строки с номером i, начиная с позиции (столбца) j, на одну позицию вправо}

{Bl - глобальная переменная}

var k:integer;

begin

k:=j;

while Bl [i, k]<>0 do begin {Поэтому размерность матрицы с плюс единицей. В последнем столбце строки всегда записан 0.}

Bl [i, k]:=Bl [i, k+1];

Inc(k);

end; {while}

end; {Press}

var i, j, cnt:integer;

begin

FillChar (Bl, SizeOf(Bl), 0);

for i:=1 to N do Bl [1, i]:=i; {предполагается, что в первом блоке все столбцы}

for i:=1 to N-1 do begin

j:=1; cnt:=0;

while Bl [i, j]<>0 do begin

if A*[i, Bl [i, j]]=0 then begin {столбец не в этом блоке}

Inc(cnt);

Bl [i+1, cnt]:=Bl [i, j]; {переписать в следующую строку}

Press (i, j);

Dec(j);

end; {if}

Inc(j);

end; {while}

end; {for}

Sort;

end; {Blocs}

После этой предварительной работы мы имеем вполне «приличную» организацию данных для решения задачи путем перебора вариантов. Матрица Bl разбита на блоки, и необходимо выбрать по одному элементу (если соответствующие строки ещё не покрыты) из каждого блока. Процесс выбора следует продолжать до тех пор, пока не будут включены в «покрытие» все строки или окажется, что некоторую строку нельзя включить.

Продолжим рассмотрение метода. Если при поиске независимых множеств мы шли «сверху вниз», последовательно уточняя логику, то сейчас попробуем идти «снизу вверх», складывая окончательное решение из сделанных «кирпичиков». Как обычно, следует начать со структур данных. Во-первых, мы ищем лучшее решение, то есть то множество столбцов, которое удовлетворяет условиям задачи (непересечение и «покрытие» всего множества строк), и суммарная стоимость этого множества минимальна. Значит, необходима структура данных для хранения этого множества и значения наилучшей стоимости и, соответственно, структуры данных для хранения текущего (очередного) решения и его стоимости. Во-вторых, в решении строка может быть или не быть. Следовательно, нам требуется как-то фиксировать эту информацию. Итак, данные.

type Model=array [1..MaxN] of boolean;

var Sbetter: Model; Pbetter:integer; {лучшее решение}

S: Model; P:integer; {текущее решение}

R: Model; {R[i]=true - признак того, что строка i «покрыта» текущим решением}

Логика включения (исключения) столбца с номером k в решение (из решения) имеет вид:

procedure Include (k:integer); {включить столбец в решение}

{A*, R, Price, S, P - глобальные переменные}

var j:integer;

begin

P:=P+Price[k]; {текущая цена решения}

S[k]:=true; {столбец с номером k в решение}

for j:=1 to N do

if A*[j, k]=1 then R[j]:=true; {строки, «покрытые» столбцом k}

end; {Include}

procedure Exclude (k:integer); {исключить столбец из решения}

var j:integer;

begin

p:=p-Price[k];

S[k]:=false;

for j:=1 to N do if (A*[j, k]=1) and R[j] then R[j]:=false;

end; {Exclude}

Проверка, сформировано ли решение, заключается в том, чтобы просмотреть массив R и определить, все ли его элементы равны истине.

function Result:boolean;

var j:integer;

begin

j:=1;

while (j<=N) and R[j] do Inc(j);

if j=N+1 then Result:=true else Result:=false;

end; {Result}

Кроме перечисленных «кирпичиков», нам необходимо уметь определять, можно ли столбец с номером k включать в решение. Для этого следует просмотреть столбец с номером k матрицы A* и проверить, нет ли совпадений единичных элементов со значением true соответствующих элементов массива R.

function Cross (k:integer):boolean; {пересечение столбца с частичным решением, сформированным ранее}

var j:integer;

begin

j:=1;

while (j<=N) and Not (R[j] and (A*[j, k]=1)) do Inc(j);

if j=N+1 then Cross:=true else Cross:=false;

end; {Cross}

Заключительная логика поиска (Find) имеет в качестве параметров номер блока (строки матрицы Bl) - переменная bloc и номер позиции в строке. Первый вызов - Find (1,1).

procedure Find (bloc, jnd:integer);

{переменные глобальные}

begin

if Result then begin if P<Pbetter then begin Pbetter:=P;

Sbetter:=S;

end;

end

else if Bl [bloc, jnd]=0 then exit

else if Cross (Bl[bloc, jnd]) then begin

Include (Bl[bloc, jnd]);

Find (bloc+1,1);

Exclude (Bl[bloc, jnd]);

end

else if R[bloc] then Find (bloc+1,1);

Find (bloc, jnd+1);

end; {Find}

Нам осталось дать общую логику, но после выполненной работы она не вызывает затруднений.

program R_min;

const MaxN=…;

type… var…

procedure Init; {ввод и инициализация данных}

begin

…

end;

procedure Print; {вывод результата}

begin

…

end;

{процедуры и функции, рассмотренные ранее}

{основная логика}

begin

Init;

Blocs;

Find (1,1);

Print;

end.

Заключение

Понятие, противоположное максимальному независимому множеству, есть максимальный полный подграф (клика). В максимальном независимом множестве нет смежных вершин, в клике все вершины попарно смежны. Максимальное независимое множество графа G соответствует клике графа G', где G' - дополнение графа G.

Литература