Program to find connected and non-isomorphic graphs

2 次查看（过去 30 天）
Gamma1990
Gamma1990 2021-10-1
评论： Gamma1990 2021-10-2
Hello,
I want to determine the connectivity and isomorphism of the graph and save the connected unlabeled graph in the cell array.
In order to do this, I'm trying to make the program that determines connected and non-isomorphic graphs by defining adjacency matrix.
However, It doesn't seem to be working properly.
Although it can determine adjacency matrix that are connected graphs, it cannot determine adjacency matrix that are non-isomorphic graphs.
Here is the code.
% setting
nd = 4; % Number of nodes
eg = nd*(nd-1)/2; % Maximum number of edges
egs = dec2bin(0:2^eg-1)-'0'; % Combinations of edges
tri = find(triu(ones(nd), 1)); % Index of the upper triangle of the adjacency matrix
adj = zeros(nd); % Preallocation of adjacency matrix
adjbefore = zeros(nd); % Preallocation of adjacency matrix
data = cell(1, 1); % Preallocation of the cell array
% Loop to find the first graph and save it in the cell array
index = 1;
for i = 1:2^eg % Repeat for several combinations of edges
adj(tri) = egs(i,:); % Assign combination to the upper triangle
G = graph(adj, 'upper'); % Defining a Graph
if all(~diff(conncomp(G))) % If it's connected
data{index, 1} = vertcat(adj); % Save the adjacency matrix in the cell array
index = index + 1;
if isempty(data{1, 1}) == 0 % Stop the loop if a connected graph is found
break
end
end
end
% A loop that determines whether a graph in the cell array and a graph that just calculated are non-isomorphism
% If they are non-isomorphism, save the graph's adjacency matrix that just calculated
for i = i+1:2^eg % Repeat for several combinations of edges
% Determine graph connectivity
adj(tri) = egs(i,:); % Assign combination to the upper triangle
G = graph(adj, 'upper'); % Defining a Graph
if not(all(~diff(conncomp(G)))) % If it's not connected
continue % Skip statements below and repeat next
else
% Loop to determine isomorphism
for i2 = 1:index-1
adjbefore = data{i2, 1};
Gbefore = graph(adjbefore, 'upper'); % Access the adjacency matrix in the cell array
if not(isvector(isomorphism(G, Gbefore))) % If it's non-isomorphism
data{index, 1} = vertcat(adj); % Save the adjacency matrix in the cell array
index = index + 1;
break % Stop the loop if a non-isomorphic graph is found and repeat next
end
end
end
end
When I set the number of nodes 4, I can get 38 adjacency matrix.
However, according to (Number of Graphs on n unlabelled vertices (yorku.ca)), number of graphs on 4 unlabelled nodes is only 6.
How do I get this program to work properly?

请先登录，再回答此问题。

采纳的回答

Christine Tobler
Christine Tobler 2021-10-1
In the last loop, you are checking if adj is isomorphic to any previous graph. If there is one graph that adj is not isomorphic to, it's added to the list.
However, you want to find out if adj is not isomorphic to any of the graphs in data, not just if it's not isomorphic to at least one of them.

更多回答（0 个）

类别

在 Help Center 和 File Exchange 中查找有关 Matrix Indexing 的更多信息

标签

产品


版本

R2021b

Community Treasure Hunt

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

Start Hunting!

Translated by