Labelling nodes for undirected graph

1 次查看(过去 30 天)
I have the following issue in my code for L(2,1)-labelling problem. L(2,1)-labelling is to label positive integers to the nodes of graph such that
1) adjacent nodes receive value which differ by at least 2.
2) If the distance between the two nodes is 2 the difference between these nodes are 1.
my issue in the second loop
%this codes related to Njud Alotaibi (copy right)
function labellingcycles
%-----creating a graph-------
s=[1 1 2 3 4];
t=[2 3 4 5 5];
G=graph(s,t);
plot(G);
%-----Sets--------
S=[0,randperm(4)];
Ver=[];
x=[];
% the first for loop here for first random labelling for the nodes
for i=1:5
Ver(i)=S(i);
Ver(:, i) = Ver(i);
end
Ver = Ver(:, 1:5)
% the second for loop to test the values in Ver set does it meet the L(2,1)-labelling problem or not and
% store it in x set
for j=1:5
% If conditions on the values should differen from their neighbors values and %
% the difference between values should be 2 or more
if (Ver(j)~= Ver(neighbors(G,j))) & (abs(Ver(j)-Ver(neighbors(G,j)))>=2)
x(j)=Ver(j);
x(:, j) = x(j);
% if does not meet the condition i need to change the value to
% meet the condition but how
else
break % break becuse i just need to change the value that does not meet the condition
end
end
x = x(:, 1:5)
end

回答(1 个)

ag
ag 2023-9-29
Hi Njud,
I understand that you need to label your graph as per the below stated conditions:
  1. Value for the adjacent nodes should differ by at least 2.
  2. Value for nodes with distance 2, should differ by 1.
To do so, you will have to use recursion or stack for implementing a graph traversal algorithm(BFS should be of help).
Please refer to the following documentation of “bfsearch, which is an in-built function for BFS,
Hope this helps!
Best Regards,
Aryan Gupta

类别

Help CenterFile Exchange 中查找有关 Graph and Network Algorithms 的更多信息

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by