Automorphism group of a graph

13 次查看（过去 30 天）
Ben De Schepper
Ben De Schepper 2023-7-27
评论： Zahid 2024-3-8
I'm writing an algorithm to compute the automorphism group of a given graph. I wrote the following code which checks whether any permutation of the nodes yields a graph autmorphism. I have tested this code on small sample graphs (the circle graph with 7 vertices in this code for example), and it works fine. But when I try to test it on a (slightly) bigger graph, say, 50 vertices and 150 edges, it takes very long to compute as the number of permutations of n elements is equal to n!. Does anybody have tips for making this code more efficient to make it useful for graphs with 100 vertices or less?
% Number of vertices
numVertices = 7;
% Create an empty graph
G = graph([], []);
% Add edges to form the circle graph
for i = 1:numVertices
if i == numVertices
G = addedge(G, i, 1);
else
G = addedge(G, i, i+1);
end
end
% Plot the graph
figure;
h = plot(G, 'Layout', 'force');
% Get the adjacency matrix
adjMatrix = adjacency(G);
% Compute the automorphism group using the adjacency matrix
automorphisms = {};
allPermutations = perms(1:numVertices);
for i = 1:size(allPermutations, 1)
permVector = allPermutations(i, :);
permMatrix = zeros(numVertices);
for j = 1:numVertices
permMatrix(j, permVector(j)) = 1;
end
resultMatrix = permMatrix * adjMatrix * permMatrix';
if isequal(resultMatrix, adjMatrix)
automorphisms{end+1} = permMatrix;
end
end
% Convert cell array to matrix format
automorphisms = cat(3, automorphisms{:});
% Display the automorphism group
disp('Automorphism Group Permutations:');
disp(automorphisms);
% Number of automorphisms
numAutomorphisms = size(automorphisms, 3);
disp(['Number of Automorphisms: ', num2str(numAutomorphisms)]);
  1 个评论
Zahid
Zahid 2024-3-8
I want to generate regular graph of {8,3} tiling in the form of adjacency matrices for large number of vertices say n=10000. Is that possible to do?

请先登录，再进行评论。

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

采纳的回答

Dheeraj
Dheeraj 2023-8-17
Hi,
Your current approach involves trying all permutations of the graph and checking if they preserve the adjacency structure. This approach is inherently expensive, and as you've observed, its runtime grows factorially with the number of vertices.
As computing automorphism group of a given graph is an NP-Complete problem, you could use automorphism libraries like ‘nauty and Traces’ as they are optimised for graph automorphism problems and are efficient than the brute-force methods.
You could refer to this document on ‘nauty and Traces’ for better understanding.
https://pallini.di.uniroma1.it

更多回答（0 个）

类别

在 Help Center 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息

标签

产品


版本

R2023a

Community Treasure Hunt

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

Start Hunting!

Translated by