О задаче нахождения максимально-независимых множеств графа

О задаче нахождения максимально-независимых
множеств графа

Теория: Дан неориентированный граф G=(V,E). Независимое множество вершин есть множество вершин графа G, такое, что любые две вершины в нем не смежны, т.е. никакая пара вершин не соединена ребром.

Независимое множество называется максимальным, когда нет другого независимого множества, в которое оно бы входило.

У максимально-независимого множества графа есть такое свойство:

S – максимально-независимое множество графа G

U – множество вершин, смежных с вершинами множества S

G=S+U

Отсюда следует и метод решения задачи нахождения максимально-назависимых множеств (МНМ), то есть находится такое множество несмежных вершин графа, которое в совокупности со своими смежными вершинами образует граф. Основной идеей сокращения перебора является последовательное расширение независимого множества. Если его нельзя будет расширить, то это множество и есть максимально- независимое.

В работе [1] приведена следующая логика решения данной задачи:

Переменные:

Type Sset=set of 1..N;

a:Array[1..N] of set of 1..N; i-ый элемент массива множество вершин, смежных с вершиной i.[1]

Ss – массив решения. Решением являются первые k элементов

k – переменная, указывающая на порядковый номер вершины, которую мы хотим включить в решение

qp – множество вершин, которые еще не были рассмотрены в процессе перебора

qm - множество вершин, которые уже были просмотрены в процессе перебора

Gg – множество кандидатов на расширение текущего независимого множества.

Опишем логику вывода решения из массива Ss:

Procedure Print(k:byte);

Var i:integer;

Begin

Writeln;

For i:=1 to k do write(Ss[i]:2);

End;

Для решения нам понадобится функция подсчета количества элементов в множестве.

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;

{основная процедура решения задачи}

Procedure FIND (k:integer; qp,qm:sset);

var i,delt,j:byte;

gg:sset;

begin

if (qp<>[]) or (qm<>[]) then begin

{форомирование множества Gg}

if qm<>[] then begin

delt:=n+1;

for j:=1 to n do

if j in qm then

АА

if number(a[j]*qp)

i:=j;

delt:=number(a[j]*qp);

end;

gg:=qp*a[i];

end

else gg:=qp;

{поиск следующей вершины}

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:=qp-[i];

Б

qm:=qm+[i];

if number(qp*a[i])

then gg:=qp*a[i];

end;

inc(i);

end;

end else print(k);

end;

Но в вышеуказанной книге приведен пример, который не в полной мере раскрывает необходимость использования блоков АА и Б, а также целесообразность введения множества Qm. Поэтому попытаемся привести новый пример и уточнить вышеуказанные моменты методом трассировки.

Рассмотрим граф на рисунке 1. Матрица A для него будет выглядеть следующим образом:

A[1]=[2,5,10]

A[2]=[1,3,9,10]

A[3]=[2,4,7..9]

A[4]=[3,5..7]

A[5]=[1,4,6]

A[6]=[4,5,7]

A[7]=[3,4,6,8,9]

A[8]=[3,7,9]

A[9]=[2,3,7,8,10]

A[10]=[1,2,9]

Используем метод трассировки.

№	K	Qp	Qm	Gg	Ss	Примечания
1	1	[1..10]	[]	[1..10]	(1)	Вбираем первую вершину
2	2	[3,4,6..9]	[]	[3,4,6..9]	(1,3)	Включаем вершину 3
3	3	[6]	[]	[6]	(1,3,6)	Включаем вершину 6
4	4	[]	[]	[]	(1,3,6)	Вывод первого мн-ва и выход в предыдущую копию процедуры FIND
5	3	[]	[6]	[]	(1,3,6)	Выход в предыдущую копию Find
6	2	[4,6..9]	[3]	[4,7..9]	(1,4)	Исключаем вершину 3 из Ss и включаем ее в Qm. Продолжает работу цикл while. Он включает следующую вершину – 4.
7	3	[8,9]	[]	[8,9]	(1,4,8)	Вывод второго МНМ
8	3	[9]	[8]	[9]	(1,4,9)	Вывод третьего МНМ и выход в предыдущую копию Find
9	2	[6..9]	[3,4]	[6,7]	(1,6)
10	3	[8,9]	[3]	[]	(1,6)	Первое использование блока AA. Этот блок используется для сокращения перебора. Он формирует множество Gg как пересечение множеств Qp и A[j], где j из Qm. Причем мощность множеств минимальна.
	3	[8,9]	[3]	[8,9]	(1,6)	В итоге формирования I приняло значение 3
	3	[8,9]	[3]	[8,9]	(1,6,8)
11	4	[]	[]	[]	(1,6,8)	Вывод МНМ
12	3	[9]	[3,8]	[9]	(1,6,9)
13	4	[]	[]	[]	(1,6,9)	Вывод МНМ
14	2	[7..9]	[3,4,6]	[7]	(1,7)
15	3	[]	[]	[]	(1,7)	Вывод МНМ
16	1	[2..10]	[1]	[2,5,10]	(2)
17	2	[4..8]	[]	[4..8]	(2,4)
18	3	[8]	[]	[8]	(2,4,8)
19	4	[]	[]	[]	(2,4,8)	Вывод МНМ
20	2	[5..8]	[4]	[5..7]	(2,5)
21	3	[7..8]	[]	[7..8]	(2,5,7)
22	4	[]	[]	[]	(2,5,7)	Вывод МНМ
23	3	[8]	[7]	[8]	(2,5,8)
24	4	[]	[]	[]	(2,5,8)	Вывод МНМ
25	2	[6..8]	[4,5]	[6]	(2,6)
26	3	[8]	[]	[8]	(2,6,8)
27	4	[]	[]	[]	(2,6,8)	Вывод МНМ
28	1	[3..10]	[1,2]	[2,5,10]	(5)
29	2	[3,7..10]	[2]	[3,9,10]	(5)	Вновь включается в работу блок AA. Qm состоит из1го элемента – 2, поэтому он и будет выбран как минимальный.
	2	[3,7..10]	[2]	[3,9,10]	(5,3)
30	3	[10]	[]	[10]	(5,3,10)
31	4	[]	[]	[]	(5,3,10)	Вывод МНМ
32	2	[7..10]	[2,3]	[3,9,10]	(5,9)
33	3	[]	[]	[]	(5,9)	Вывод МНМ
34	2	[7,8,10]	[2,3,9]	[3,9,10]	(5,10)
35	3	[7,8]	[3]	[]	(5,10)	Вновь срабатывает ящик AA.
	3	[7,8]	[3]	[7,8]	(5,10)	Gg изменится после выбора как минимального множества пересечения Qp и А[3].
	3	[7,8]	[3]	[7,8]	(5,10,7)
36	4	[]	[]	[]	(5,10,7)	Вывод МНМ
37	3	[8]	[3,7]	[8]	(5,10,8)	…Вывод МНМ
38	1	[3,4,6..10]	[1,2,5]	[4,6]	(6)
39	2	[3,8..10]	[1,2]	[]	(6)	Вновь срабатывает блок AA. Множество ранее просмотренных состоит из двух элементов. Из них, для сокращения перебора, выбирается число при котором пересечение Qp и множества вершин смежных данной наименьшее. Это 1.
	2	[3,8..10]	[1,2]	[10]	(6)	Множество Gg преобразовалось.
	2	[3,8..10]	[1,2]	[10]	(6,10)	…
40	4	[]	[]	[]	(6,10,3)	Вывод МНМ
41	4	[]	[]	[]	(6,10,8)	Вывод последнего МНМ и выход из процедуры

Примечание! В блоках АА и Б выбирается минимальное по мощности множество, т.к., выполняя такой шаг, мы каждый раз, сокращая множество Gg сокращаем количество итераций в рассмотрении, а значит и сокращаем перебор.

Литература

1. Окулов С.М. Конспекты занятий по информатике (алгоритмы на графах). Киров, 1996.

---

[1] Данный метод описания графа используется, т.к. нам часто придется рассматривать вершины, смежные с данной.

Домініко Дольче. А Лил Вейн стал мужем аж двух девушек.

Наши машины и все что нужно знать об их эксплуатации

Блог про фiнансову кризу у свiтi. А вы знаете, что такое рецессия экономики??