Должна работать логика черного ящика АА. Замечание 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. Рассмотрим множество столбцов матрицы А*, имеющих единицы в конкретной строке. Для нашего примера: U¹ =(1, 6, 7, 8), U² =(1, 2, 5, 8), U³ =(2, 3, 5), U⁴ =(3, 4), U⁵ =(2, 3, 4, 5), U⁶ =(5, 6), U⁷ =(6, 7), U⁸ =(7,8). Видим, что U⁴ ÌU⁵ . Из этого следует, что 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