基于matlab的最小支配集CDS仿真

目录

1.算法描述

2.仿真效果预览

3.MATLAB部分代码预览

4.完整MATLAB程序

---

1.算法描述

       支配集的定义如下：给定无向图G =（V , E）,其中V是点集， E是边集， 称V的一个子集S称为支配集当且仅当对于V-S中任何一个点v, 都有S中的某个点u, 使得(u, v) ∈E。对于图G = (V, E) 来说,最小支配集指的是从 V 中取尽量少的点组成一个集合, 使得 V 中剩余的点都与取出来的点有边相连.也就是说,设 V' 是图的一个支配集,则对于图中的任意一个顶点 u ,要么属于集合 V', 要么与 V' 中的顶点相邻. 在 V' 中除去任何元素后 V' 不再是支配集, 则支配集 V' 是极小支配集.称G 的所有支配集中顶点个数最少的支配集为最小支配集,最小支配集中的顶点个数称为支配数.

       最小支配集(minimal dominating set)：对于图G=(V,E)来说，设V'是图G的一个支配集，则对于图中的任意一个顶点u，要么属于集合V'，要么与V'中的顶点相连。在V'中除去任何元素后V'不再是支配集，则支配集V'是极小支配集。称G中所有支配集中顶点个数最少的支配集为最小支配集，最小支配集中的顶点个数称为支配数。

最小支配集的性质：

1）求最小支配集问题被证明属于NP完全问题,即对于给定问题域的输入规模,目前尚无足够的手段证明该问题能够被判定在多项式时间内求解。

2）在含n个点的任意图中，若任意点的度大于等于3，则该图的最小支配集小于等于3n/8。

3）对于特殊图，如树，可使用贪心或dp的方法解决问题。

贪心策略
       首先选择一点为树根,再按照深度优先遍历得到遍历序列,按照所得序列的反向序列的顺序进行贪心,对于一个即不属于支配集也不与支配集中的点相连的点来说,如果他的父节点不属于支配集,将其父节点加入到支配集

具体实现
1.设整型数组dfn,fa,布尔数组vis,st。dfn[i]表示dfs中出现的第i个节点，fa[i]表示dfs中节点i的父节点，vis[i]-false表示节点i不属于支配集也不与支配集中的点相连，st[i]-true表示节点i在MDS中。

2.建图（邻接表）。

3.dfs一遍树，确定dfn,fa。

4.dfn逆序查找，确定vis,st,同时得出MDS。

2.仿真效果预览

matlab2013B仿真结果如下：

3.MATLAB部分代码预览

tempall=1;
temp_self=Neighbor_hop2(:,:,1)*0;%2 hop's information
 
for i=1:Node_Num
 
    if Color_N(i,1)==4||Color_N(i,1)==2
        temp_self=temp_self*0;%2 hop's information
        
        %node i formulation the 2_hop connected graph
        for n=1:d1(i,1)
            temp2=d1(d1(i,n+1),1);
            temp_count=1;
            state=1;
            for m=2:temp2+1
                temp_self(n,1)=d1(i,n+1);
                temp=Neighbor_hop2(n,m,i);
                state=1;
                for p=1:d1(i,1)
                    if temp==i
                        state=0;
                        break;
                    elseif temp==d1(i,p+1)
                        state=0;
                        break;
                    end
                end
                if state==1
 
                    temp_count=temp_count+1;
                    temp_self(n,temp_count)=temp;
 
                end
            end
        end
        
        
        
        
%%        
        %chose some node in two_hops of node i to connect the2_hop's dominating nodes
        Already_handle=zeros(Max_Degree*Max_Degree,1);
        Already_handle_result=Already_handle;
        handle_count=0;
        for n=1:d1(i,1)
            if temp_self(n,1)==0;
                break;                
            end
            for m=2:Max_Degree+1
                if temp_self(n,m)==0
                    break;
                end
                if Color_N(temp_self(n,m),1)==4||Color_N(temp_self(n,m),1)==2
                    state=0;
                    for p=1:handle_count
                        if Already_handle(p,1)==temp_self(n,m)
                            state=1;
                            if Already_handle_result(p,1)==0
                                break;
                            else
                                if Color_N(temp_self(n,1))==2||Color_N(temp_self(n,1))==4
                                    Already_handle_result(p,1)=0;
                                    break;
                                elseif  d1(temp_self(n,1),1)>d1(Already_handle_result(p,1),1)
                                    Already_handle_result(p,1)=temp_self(n,1);
                                elseif d1(temp_self(n,1),1)==d1(Already_handle_result(p,1),1)
                                    if temp_self(n:1)
                                        Already_handle_result(p,1)=temp_self(n,1);
                                    end
                                end
                            end
                        end
                    end
                    if state==0;
                        if Color_N(temp_self(n,1))==2||Color_N(temp_self(n,1))==4
                            Already_handle(handle_count+1,1)=temp_self(n,m);
                            Already_handle_result(handle_count+1,1)=0;
                            handle_count=handle_count+1;
                        else
                            Already_handle(handle_count+1,1)=temp_self(n,m);
                            Already_handle_result(handle_count+1,1)=temp_self(n,1);
                            handle_count=handle_count+1;
                        end
                    end
                end
            end
        end
        
        for n=1:handle_count
           if  Already_handle_result(n,1)==0
              
           else
               Color_N(Already_handle_result(n,1))=6;
               
               temp1=Already_handle_result(n,1);
               temp2=Already_handle(n,1);
               plot([Posxy(i,1),Posxy(temp1,1)],[Posxy(i,2),Posxy(temp1,2)],'o-.c')
               plot([Posxy(temp2,1),Posxy(temp1,1)],[Posxy(temp2,2),Posxy(temp1,2)],'o-.c')
               
           end
        end
        
%%        
        %node i formulation the 3_hop connected graph
       Already_handle2=zeros(Max_Degree*Max_Degree*Max_Degree,1);
       handle_count2=0;
       Already_handle2_reult=zeros(Max_Degree*Max_Degree*Max_Degree,2);
       
       for n=1:d1(i,1)
           if temp_self(n,1)==0;
                break;                
           end
           for m=2:Max_Degree+1
                if temp_self(n,m)==0
                    break;
                end
                for p=1:d1(temp_self(n,m),1)
                    
                    temp_node=d1(temp_self(n,m),p+1);
                    
                    if Color_N(temp_node)==2||Color_N(temp_node)==4
                        
                        state_in=0;
                        
                        % it is one of 2hops neighboor of nod i if state_in==1;
                        for n2=1:d1(i,1)
                            if temp_self(n2,1)==0
                                break;
                            end
                            if temp_self(n2,1)==temp_node
                                state_in=1;
                                break;
                            end
                            for m2=2:Max_Degree+1
                                if temp_self(n2,m2)==0
                                    break;
                                end
                                if temp_self(n2,m2)==temp_node
                                    state_in=1;
                                    break;
                                end
                            end
                            if state_in==1
                                break;
                            end
                        end
                        
                        % it is one of 2hops neighboor of nod i if
                        % state_in==0, then we get the rout from there.
                        if state_in==0
                            
                            state_in2=0;
                            
                            for q=1:handle_count2
                                
                                if temp_node==Already_handle2(q,1)
                                    
                                    state_in2=1;
                                    
                                    temp1=Already_handle2_reult(q,1);
                                    temp2=Already_handle2_reult(q,2);
                                    temp3=temp_self(n,1);
                                    temp4=temp_self(n,m);
                                    
                                    if temp1==0
                                        break;
                                        %do nothing
                                    else
                                        if Color_N(temp3,1)==2||Color_N(temp3,1)==4||Color_N(temp4,1)==2||Color_N(temp4,1)==4
                                            Already_handle2_reult(q,1)=0;
                                            Already_handle2_reult(q,2)=0;
                                        else
                                            a=d1(temp3,1)+d1(temp4,1);
                                            b=d1(temp1,1)+d1(temp2,1);
                                            if a>b
                                                Already_handle2_reult(q,1)=temp3;
                                                Already_handle2_reult(q,2)=temp4;
                                            elseif a==b
                                                if temp3+temp4
                                                    Already_handle2_reult(q,1)=temp3;
                                                    Already_handle2_reult(q,2)=temp4;
                                                else
                                                    %do nothing
                                                end
                                            end
                                        end
                                    end
                                    
                                end
                                
                                if state_in2==1
                                   break; 
                                end
                                
                            end
                            
                            if state_in2==0;
                                handle_count2=handle_count2+1;
                                Already_handle2(handle_count2,1)=temp_node;
                                temp1=temp_self(n,1);
                                temp2=temp_self(n,m);
                                if  Color_N(temp1,1)==2||Color_N(temp1,1)==4||Color_N(temp2,1)==2||Color_N(temp2,1)==4
                                    Already_handle2_reult(handle_count2,1)=0;
                                    Already_handle2_reult(handle_count2,2)=0;
                                else
                                    Already_handle2_reult(handle_count2,1)=temp_self(n,1);
                                    Already_handle2_reult(handle_count2,2)=temp_self(n,m);
                                end
                            end
                            
                        end
                        
                    end
                    
                end
                
           end
       end
       
       for n=1:handle_count2
           if  Already_handle2_reult(n,1)==0
 
           else
               Color_N(Already_handle2_reult(n,1),1)=7;
               Color_N(Already_handle2_reult(n,2),1)=7;
               
               temp1=Already_handle2_reult(n,1);
               temp2=Already_handle2_reult(n,2);
               temp3=Already_handle2(n,1);
               plot([Posxy(i,1),Posxy(temp1,1)],[Posxy(i,2),Posxy(temp1,2)],'o-.b')
               plot([Posxy(temp2,1),Posxy(temp1,1)],[Posxy(temp2,2),Posxy(temp1,2)],'o-.b')
               plot([Posxy(temp2,1),Posxy(temp3,1)],[Posxy(temp2,2),Posxy(temp3,2)],'o-.b')
 
           end
       end
       
    end
end
A_037

4.完整MATLAB程序

matlab源码说明_我爱C编程的博客-CSDN博客

V