当前位置：网站首页>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
边栏推荐
- C and pointer Chapter 18 runtime environment 18.2 interface between C and assembly language
- 解析网页的完整回顾
- 查看 Anaconda 创建环境的位置
- Leetcode topic - array
- [PCB open source sharing] stc8a8k64d4 development board
- Today's 20220719 toss deeplobcut
- Search engine hijacking of black hat SEO
- Complete review of parsing web pages
- C and pointer Chapter 18 runtime environment 18.1 judgment of runtime environment
- MySql
猜你喜欢
5_线性回归(Linear Regression)
Matlab simulation of inverted pendulum control system based on qlearning reinforcement learning
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
CCPD data set processing (target detection and text recognition)
Leetcode - hash table
View where Anaconda created the environment
Relationship between limit, continuity, partial derivative and total differential of multivariate function (learning notes)
MySQL optimization
动态联编和静态联编、以及多态
20220720折腾deeplabcut2
随机推荐
[Qt]容器类、迭代器、foreach关键字
Class and object notes I
Complete review of parsing web pages
100. Same tree
94. Middle order traversal of binary tree
爬虫解析网页的 对象.元素名方法
13_ Ensemble learning and random forests
RESNET paper interpretation and code implementation (pytorch)
Arcgis和Cass实现断面展高程点
Flink SQL (II) Kafka connector
Anaconda = > pycharm=> CUDA=> cudnn=> pytorch environment configuration
Iptables prevent nmap scanning and binlog
Signal and system learning zero input response
深度学习调参技巧
Arthas quick start
Codeforces B. Orac and Models (dp)
CCPD data set processing (target detection and text recognition)
Configure deeplobcut2 with your head covered
UNET notes
9_ Logistic regression