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.