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

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];