Adjacency matrices: (a) notation discrepancy, and (b) applications

  • Thread starter nomadreid
  • Start date
  • #1
nomadreid
Gold Member
1,463
148
Two questions, both about adjacency matrices (graphs). The first, specific, the second, general.
[1] I read:
"Consider a directed graph and a positive integer k. Then the number of directed walks from node i to node j of length k is the entry on row i and column j of the matrix Ak..." [where A is the adjacency matrix of a non-directed non-weighted graph, and the exponentiation being normal matrix multiplication in examples on the site]. From http://www.math.cornell.edu/~mec/Winter2009/RalucaRemus/Lecture2/lecture2.html

OK, that seems straightforward. But then I look on another site,
http://cpsc.ualr.edu/srini/DM/chapters/review5.3.html
where they give an example of A2, A3, etc., with a method that is not clear but is definitely not by normal matrix multiplication: specifically
in the example, A =
0 0 1 0 0
0 0 0 1 0
0 1 0 0 1
0 1 0 0 0
1 0 1 0 0
and the site gives
0 0 1 0 0
0 0 0 1 0
0 1 0 1 1
0 1 0 1 0
1 0 1 0 0
as A2, whereas using normal matrix multiplication, one gets A2=
0 1 0 0 1
0 1 0 0 0
1 0 1 1 0
0 0 0 1 0
0 1 1 0 1
which is evidently very different. So what is going on here?

[2] beyond the use of adjacency matrices for
(a) a table (to see what is connected to what) ,
(b) the above application (to see how many paths exist between two points),
(c) to illustrate the Coates method for solving simultaneous equations,
are there any uses for adjacency matrices?

Thanks for any help.
 

Answers and Replies

  • #2
18,264
7,947
Thanks for the post! This is an automated courtesy bump. Sorry you aren't generating responses at the moment. Do you have any further information, come to any new conclusions or is it possible to reword the post?
 
  • #3
nomadreid
Gold Member
1,463
148
To make the question simpler: if you multiply an adjacency matrix (unweighted) by itself, what can you conclude about the product?
 
  • #4
Stephen Tashi
Science Advisor
7,476
1,416
Then the number of directed walks from node i to node j of length k is the entry on row i and column j of the matrix Ak..."
But then I look on another site,
http://cpsc.ualr.edu/srini/DM/chapters/review5.3.html
where they give an example of A2, A3, etc.,
I don't know graph theory, but a casual look shows that the second site is explaning "Warshall's algorithm". According to http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Tremblay/L17-Warshall.htm :

Warshall's algorithm determines whether there is a path between any two nodes in the graph. It does not give the number of the paths between two nodes.
So "whether there is a path" between two give nodes is a different question than "the number of paths" or "the number of paths of length k" between two given nodes.

I think your second link is using superscripts on the matrix that do not mean exponentiation.

(In my brief web searching on this topic, I get the impression that many authors of computer science material don't write precisely. I don't think Warshall's algorithm "determines whether there is a path between any two nodes in the graph". I think it "determines for each pair of nodes on the graph whether there is a path between them".)
 
  • Like
Likes nomadreid
  • #5
nomadreid
Gold Member
1,463
148
Thank you very much, Stephen Tashi. When I look again with the aid of the website you provided, you are right: the second website I provided is using the superscripts to explain Warshall's algorithm, and is simply sloppy in its notation, so that it is easy to mistake them (as I did) for exponents. The website you provided is more careful with its notation, and the explanation is much better. Anyway, that perfectly explains the discrepancy between the two websites I was comparing: the first website I provided was very explicit about the superscripts meaning exponentiation (so I guess that does, unlike Warshall's algorithm, give the number of paths when you sum up all the powers of the adjacency matrix.) So, thanks again!
 

Related Threads on Adjacency matrices: (a) notation discrepancy, and (b) applications

  • Last Post
Replies
1
Views
1K
Replies
6
Views
1K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
1
Views
938
Replies
5
Views
830
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
6
Views
5K
  • Last Post
2
Replies
33
Views
7K
  • Last Post
Replies
4
Views
2K
Replies
2
Views
3K
Top