当前位置：网站首页>CDs simulation of minimum dominating set based on MATLAB
CDs simulation of minimum dominating set based on MATLAB
2022-07-27 00:27:00 【I love c programming】
Catalog
3. Preview of some simulation drawings
4. Source code acquisition method
1. Algorithm description
The definition of dominating set is as follows ： Given an undirected graph G =（V , E）, among V It's a collection , E It's an edge set , call V A subset of S It is called a dominating set if and only if for V-S Any point in v, There are S A point in u, bring (u, v) ∈E. For Graphs G = (V, E) Come on , The minimum dominating set refers to the minimum dominating set from V Take as few points as possible to form a set , bring V The rest of the points in are connected by edges to the points taken out . in other words , set up V' Is a dominating set of graphs , Then for any vertex in the graph u , Or belong to a collection V', Or with V' The vertices in the are adjacent to each other . stay V' After removing any element from V' No longer a dominating set , Then dominating set V' Is a minimal dominating set . call G The dominating set with the least number of vertices in all dominating sets is the minimum dominating set , The number of vertices in the minimum dominating set is called dominating number .
The minimum dominating set (minimal dominating set)： For Graphs G=(V,E) Come on , set up V' The picture is G A dominating set of , Then for any vertex in the graph u, Or belong to a collection V', Or with V' The vertices in are connected . stay V' After removing any element from V' No longer a dominating set , Then dominating set V' Is a minimal dominating set . call G The dominating set with the least number of vertices in all dominating sets is the minimum dominating set , The number of vertices in the minimum dominating set is called dominating number .
Properties of the minimum dominating set ：
1） The problem of finding the minimum dominating set is proved to belong to NP Problem completely , That is, the input scale of a given problem domain , At present, there is not enough means to prove that the problem can be determined to be solved in polynomial time .
2） Within n In an arbitrary graph of points , If the degree of any point is greater than or equal to 3, Then the minimum dominating set of the graph is less than or equal to 3n/8.
3） For special graphs , Such as tree , You can use greed or dp The best way to solve the problem .
2. Partial procedure
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)
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<temp1+temp2
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
end3. Preview of some simulation drawings
4. Source code acquisition method
Get the way 1：
Click the download link ：
be based on matlab The minimum dominating set of CDS Simulation + Program operation video
Access method 2：
Blog resource item , Search for resources with the same name as blog .
Access method 3：
If the download link fails , Blogger wechat contact .
A37
边栏推荐
猜你喜欢
7_主成分分析法（Principal Component Analysis）
LeetCode——链表篇
13_集成学习和随机森林(Ensemble Learning and Random Forests)
Recbole use 1
Drawing warehouse Tsai
Leetcode - hash table
TypeScript（tsconfig.json）
Relationship between limit, continuity, partial derivative and total differential of multivariate function (learning notes)
画冲击函数
4-4 object lifecycle
随机推荐
Oracle data guard service, process and protection mode
2022-07-17:1, 2, 3... N-1, N, n+1, n+2... In this sequence, only one number has repetition (n). This sequence is unordered. Find the repeated number n. This sequence is ordered. Find the repeated numb
Codeforces d.constructing the array (priority queue)
Tree and binary tree (learning notes)
Halloween treatments (drawer principle)
Iptables prevent nmap scanning and binlog
爬虫中Request属性
Codeforces B. Orac and Models (dp)
C and pointer Chapter 18 runtime environment 18.2 interface between C and assembly language
爬虫解析网页的 对象.元素名方法
Training team lpoj round10 e Jumping Frog
20220720 toss deeplobcut2
4-4 object lifecycle
Anaconda = > pycharm=> CUDA=> cudnn=> pytorch environment configuration
94. Middle order traversal of binary tree
Leetcode topic - array
Sliding window problem summary
Dynamic memory management
卷积神经网络——LeNet（pytorch实现）
13_ Ensemble learning and random forests