Question

1. Express the degree of a vertex in terms of the adjacency matrix
2. Describe how you can find out whether a graph is connected, based on its adjacency matrix, using only matrix addition and multiplication.

Answer 1

number of non zero elements in the row of the corresponding vertex tells the degree of that vertex.

If you put all 1 on the diagonal of your adjacency matrix A, and all edge weights are positive then when you multiply A^2=A∗A you get a non-zero entry aij in A^2 if and only if there exist non-zero aik and akj in A for some k, i.e. there is a path of length 2 between i and j if k≠j and k≠i and there is a path of length 1 if k=j or k=i. So the non-zero entries in A^2 tell you all pairs of nodes that are connected by a path of length 1 or 2. Similarly the entries in A^k tell you all pairs of nodes that are connected by a path of length k or less. So if you start with A and keep squaring until you get A^k where k≥n where n is the number of nodes, then the non-zero entries in row i tell you all the nodes that are connected to node i (since two connected nodes must be connected by a path of length n or less). So if you have a row in A^k that is all non-zero, then the graph is connected. If the graph is not connected, you can similarly tell the connected components from the rows of A^k