Курсовая работа
«Алгоритмы на графах. Независимые и доминирующие множества»
Введение
Определим граф как конечное множество вершин 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); exitend;
{черный ящик А}
;
i:=1;
while i
if i in Gg then begin
Ss[k]:=i;
Find (k+1, Qp-A[i] – [i], Qm-A[i] – [i]);
{черный ящик Б}
;
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) Итак, первое уточнение черного ящика А.
ifQm[] 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])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)
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] 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 после этого преобразования будетиметь вид: 1 3 4 6 … 2 5 7 …. 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] thenR[j]:=false;
end; {Exclude}
Проверка, сформировано ли решение, заключается в том, чтобыпросмотреть массив R и определить, все ли его элементы равны истине.
function Result:boolean;
var j:integer;
begin
j:=1;
while (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
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
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.