Properties of adjacency matrix

8 visualizaciones (últimos 30 días)
Marc Laub
Marc Laub el 17 de Jul. de 2020
Comentada: Marc Laub el 30 de Nov. de 2022
Hey
following thought about the adjacency matrix of a graph.
Is it possible to distinguish from the adjacency matrix of a graph if the whole system of points is interconnected, or if there are 2 or more subsystems, whcih have connections inside each subsystem but the subsystems are not connected to each other.
Which properties does the adjacency matrix need to represent a interconnected system, or where do i have to seed the "ones" in the matrox to ensure the whole system is interconnected?
I havent figured it out on my own my some example systems, but maybe someone has the answer on this already.
many thanks in advance

Respuesta aceptada

Bruno Luong
Bruno Luong el 27 de Jul. de 2020
Editada: Bruno Luong el 27 de Jul. de 2020
Here is a quick and dirty calculation of connexed component using adjacent matrix. It returns the same output as MATLAB conncomp function in BINS and BINSIZES.
% TMW example
s = [1 2 2 3 3 3 4 5 5 5 8 8 9];
t = [2 3 4 1 4 5 5 3 6 7 9 10 10];
G = digraph(s,t,[],20);
A = G.adjacency;
A = spones(A + A'); % no need to symmetrize for undirected graph
n = size(A,1);
bins = zeros(n,1);
k = 0;
while any(bins==0)
x = sparse(find(~bins,1), 1, true, n, 1, n);
y = x;
while true
y = A*y;
y = y > 0 & ~x;
if nnz(y) == 0
break
end
x = x | y;
end
k = k+1;
bins(x) = k;
end
% Formating output
nodes = (1:n)';
Comptable = table(nodes, bins);
CompSet = accumarray(bins, nodes, [], @(x) {sort(x)'});
binsizes = accumarray(bins, 1);
Display
plot(G,'Layout','layered')
k = length(CompSet);
fprintf('Graph has %d bins(s)\n', k);
Comptable
binsizes
for i=1:k
fprintf('Compnent %d: Nodes = %s\n', i, mat2str(CompSet{i}));
end
  2 comentarios
Bruno Luong
Bruno Luong el 29 de Nov. de 2022
What is the deal of accepting my answer after more than 2 years?
Thanks anyway.
Marc Laub
Marc Laub el 30 de Nov. de 2022
Someones answer to another recent question of mine was, that I marked to few answers as accepted. So I went back my whole history to catch up... Seems some people care more than others

Iniciar sesión para comentar.

Más respuestas (3)

Bruno Luong
Bruno Luong el 17 de Jul. de 2020
Checkout conncomp
  3 comentarios
Bruno Luong
Bruno Luong el 17 de Jul. de 2020
I can't see why you stop yourself of using graph, which is no more no less than the object build around an adjadcent matrix, with a lot of convenient build-in stock functions. Anyway it's your call.
I'll delete this answer in few hours since it's not what you are expected.
Steven Lord
Steven Lord el 17 de Jul. de 2020
What "special properties" did you need that prevented you from using graph or digraph? If you need the nodes and/or edges to have additional information associated with them, you can do that. See this documentation page for details.

Iniciar sesión para comentar.


Christine Tobler
Christine Tobler el 27 de Jul. de 2020
In terms of the adjacency matrix, a disconnected graph means that you can permute the rows and columns of this matrix in a way where the new matrix is block-diagonal with two or more blocks (the maximum number of diagonal blocks corresponds to the number of connected components).
If you want to compute this from scratch, you'll be better off using graph-style algorithms instead of matrix terminology, specifically a breadth-first search or depth-first search. These can be implemented in terms of the adjacency matrix, although it will be less efficient than the built-in used in the graph object. See https://en.wikipedia.org/wiki/Component_(graph_theory) which has some discussion of the algorithms involved.
  1 comentario
Bruno Luong
Bruno Luong el 27 de Jul. de 2020
Editada: Bruno Luong el 27 de Jul. de 2020
Here is a quick and dirty check of graph connexity using adjacent matrix. But I agree why not using stock function that is much better implemented (there is also some code on the FEX using graph algo, that once I checked out - can't remember the name - but I ended up using my own on implementation)
% A is the adjacent matrix, assumed to be symmetric (undirect graph)
n = size(A,1);
x = zeros(n,1);
x(1) = 1;
c = 1; % sum(x)
while true
x = A*x > 0 | x;
s = sum(x);
if s == c
break
end
c = s;
end
if c == n
fprintf('Single component\n');
else
fprintf('Multiple components\n');
end

Iniciar sesión para comentar.


Bruno Luong
Bruno Luong el 27 de Jul. de 2020
Editada: Bruno Luong el 27 de Jul. de 2020
Another way - most direct perhaps link to matrix property - is using this property of Laplacian matrix:
"The number of connected components in the graph is the dimension of the nullspace of the Laplacian and the algebraic multiplicity of the 0 eigenvalue." from https://en.wikipedia.org/wiki/Laplacian_matrix
Not sure how is the numerical stability (probably not very reliable).
% TMW example
s = [1 2 2 3 3 3 4 5 5 5 8 8 9];
t = [2 3 4 1 4 5 5 3 6 7 9 10 10];
G = graph(s,t);
A = G.adjacency;
Use Laplacian
D = diag(sum(A)); % degree matrix
L = D - A; % laplacian matrix
[Q,R,P] = qr(L);
nc = full(sum(abs(diag(R)) < eps)) % number of components
  1 comentario
Bruno Luong
Bruno Luong el 28 de Jul. de 2020
Editada: Bruno Luong el 28 de Jul. de 2020
A basis of the null space of the Laplacian is actually the indicator (characteristic) functions of each connected component of G.

Iniciar sesión para comentar.

Categorías

Más información sobre Graph and Network Algorithms en Help Center y File Exchange.

Productos


Versión

R2019b

Community Treasure Hunt

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

Start Hunting!

Translated by