Adjacency Matrices Can someone explain adjacency matrix's in simple terms? I'm not grasping the material from the text at all, and can't solve the sample solutions provided.such as k2,k3 and the reverse. I understand its the vertices in matrix form but how do you transfer that? Can someone show the logical steps here in a simple, understandable way if possible?
Thanks
 A: Okay, let us construct the adjacency matrix for the graph $G$ here:

here we have numbered the nodes 1 to 6.
For a graph with $n$ nodes, the adjacency matrix will be an $n \times n$ matrix. So in, our case, we will get a $6 \times 6$ matrix.
The $i$:th row in our matrix will correspond to node $i$. If there is a 1 in the $j$:th position in row $i$, there is an edge from node $i$ to node $j$. If there is a zero, it means that there is no edge between node $i$ and node $j$.
So, let us construct the first row in our adjacency matrix, the row that corresponds to node 1. Node 1 has edges only to the nodes 1, 2 and 5.  Thus, our first row will be:
$$\begin{pmatrix} 1 & 1 & 0 & 0 & 1 & 0\end{pmatrix}.$$
Let us go back and check this. The first one says that there is an edge from node 1 to node 1, which is true. Same for the second one. The third element, the first zero, says that there is no edge from node 1 to node 3, which is also true. And so on.
We can continue on and do this for every node. Our fourth row, corresponding to node 4, will be:
$$\begin{pmatrix} 0 & 0 & 1 & 0 & 1 & 1 \end{pmatrix}.$$
Our full matrix will be:
$$\begin{pmatrix}
1 & 1 & 0 & 0 & 1 & 0 \\
1 & 0 & 1 & 0 & 1 & 0 \\
0 & 1 & 0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 & 1 & 1 \\
1 & 1 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 0 
\end{pmatrix}$$
Given example
Now, you gave the example:
$$\begin{pmatrix}
0&0&0&1&1 \\
0&0&0&1&1 \\
0&0&0&1&1 \\
1&0&1&0&0 \\
1&0&1&0&0
\end{pmatrix}$$
since this is a $5 \times 5$ matrix, we should have a matrix with 5 nodes, let us call them 1, 2, 3, 4 and 5. We also see that the matrix is not symmetric, so the edges are directed (the graph above had undirected edges).
In the matrix we see that the nodes 1, 2 and 3 all have edges to the same nodes, namely 4 and 5. We also see that the nodes 4 and 5 have edges to the same nodes, namely 1 and 3. From this it is not that hard to draw the graph.
