Диссертация (1149246), страница 13
Текст из файла (страница 13)
ПРОГРАММНАЯ РЕАЛИЗАЦИЯМЕТОДА ПОЛНОГО ПЕРЕБОРА ДЛЯ ПОСТРОЕНИЯВСЕХ МАКСИМАЛЬНЫХ НЕЗАВИСИМЫХМНОЖЕСТВ> restart;> Matching:=proc(M) #формируем n*(n-1)/2 пар из вершин множества Mlocal S,n,i,j;S:=[];n:=nops(M);for i from 1 to n-1 dofor j from i+1 to n doS:=[op(S),[M[i],M[j]]];end do;end do;return S;end proc:> Independent_check:=proc(A,M) #проверка на независимость множества Mlocal n,kol,independent,i,S;S:=Matching(M);n:=nops(S);kol:=0;independent:=false;for i from 1 to n doif A[S[i][1],S[i][2]]=0 then kol:=kol+1; end if;end do;if nops(S)=kol then independent:=true; end if;return independent;end proc:106> Bin_System:=proc(N,n) #генерируем двоичную последовательность:#0...0, 0...1, 0...10, 0...11 и т.д.local p1,p2,x,kol,i,j,position,l,S;p1:=N;kol:=1;while p1<>0 and p1<>1 dop2:=trunc(p1/2);x[kol]:=p1-p2*2; kol:=kol+1;p1:=p2;end do;position:=n-(kol);S:=[];for i from 1 to position doS:=[op(S),0];end do;S:=[op(S),p1]; l:=1;for j from position+2 to n doS:=[op(S),x[kol-l]]; l:=l+1;end do;return S;end proc:> SubSet:=proc(Sett,n,N) #строим N-e подмножествоlocal S, sub_Sett, i;S:=Bin_System(N,n):sub_Sett:={};for i from 1 to n doif S[n-i+1]=1 then sub_Sett:={op(sub_Sett),Sett[i]}; end if;end do;107return sub_Sett;end proc:> Total_Simple:=proc(G,A) #G - множество вершин графа,#А - его матрица смежностиlocal Q,N,m,n;MG:={}; #все построенные максимальные независимые множестваmG:=nops(MG): n:=nops(G):for N from 1 to 2^n-1 do #всего подмножеств будет 2^n-1#(без учета пустого множества)Q:=SubSet(G,n,N);nQ:=nops(Q):if Independent_check(A,Q)=true thenfindVertex:=0:Vr:=V minus Q:nr:=nops(Vr):if nops(Vr)<>0 thenfor j from 1 to nr doQr:=Q union {Vr[j]}:if Independent_check(A,Qr)=true thenfindVertex:=1:break:end if:end do:end if:if findVertex=0 then MG:={op(MG),Q}; end if:end if;end do;return MG, nops(MG);end proc:108ПРИЛОЖЕНИЕ 3.
ПРОГРАММНАЯ РЕАЛИЗАЦИЯАЛГОРИТМА БРОНА-КЕРБОША> restart;> BronKerbosh:=proc(Adj) #граф задан списками смежности Adjlocal i,s,K,M,P,kol,v,ind_vertex,MaxIndepSet;K||0:={}:for i from 1 to n doK||0:={op(K||0),i}:end do:M||0:={}:P||0:={}:s:=0:kol:=0:while nops(K||s)<>0 or nops(M||s)<>0 doif nops(K||s)<>0 thenv[s]:=K||s[1];ind_vertex:=v[s];M||(s+1):=M||s union {v[s]};K||(s+1):=K||s minus Adj||ind_vertex minus {v[s]};P||(s+1):=P||s minus Adj||ind_vertex;s:=s+1;elseif nops(P||s)=0 thenkol:=kol+1; MNM||kol:=M||s;end if;s:=s-1;K||s:=K||s minus {v[s]};P||s:=P||s union {v[s]};109end if;end do;MaxIndepSet:={};for i from 1 to kol doMaxIndepSet:={op(MaxIndepSet),MNM||i}:end do:return MaxIndepSet, kol;end proc:110ПРИЛОЖЕНИЕ 4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯАЛГОРИТМА РОБСОНА> restart;> Robson:=proc(G,MD,MS)local MaximumSet:> MassDegAdj:=proc(MD,NewG) #массив степеней вершин подграфа NewGlocal nMD,i,MassDegNewG,Adj:MassDegNewG:=[]:nMD:=nops(MD):for i from 1 to nMD doif member(MD[i][1],NewG) thenAdj:=MD[i][3] intersect NewG:MassDegNewG:=[op(MassDegNewG),[MD[i][1],nops(Adj),Adj]]:end if:end do:return MassDegNewG:end proc:> Domination:=proc(A,B,MD,indA,indB) #проверка на доминированиеlocal i,n,kol,AD,BD:AD:=MD[indA][3] union {A}:BD:=MD[indB][3] union {B}:n:=nops(AD):kol:=0:for i from 1 to n doif member(AD[i],BD) then kol:=kol+1: end if:end do:if kol=n then #print(’A_dominates_B’):return true: else return false:111end if:end proc:> DFS:=proc(V,MD) #поиск компонент связности графаlocal n,i,Mark,count,j,Component,k,nV,maxV,C:Component:=proc(x,count,Mark,MassD)local Ad,nAd,i,Metka,nMD,v:#считываем списки смежности из массива MassD, для того чтобысформировать списки смежности вершин, смежных с xnMD:=nops(MassD):for i from 1 to nMD dov:=MassD[i][1]:Adj||v:=MassD[i][3]:end do:Metka:=Mark:Metka[x]:=count:Ad:=Adj||x:nAd:=nops(Ad):for i from 1 to nAd doif Metka[Ad[i]]=0 thenMetka:=Component(Ad[i],count,Metka,MD):end if:end do:return Metka:end proc:n:=nops(V):maxV:=V[1]:for i from 2 to n doif V[i]>maxV then maxV:=V[i]; end if;end do:112Mark:=[]:for i from 1 to maxV doif member(i,V) then Mark:=[op(Mark),0]:else Mark:=[op(Mark),-1]end if:end do:count:=0: #счетчик числа компонентfor i from 1 to n doif Mark[V[i]]=0 thencount:=count+1:Mark:=Component(V[i],count,Mark,MD):end if:end do:C:=[];for k from1 to count doC||k:={}:nV:=nops(V):for i from 1 to nV doif Mark[V[i]]=k thenC||k:={op(C||k),V[i]}:end if:end do:C:=[op(C),C||k]:end do:Mark:=[]:return count,C:end proc:> sortS:=proc(Deg) #сортировка массива степеней Deglocal MD, n, i,j,tmp,S,k:113MD:=Deg:n:=nops(MD):for i from 1 to n dofor j from 1 to n-i doif MD[j][2]>MD[j+1][2] thentmp:=MD[j+1]: MD[j+1]:=MD[j]: MD[j]:=tmp:end if:end do:end do:S:=[]:for k from 1 to n doS:=[op(S),MD[k][1]]:end do:return S, MD;end proc:> choose_AB:=proc(min,MassDegree)# выбор вершин A и Blocal nMD,i,a,ad,nAdj,maxD,j,b,MassAB,b_max,vA,vB,nMassAB,maxB,v;nMD:=nops(MassDegree):#считываем список смежности из массива MassDegreefor i from 1 to nMD dov:=MassDegree[i][1]:Adj||v:=MassDegree[i][3]:ind||v:=i:end do:MassAB:=[]: #массив кандидатов на роль вершин A и Bfor i from 1 to nMD doif MassDegree[i][2]=min thena:=MassDegree[i][1]:ad:=Adj||a:114nAdj:=nops(ad):maxD:=0:for j from 1 to nAdj dob:=ad[j]:if nops(Adj||b)>maxD then maxD:=nops(Adj||b):b_max:=b:end if:end do:MassAB:=[op(MassAB),[a,b_max,maxD]];end if:end do:nMassAB:=nops(MassAB):maxB:=MassAB[1][3]: vA:=MassAB[1][1]; vB:=MassAB[1][2]:for i from 2 to nMassAB doif MassAB[i][3]>maxB then maxB:=MassAB[i][3]; vA:=MassAB[i][1]:vB:=MassAB[i][2]:end if;end do:return [[vA,vB],[ind||vA, ind||vB]]:end proc:> min_degree:=proc(MassDegree,n) #определение минимальной степениlocal min, i, nD:min:=n:nD:=nops(MassDegree):for i from 1 to nD doif MassDegree[i][2]<min then min:=MassDegree[i][2] end if:end do:return min:end proc:115omega:={}:for i from 1 to n doomega:={op(omega),i};end do:nw:=nops(omega):MassDegree:=[]: #массив степенейfor i from 1 to nw doAdj||i:={}: degree||i:=0:for j from 1 to nw doif A[i,j]=1 thenAdj||i:={op(Adj||i),j}:degree||i:=degree||i+1:end if:end do:MassDegree:=[op(MassDegree),[i,degree||i]]:end do:############ ОСНОВНАЯ ФУНКЦИЯ MS ########################> ms:=proc(G,MD,MS)local n, MinimumDegree, AB, Av, Bv, nG, i, w, NewG, MassDegNewG;local p, MaxSet, realization:local Connect, Comp, nComp, minComp, n_minComp, tau, MassDegC;local realization1, realization2, BBv,ms2MaxSet, ms2NewG;local ms2MassDegNewG, ms2nG, nAdv, N2:local v,massN2,t, N2sort,N,massN,Nsort,domin,j,notdomin1,NewGB;local MassDegNewGB,nGB,notdomin2,nMd,Adj,nMD,Adv:n:=nops(G): #количество вершин в текущем графеif n=0 thenreturn [0,MS]: end if:if n=1 thenMaxSet:=MS union G:116return [1,MaxSet]:end if:if n>1 then #вызываем функцию проверки на связностьConnect:=DFS(G,MD):if Connect[1]>1 then #если граф не связныйComp:=Connect[2]:nComp:=nops(Comp):#Выбираем наименьшую компоненту связностиminComp:=Comp[1]: n_minComp:=nops(minComp):for i from 2 to nComp dotau:=nops(Comp[i]):if tau<n_minComp then minComp:=Comp[i]; n_minComp:=tau:end if:end do:#формирование подграфа G-CNewG:=G minus minComp:#массив степеней и новые списки смежности для G-CMassDegNewG:=MassDegAdj(MD,NewG):#массив степеней и новые списки смежности для CMassDegC:=MassDegAdj(MD,minComp):#print(’НАЧАЛАСЬ_РЕАЛИЗАЦИЯ_MS_ДЛЯ_G-C’):realization1:=ms(NewG,MassDegNewG,MS):#для G-C#print(’НАЧАЛАСЬ_РЕАЛИЗАЦИЯ_MS_ДЛЯ_НАИМЕНЬШЕЙ_КОМПОНЕНТЫ_СВЯЗНОСТИ’):realization2:=ms(minComp,MassDegC,MS):#для min компоненты Creturn [realization1[1]+realization2[1],realization1[2] unionrealization2[2]]:else #если граф связный, т.е.
число компонент =1#print(’ВЫБОР_МИНИМАЛЬНОЙ_СТЕПЕНИ_ВЕРШИНЫ’):MinimumDegree:=min_degree(MD,n): #минимальная степень вершинAB:=choose_AB(MinimumDegree,MD): #выбранная пара вершин A и BAv:=AB[1][1]: ind||Av:=AB[2][1]:117Bv:=AB[1][2]: ind||Bv:=AB[2][2]:#Если минимальная степень вершины равна 1if MinimumDegree=1 then #print(’111111111111111111’);MaxSet:=MS union {Av}:NewG:=G minus ({Av} union MD[ind||Av][3]):MassDegNewG:=MassDegAdj(MD,NewG):realization:=ms(NewG,MassDegNewG,MaxSet):return [1+realization[1], realization[2]]:#завершение дляifMinimumDegree=1############################################################если минимальная степень вершины =2elif MinimumDegree=2 then #print(’2222222222222222’);BBv:=op(MD[ind||Av][3] minus {Bv}):#нужно определить уникальный номер вершины BBv в массиве MD,#для того чтобы потом найти множество Adj(BBv)nMD:=nops(MD):for i from 1 to nMD doif MD[i][1]=BBv then ind||BBv:=i: break: end if:end do:if A[Bv,BBv]=1 thenMaxSet:=MS union {Av}:NewG:=G minus ({Av} union MD[ind||Av][3]):MassDegNewG:=MassDegAdj(MD,NewG):realization:=ms(NewG,MassDegNewG,MaxSet):return [1+realization[1], realization[2]]:elseMaxSet:=MS union {Bv,BBv}:NewG:=G minus (({Bv} union MD[ind||Bv][3]) union({BBv} union MD[ind||BBv][3])):118MassDegNewG:=MassDegAdj(MD,NewG):#print(’НАЧАЛАСЬ_РЕАЛИЗАЦИЯ_ПЕРВОЙ_ЧАСТИ_МАКСИМУМА_d(A)=2’):realization1:=ms(NewG,MassDegNewG,MaxSet):#считываем список смежности из массива MassDegree,# для того, чтобы сформировать N2(A) - соседей соседей вершины Afor i from 1 to nMD dov:=MD[i][1]:Adj||v:=MD[i][3]:end do:ms2MaxSet:=MS union {Av}:ms2NewG:=G minus ({Av} union MD[ind||Av][3]):ms2MassDegNewG:=MassDegAdj(MD,ms2NewG):Adv:=MD[ind||Av][3]:nAdv:=nops(Adv):N2:={}:for i from 1 to nAdv dov:=Adv[i]: #Каждый сосед вершины AvN2:=N2 union Adj||v:end do:N2:=N2minus {Av}: # множество N2 - это множество соседей соседей#вершины Av, за исключением самой Av.N2:=[op(N2)]: # из множества N2 делаем список, чтобы можно было# отсортировать по степеням входящих вершинmassN2:=[]:ms2nG:=nops(ms2NewG):for t from 1 to ms2nG do #для всех вершин вif member(ms2MassDegNewG[t][1],N2) thenmassN2:=[op(massN2),ms2MassDegNewG[t]]:end if:новом подграфе119end do:N2sort:=sortS(massN2):N2:=N2sort[1]:#print(’НАЧАЛАСЬ_РЕАЛИЗАЦИЯ_ВТОРОЙ_ЧАСТИ_МАКСИМУМА_d(A)=2’):realization2:=ms2(ms2NewG,ms2MassDegNewG,ms2MaxSet,N2):if max(2+realization1[1],1+realization2[1])=2+realization1[1] thenreturn [2+realization1[1], realization1[2]]:elsereturn [1+realization2[1], realization2[2]]:end if;end if:#завершение для if MinimumDegree=2################################################elif MinimumDegree=3 then #print(’3333333333333333333333333333’);#для второй части максимума, для msMaxSet:=MS union {Av}:NewG:=G minus ({Av} union MD[ind||Av][3]):MassDegNewG:=MassDegAdj(MD,NewG):#print(’НАЧАЛАСЬ_РЕАЛИЗАЦИЯ_ПЕРВОЙ_ЧАСТИ_МАКСИМУМА_d(A)=3’):realization1:=ms(NewG,MassDegNewG,MaxSet):#для первой части максимума, для ms2ms2MaxSet:=MS:ms2NewG:=G minus {Av}:ms2MassDegNewG:=MassDegAdj(MD,ms2NewG):N:=[op(MD[ind||Av][3])]:massN:=[]:ms2nG:=nops(ms2NewG):for t from 1 to ms2nG do #для всех вершин вif member(ms2MassDegNewG[t][1],N) thenновом подграфе120massN:=[op(massN),ms2MassDegNewG[t]]:end if:end do:Nsort:=sortS(massN):N:=Nsort[1]:#print(’НАЧАЛАСЬ_РЕАЛИЗАЦИЯ_ВТОРОЙ_ЧАСТИ_МАКСИМУМА_d(A)=3’):realization2:=ms2(ms2NewG,ms2MassDegNewG,ms2MaxSet,N):if max(realization2[1],1+realization1[1])=1+realization1[1] thenreturn [1+realization1[1], realization1[2]]:elsereturn [realization2[1], realization2[2]]:end if;#завершение для if MinimumDegree=3##################################################elifMinimumDegree>3 thenif Domination(Av,Bv,MD,ind||Av,ind||Bv)=true then#print(’DOMINATION’):NewG:=G minus {Bv}:MassDegNewG:=MassDegAdj(MD,NewG):domin:=ms(NewG,MassDegNewG,MS):return [domin[1],domin[2]]:else#print(’NOT_DOMINATION’):#для первой части максимумаNewG:=G minus {Bv}:MassDegNewG:=MassDegAdj(MD,NewG):#print(’НАЧАЛАСЬ_РЕАЛИЗАЦИЯ_ПЕРВОЙ_ЧАСТИ_МАКСИМУМА_not_domin’):notdomin1:=ms(NewG,MassDegNewG,MS):#для второй части максимума121NewGB:=G minus ({Bv} union MD[ind||Bv][3]):MassDegNewGB:=MassDegAdj(MD,NewGB):MaxSet:=MS union {Bv}:#print(’НАЧАЛАСЬ_РЕАЛИЗАЦИЯ_ВТОРОЙ_ЧАСТИ_МАКСИМУМА’):notdomin2:=ms(NewGB,MassDegNewGB,MaxSet):if max(1+notdomin2[1],notdomin1[1])=1+notdomin2[1] thenreturn [1+notdomin2[1], notdomin2[2]]:elsereturn [notdomin1[1], notdomin1[2]]:end if;end if:#for if Domination(Av,Bv,MD,ind||A,ind||B)=trueend if: #for if MinimumDegree=1end if: #for Connect[1]>1end if: #for if n>1end proc: #for ms:########### ВСПОМОГАТЕЛЬНАЯ ФУНКЦИЯ MS2################> ms2:=proc(G,MD,MS,S)local nS,MaxSet,NewG,MassDegNewG,nG,i,w,realization,NewS,j,realiz2;local E,nE,si,SS,sjk,sj,sk,S_set,realiz3:local nMD,v,continue,p,realiz_vertex,NewG1,MassDegNewG1,NewS1;local massNewS1,nG1,t,NewSsort1,MaxSet1,realiz_max1,NewG2:local MassDegNewG2,NewS2,massNewS2,nG2,massNewS,NewSsort2;local realiz_max2,P,MaxSet2,nGG,exist,NewSsort,realization1:nS:=nops(S):if nS<=1 then return [0,MS]:elif nS=2 thenif A[S[1],S[2]]=1 then return [0,MS]:elsenMD:=nops(MD):122for i from 1 to nMD dov:=MD[i][1]:Adj||v:=MD[i][3]:end do:MaxSet:=MS union {S[1],S[2]}:NewG:=G minus (({S[1]} union Adj||(S[1])) union({S[2]} union Adj||(S[2]))):MassDegNewG:=MassDegAdj(MD,NewG):realization:=ms(NewG,MassDegNewG,MaxSet):return [2+realization[1],realization[2]]:end if: #for if A[S[1],S[2]]=1elif nS=3 then#в этом случае очень важна сортировка множества S по Adj(v)!nMD:=nops(MD):for i from 1 to nMD dov:=MD[i][1]:Adj||v:=MD[i][3]:end do:if nops(Adj||(S[1]))=0 thenNewG:=G minus {S[1]}:MassDegNewG:=MassDegAdj(MD,NewG):MaxSet:=MS union {S[1]}:NewS:=[]:for j from 2 to nS doNewS:=[op(NewS),S[j]]:end do:realiz2:=ms1(NewG,MassDegNewG,MaxSet,NewS):return [1+realiz2[1],realiz2[2]]:else #print(’Construct_E’):123E:=[]; # множество ребер среди элементов Sfor i from 1 to nS-1 dofor j from i+1 to nS doif A[S[i],S[j]]=1 then E:=[op(E),{S[i],S[j]}]; end if:end do:end do:nE:=nops(E):if nE<>0 thenif nE=3 thenreturn [0,MS]:elif nE=2 thennMD:=nops(MD):for i from 1 to nMD dov:=MD[i][1]:Adj||v:=MD[i][3]:end do:si:=E[1] intersect E[2]:SS:={op(S)}:sjk:=SS minus si:sj:=sjk[1]: sk:=sjk[2]:MaxSet:=MS union {sj,sk}:NewG:=G minus (({sj} union Adj||sj) union ({sk} union Adj||sk)):MassDegNewG:=MassDegAdj(MD,NewG):realization:=ms(NewG,MassDegNewG,MaxSet):return [2+realization[1], realization[2]]:elif nE=1 thennMD:=nops(MD):for i from 1 to nMD dov:=MD[i][1]:124Adj||v:=MD[i][3]:end do:S_set:={op(S)}:sk:=op(S_set minus {E[1][1],E[1][2]}):NewG:=G minus ({sk} union Adj||sk):MassDegNewG:=MassDegAdj(MD,NewG):MaxSet:=MS union {sk} :NewS:=[E[1][1],E[1][2]]:realiz3:=ms1(NewG,MassDegNewG,MaxSet,NewS):return [1+realiz3[1],realiz3[2]]:end if: #for if nE=3else #print(’constructN’);nMD:=nops(MD):for i from 1 to nMD dov:=MD[i][1]:Adj||v:=MD[i][3]:end do:continue:=true: P:={}:for i from 1 to nS-1dofor j from i+1 to nS doP:=(Adj||(S[i]) intersect Adj||(S[j]));if nops(P)>0 then continue:=false: break; end if:end do:if continue=false then break: end if:end do:if nops(P)<>0 thenv:=P[1]:NewG:=G minus {v}:MassDegNewG:=MassDegAdj(MD,NewG):125nMD:=nops(MassDegNewG):for i from 1 to nMD dov:=MassDegNewG[i][1]:Adj||v:=MD[i][3]:end do:#проводим сортировку множества SNewS:=S:ns:=nops(NewS):for i from 1 to ns dofor j from 1 to ns-i doif nops(Adj||(NewS[j]))>nops(Adj||(NewS[j+1])) thentmp:=NewS[j+1]: NewS[j+1]:=NewS[j]: NewS[j]:=tmp:end if:end do:end do:realiz_vertex:=ms2(NewG,MassDegNewG,MS,NewS);return [realiz_vertex[1],realiz_vertex[2]];elseif nops(Adj||(S[1]))=1 thenNewG:=G minus ({S[1]} union Adj||(S[1])):MassDegNewG:=MassDegAdj(MD,NewG):NewS1:=[S[2],S[3]]:massNewS1:=[]:nGG:=nops(NewG):for t from 1 to nGG doif member(MassDegNewG[t][1],NewS1) thenmassNewS1:=[op(massNewS1),MassDegNewG[t]]:end if:end do:126NewSsort1:=sortS(massNewS1):NewS1:=NewSsort1[1]:MaxSet1:=MS union {S[1]}:realiz_vertex:=ms1(NewG,MassDegNewG,MaxSet1,NewS1);return [1+realiz_vertex[1],realiz_vertex[2]];else #print(’MAX_RETURN’):#входные данные для первой части максимума#формирование подграфа G-N(v)NewG1:=G minus ({S[1]} union Adj||(S[1])):#формирование массива степеней и списков смежности для G-N(v)MassDegNewG1:=MassDegAdj(MD,NewG1):#формирование нового отсортированного множества S-s1NewS1:=[S[2],S[3]]:massNewS1:=[]:nG1:=nops(NewG1):for t from 1 to nG1 doif member(MassDegNewG1[t][1],NewS1) thenmassNewS1:=[op(massNewS1),MassDegNewG1[t]]:end if:end do:NewSsort1:=sortS(massNewS1):NewS1:=NewSsort1[1]:MaxSet1:=MS union {S[1]}:realiz_max1:=ms1(NewG1,MassDegNewG1,MaxSet1,NewS1);#входные данные для второй части максимума#формирование подграфа G-N(s2)-N(s3)-s1NewG2:=G minus ({S[1],S[2],S[3]} union Adj||(S[2])union Adj||(S[3])):#массив степеней и списки смежности для G-N(s2)-N(s3)-s1127MassDegNewG2:=MassDegAdj(MD,NewG2):#формирование нового отсортированного множества N(s1)NewS2:=[op(Adj||(S[1]))]:massNewS2:=[]:nG2:=nops(NewG2):for t from 1 to nG2 doif member(MassDegNewG2[t][1],NewS2) thenmassNewS:=[op(massNewS2),MassDegNewG2[t]]:end if:end do:NewSsort2:=sortS(massNewS2):NewS2:=NewSsort2[1]:MaxSet2:=MS union {S[2],S[3]}:realiz_max2:=ms2(NewG2,NewMD2,MaxSet2,NewS2);if max(1+realiz_max1[1],2+realiz_max2[1])=1+realiz_max1[1] thenreturn [1+realiz_max1[1],realiz_max1[2]]:elsereturn [2+realiz_max2[1],realiz_max2[2]]:end if:end if: #for if d(s1)=1end if: #for if nops(P)<>0end if: #for if nE<>0end if: #for if nops(Adj||(S[1]))=0elif nS=4 thennMD:=nops(MD):exist:=0:for i from 1 to nMD doif nops(MD[i][3])<=3 then exist:=1: break: end if:end do:128if exist=1 thenrealization:=ms(G,MD,MS):return [realization[1],realization[2]]:else#####СЛУЧАЙ |S|=4 & не существует v: d(v)<=3 :НАЧАЛО####for i from 1 to nMD dov:=MD[i][1]:Adj||v:=MD[i][3]:end do:#print(’ВХОДНЫЕ_ДАННЫЕ_ДЛЯ_ПЕРВОЙ_ЧАСТИ_МАКСИМУМА’):#формирование подграфа G-N(s1)NewG:=G minus ({S[1]} union Adj||(S[1]) ):#массив степеней и списки смежности для G-N(s1)MassDegNewG:=MassDegAdj(MD,NewG):MaxSet:=MS union {S[1]}:realization:=ms(NewG,MassDegNewG,MaxSet):#print(’ВХОДНЫЕ_ДАННЫЕ_ДЛЯ_ВТОРОЙ_ЧАСТИ_МАКСИМУМА’):#формирование подграфа G-s1NewG1:=G minus {S[1]}:#формирование массива степеней и списков смежности для G-s1MassDegNewG1:=MassDegAdj(MD,NewG1):#формирование нового отсортированного множества S-s1NewS1:=[S[2],S[3],S[4]]:massNewS1:=[]:nG1:=nops(NewG1):for t from 1 to nG1 doif member(MassDegNewG1[t][1],NewS1) thenmassNewS1:=[op(massNewS1),MassDegNewG1[t]]:end if:129end do:NewSsort:=sortS(massNewS1):NewS1:=NewSsort[1]:realization1:=ms2(NewG1,MassDegNewG1,MS,NewS1):if max(1+realization[1],realization1[1])=1+realization[1] thenreturn [1+realization[1],realization[2]];elsereturn [realization1[1],realization1[2]];end if:#######СЛУЧАЙ |S|=4 & не существует v: d(v)<=3 : КОНЕЦ #######end if: #for if exist=1elif nS>=5 then########СЛУЧАЙ ms2: |S|>=5: НАЧАЛО #############realization:=ms(G,MD,MS):return [realization[1],realization[2]]:######СЛУЧАЙ ms2: |S|>=5: КОНЕЦ ##############end if: #for nS<=1end proc:########## ВСПОМОГАТЕЛЬНАЯ ФУНКЦИЯ MS1 #########G -множество вершин подграфа,MD-множество степеней вершин,#MS-независимое множество,#S-вспомогательное множество состоит только из двух элементов> ms1:=proc(G,MD,MS,S)local nS,realiz1,nMD,i,v,E,F,NewG,MassDegNewG,MaxSet,realizEF;local ADJ,nADJ,kolvo,kol,realizNEF,caseDS,realization,NewG1;local MassDegNewG1,MaxSet1,realization1,NewS1;local massNewS1,nG1,t,NewSsort:nMD:=nops(MD):for i from 1 to nMD do130v:=MD[i][1]:Adj||v:=MD[i][3]:end do:if nops(Adj||(S[1]))<=1 then #print (’d(s1)<=1’);########### СЛУЧАЙ d(s1)<=1: НАЧАЛО#############realiz1:=ms(G,MD,MS): return [realiz1[1],realiz1[2]]:########### СЛУЧАЙ d(s1)<=1: КОНЕЦ##############elif A[S[1],S[2]]=1 then########### СЛУЧАЙ edge(s1,s2): НАЧАЛО ##########if nops(Adj||(S[1]))<=3 then########### СЛУЧАЙ d(s1)<=3: НАЧАЛО ###########caseDS:=ms(G,MD,MS):return [caseDS[1],caseDS[2]]:######### СЛУЧАЙ d(s1)<=3: КОНЕЦ ###########else #print(’d(s1)>3’):######## СЛУЧАЙ d(s1)>3: НАЧАЛО ##############print(’ВХОДНЫЕ_ДАННЫЕ_ДЛЯ_ПЕРВОЙ_ЧАСТИ_МАКСИМУМА’):#формирование подграфа G-N(s1)NewG:=G minus ({S[1]} union Adj||(S[1]) ):#формирование массива степеней и списков смежности для G-N(s1)MassDegNewG:=MassDegAdj(MD,NewG):MaxSet:=MS union {S[1]}:#print(’НАЧАЛАСЬ_РЕАЛИЗАЦИЯ_ПЕРВОЙ_ЧАСТИ_МАКСИМУМА_d(s1)>3’):realization:=ms(NewG,MassDegNewG,MaxSet):#print(’ВХОДНЫЕ_ДАННЫЕ_ДЛЯ_ВТОРОЙ_ЧАСТИ_МАКСИМУМА’):#формирование подграфа G-N(s2)NewG1:=G minus ({S[2]} union Adj||(S[2]) ):#формирование массива степеней и списков смежности для G-N(s2)MassDegNewG1:=MassDegAdj(MD,NewG1):131MaxSet1:=MS union {S[2]}:#print(’НАЧАЛАСЬ_РЕАЛИЗАЦИЯ_ВТОРОЙ_ЧАСТИ_МАКСИМУМА_d(s1)>3’):realization1:=ms(NewG1,MassDegNewG1,MaxSet1):if max(realization[1],realization1[1])=realization[1] thenreturn [realization[1]+1,realization[2]];elsereturn [realization1[1]+1,realization1[2]];end if:####СЛУЧАЙ d(s1)>3:КОНЕЦ#########################end if:#for if nops(Adj||(S[1]))<=3#######СЛУЧАЙ edge(s1,s2): КОНЕЦ##################elif nops( Adj||(S[1]) intersect Adj||(S[2]) )<>0 then#########СЛУЧАЙ N(s1)_intersect_N(s2)<>0:НАЧАЛО#######print(’НОВЫЕ_ВХОДНЫЕ_ДАННЫЕ_ДЛЯ_MS1’):#формирование подграфа G-(N(s1)intersectN(s2))NewG:=G minus (Adj||(S[1]) intersect Adj||(S[2])):#массив степеней и списки смежности для G-(N(s1)intersectN(s2))MassDegNewG:=MassDegAdj(MD,NewG):realization:=ms1(NewG,MassDegNewG,MS,S):return [realization[1],realization[2]];#### СЛУЧАЙ N(s1)_intersect_N(s2)<>0: КОНЕЦ#####elif nops(Adj||(S[2]))=2 then#####СЛУЧАЙ d(s2)=2: НАЧАЛО##########E:=(Adj||(S[1]))[1]:F:=(Adj||(S[1]))[2]:if A[E,F]=1 then#формирование подграфа G-N(s1)NewG:=G minus ({S[1]} union Adj||(S[1]) ):#формирование массива степеней и списков смежности для G-N(s1)132MassDegNewG:=MassDegAdj(MD,NewG):MaxSet:=MS union {S[1]}:realizEF:=ms(NewG,MassDegNewG,MaxSet):return [1+realizEF[1],realizEF[2]]:elseADJ:=(Adj||E union Adj||F) minus {S[1]}:nADJ:=nops(ADJ):kolvo:=0:for i from 1 to nADJ doif member(ADJ[i],Adj||(S[2])) thenelsekolvo:=kolvo+1:break:end if:end do:if kolvo=nADJ then#формирование подграфа G-N(s1)-N(s2)NewG:=G minus ({S[1],S[2]} union Adj||(S[1]) union Adj||(S[2])):#массив степеней и списки смежности для G-N(s1)-N(s2)MassDegNewG:=MassDegAdj(MD,NewG):MaxSet:=MS union {E,F,S[2]}:realizNEF:=ms(NewG,MassDegNewG,MaxSet):return [3+realizNEF[1],realizNEF[2]]:else#print(’ВХОДНЫЕ_ДАННЫЕ_ДЛЯ_ПЕРВОЙ_ЧАСТИ_МАКСИМУМА’):#формирование подграфа G-N(s1)NewG:=G minus ({S[1]} union Adj||(S[1]) ):#формирование массива степеней и списков смежности для G-N(s1)MassDegNewG:=MassDegAdj(MD,NewG):MaxSet:=MS union {S[1]}:#print(’НАЧАЛАСЬ_РЕАЛИЗАЦИЯ_ПЕРВОЙ_ЧАСТИ_МАКСИМУМА):133realization:=ms(NewG,MassDegNewG,MaxSet):#print(’ВХОДНЫЕ_ДАННЫЕ_ДЛЯ_ВТОРОЙ_ЧАСТИ_МАКСИМУМА’):#формирование подграфа G-N(E)-N(F)-N(s2)NewG1:=G minus ({E,F,S[2]} union Adj||E union Adj||Funion Adj||(S[2])):#массив степеней и списки смежности для G-N(E)-N(F)-N(s2)MassDegNewG1:=MassDegAdj(MD,NewG1):MaxSet1:=MS union {E,F,S[2]}:#print(’НАЧАЛАСЬ_РЕАЛИЗАЦИЯ_ВТОРОЙ_ЧАСТИ_МАКСИМУМА):realization1:=ms(NewG1,MassDegNewG1,MaxSet1):if max(1+realization[1],3+realization1[1])=1+realization[1] thenreturn [1+realization[1],realization[2]];elsereturn [3+realization1[1],realization1[2]];end if:end if: #for if kol=nADJend if: #for if A[E,F]=1####СЛУЧАЙ d(s2)=2: КОНЕЦ###################elif nops(Adj||(S[1]))>1then#####СЛУЧАЙ: последний return ms1: НАЧАЛО ###########print(’ВХОДНЫЕ_ДАННЫЕ_ДЛЯ_ПЕРВОЙ_ЧАСТИ_МАКСИМУМА’):#формирование подграфа G-N(2)NewG:=G minus ({S[2]} union Adj||(S[2]) ):#формирование массива степеней и списков смежности для G-N(s2)MassDegNewG:=MassDegAdj(MD,NewG):MaxSet:=MS union {S[2]}:#print(’НАЧАЛАСЬ_РЕАЛИЗАЦИЯ_ПЕРВОЙ_ЧАСТИ_МАКСИМУМА’):realization:=ms(NewG,MassDegNewG,MaxSet):#print(’ВХОДНЫЕ_ДАННЫЕ_ДЛЯ_ВТОРОЙ_ЧАСТИ_МАКСИМУМА’):134#формирование подграфа G-N(s1)-s2NewG1:=G minus ({S[1],S[2]} union Adj||(S[1])):#массив степеней и списки смежности для G-N(s1)-s2MassDegNewG1:=MassDegAdj(MD,NewG1):#формирование нового отсортированного множества N(s2)NewS1:=[op(Adj||(S[2]))]:massNewS1:=[]:nG1:=nops(NewG1):for t from 1 to nG1 doif member(MassDegNewG1[t][1],NewS1) thenmassNewS1:=[op(massNewS1),MassDegNewG1[t]]:end if:end do:NewSsort:=sortS(massNewS1):NewS1:=NewSsort[1]:MaxSet1:=MS union {S[1]}:#print(’НАЧАЛАСЬ_РЕАЛИЗАЦИЯ_ВТОРОЙ_ЧАСТИ_МАКСИМУМА’):realization1:=ms2(NewG1,MassDegNewG1,MaxSet1,NewS1):if max(realization[1],realization1[1])=realization[1] thenreturn [realization[1]+1,realization[2]];elsereturn [realization1[1]+1,realization1[2]];end if:######СЛУЧАЙ: последний return ms1: КОНЕЦ ########end if:#for if nops(Adj||(S[1]))<=1end proc: #for ms1MaximumSet:=ms(G,MD,MS):return MaximumSet:end proc: #for Robson135ПРИЛОЖЕНИЕ 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
