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

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

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

Введение

Определим граф как конечное множество вершин V и набор E неупорядоченных и упорядоченных пар вершин и обозначим G=(V, E). Мощности множеств V и E будем обозначать буквами N и M. Неупорядоченная пара вершин называется ребром, а упорядоченная пара – дугой. Граф, содержащий только ребра, называется неориентированным; граф, содержащий только дуги, – ориентированным, или орграфом. Вершины, соединенные ребром, называются смежными. Ребра, имеющие общую вершину, также называются смежными. Ребро и любая из его двух вершин называются инцидентными. Говорят, что ребро (u, v) соединяет вершины u и v. Каждый граф можно представить на плоскости множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими ребрам. В трехмерном пространстве любой граф можно представить таким образом, что линии (ребра) не будут пересекаться.

Способы описания.
Выбор соответствующей структуры данных для представления графа имеет принципиальное значение при разработке эффективных алгоритмов. При решении задач используются следующие четыре основных способа описания графа: матрица инциденций; матрица смежности; списки связи и перечни ребер. Мы будем использовать только два: матрицу смежности и перечень ребер.

Матрица смежности – это двумерный массив размерности N*N.

A [i, j]=

Для хранения перечня ребер необходим двумерный массив R размерности M*2. Строка массива описывает ребро.

1. Независимые множества

Задача поиска подмножеств множества вершин 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]&Gg; Следующийшаг– выходвпредыдущуюверсию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. Доминирующее множество называется минимальным, если нет другого доминирующего множества, содержащегося в нем.

Пример
.

Доминирующие множества (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 – семейство всех минимальных доминирующих множеств графа, то число b[G]=min½S½

SÎQ

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

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

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

Представим каждый район вершиной графа и ребрами соединим только те вершины, которые соответствуют соседним районам. Нам необходимо найти число доминирования графа и хотя бы одно наименьшее доминирующее множество. Для данной задачи b[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). Видим, что U4
ÌU5
. Из этого следует, что 5-ю строку можно не рассматривать, поскольку любое множество столбцов, покрывающее 4-ю строку, должно покрывать и 5-ю. Четвертая строка доминирует над пятой.

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

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

typePr=array [1..MaxN, 1..MaxN+1] ofinteger;

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 после этого преобразования будет иметь вид:

1	3	4	6	0	…	0
2	5	7	0	0	….	0
Bl=	0	0	0	0	0	…	0
……
0	0	0	0	0	0

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.

Литература

1. Адельсон-Вельский Г.М., Диниц Е.А., Карзанов А.В. Потоковые алгоритмы. - М.: Наука, 1975.

2. Берж К. Теория графов и ее применение. – М.: ИЛ, 1962.

3. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. – М.: Наука, 1990.

4. Зыков А.А. Теория конечных графов. - Новосибирск: Наука; Сиб. отд-ние, 1969.

5. Йенсен П., Барнес Д. Потоковое программирование.-М.:Радио и связь, 1984.

6. Касьянов В.Н., Сабельфельд В.К. Сборник заданий по практикуму на ЭВМ. – М.: Наука, 1986.

7. Кристофидес Н. Теория графов. Алгоритмический подход. - М.: Мир, 1978.

8. Кофман А. Введение в прикладную комбинаторику. - М.: Наука, 1975.

9. Липский В. Комбинаторика для программистов. - М.: Мир, 1988.

10.Майника Э. Алгоритмы оптимизации на сетях и графах.-М.:Мир, 1981.

11.Нечепуренко М.И., Попков В.К., Майнагашев С.М. и др. Алгоритмы и программы решения задач на графах и сетях. - Новосибирск: Наука; Сиб. отд-ние, 1990.

12.Окулов С.М. Конспекты занятий по информатике (алгоритмы на графах). Учебное пособие для студентов и учителей школ. – Киров, 1996.

13.Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация: Алгоритмы и сложность.-М.:Мир, 1985.

14.Свами М., Тхуласираман К. Графы, сети и алгоритмы. – М.: Мир, 1984.

15.Филипс Д., Гарсиа-Диас А. Методы анализа сетей. – М.: Мир, 1984.

16.Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. - М.: Мир, 1963.

17.Фрэнк Г., Фриш И. Сети, связь и потоки. - М.: Связь, 1978.

18.Харари Ф. Теория графов. - М.: Мир, 1973.