3 ms·
Yes, it's really the same graph. There really no difference between drawing two copies of V with arrows going from one to the other, and drawing one copy of V w
by edflsafoiewq 8y ago
Yes, it's really the same graph. There really no difference between drawing two copies of V with arrows going from one to the other, and drawing one copy of V with arrows just staying in that copy. Either way, if you trace the arrows from a given vertex you will end up at the same spots.
So for example the interpretation of matrix multiplication as path composition given here explains why the nth power of the adjacency matrix gives the number of length-n walks.
(I think the precise relation is that if A the adjacency matrix for G, then if you draw the graph from this article for the matrix A, the adjacency matrix of that graph will be the block matrix
0 A
A 0
That's assuming the edges in the article are regarded as undirected; if they are directed, just replace one of the As with 0.)
- ajuc 8y agoThanks. It's crazy to me that I've had graph theory on university, and many graph algorithms, and I don't remember ever hearing that multiplicating adjacency matrices have this properties. Maybe I just forgot about it. It would make some algorithms much easier :)
- edflsafoiewq 8y agoHeh. No one noticed but that should have been 0 A^T A 0 In the matrix-as-arrows-from-dots-in-Y-to-dots-in-X picture, the transpose means "turn all the arrows around". This also explains the connection between the transpose and the categorical dual.