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

Проверка, сформировано ли решение, заключается в том, чтобы просмотреть массив 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]);