Пример.
Доминирующие множества (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). Эти вершины выделены на рисунке.
Рассмотрим граф. На рисунке показана его матрица смежности А и транспонированная матрица смежности с единичными диагональными элементами А*. Задача определения доминирующего множества графа 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-ю. Четвертая строка доминирует над пятой.
Попытаемся осознать метод решения задачи, рассматривая, как обычно, пример. У нас есть ориентированный граф, его матрица смежности и транспонированная матрица смежности с единичными диагональными элементами. Исследуем структуру матрицы А*. Нас интересует, какие столбцы содержат единицу в первой строке, какие столбцы содержат единицу во второй строке и не содержат в первой и так далее. С этой целью можно было бы переставлять столбцы в матрице А*, но оставим ее «в покое». Будем использовать дополнительную матрицу 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.