May the 4th

Adjaceny Matrices

To work with graph algorithms we need something more precise than a picture. Here comes the adjacency matrix! For a graph \(G\) with vertices \(v_1, \ldots, v_n\) we define an \(n \times n\) matrix \(A\) which has \(a_{i,j} = 1 \) when \(v_i\) is connected to \(v_j\) and 0 otherwise.

Has the adjacency matrix: $$ A = \left(\begin{array}{rrrr} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{array}\right) $$

Cool properties of Adj. Matrices

• The diagonals are 0 in adjacency matrices for standard graphs since anything other than 0 would be a loop (pseudo graphs allow them).
• In non-directed graphs \(a_{i,j} = a_{j,i}\), in directed graphs this is not the case. Likewise any symmetric matrix of 0's and 1's can be seen as an adjacency matrix of a pseudograph (graphs require the extra contstraint that the diagonal has a 0 diagonal).
• In the adjacency matrix of a graph (not pseudograph) the sum of the 1s in row \(i\) is the degree of \(v_i\). The same holds for column \(i\).
• The \((i,j)\) entry of \(A^2\) is the number of different walks of length 2 from \(v_i\) to \(v_j\)!
• In general the \((i,j)\) entry of \(A^k\) is the number of walks of length \(k\) from \(v_i\) to \(v_j\).
• Theorem: Two graphs are isomorphic if and only if their vertices can be labeled in such a way that the corresponding adjacency matrices are equal.
• Let \(G_1\) and \(G_2\) be graphs with adjacency matrices \(A_1\) and \(A_2\). \(G_1\) is isomorphic to \(G_2\) if and only if there exists a permutation matrix (an identity with rows shuffled) \(P\) such that \(A_2 = P A_1 P^{T}\).

Problems

1. What is the adjacency matrix of \(K_n\)? Label the vertices of \(K_{m,n}\) so that the adjacency matrix has an especially nice form.
2. If you add all of the values in an adjacency matrix what do you get?
3. Let \(A\) be the adjacency matrix of a graph \(G\) with vertices \(v_1, v_2, \ldots, v_n\). Prove that the \(i^{\textrm{th}}\) entry on the diagonal of \(A^3\) equals twice the number of distinct triangles that contain \(v_i\).
4. Find the adjacency matrices of these two graphs \(A_1\) and \(A_2\) then find the permutation matrix \(P\) such that \(A_1 = P A_2 P^{T}\) proving them isomporphic.
   
   
5. The following pseudograph captures all strings made from 'a' and 'b' which only allow one 'b' at a time.
   
   Create an adjacency matrix for it, and try to count all of the strings of length 4, now length \(n\).
6. Now make a graph for all strings which allow at most two 'b's in a row at a time. Can you answer the same questions?
7. What are other ways that a graph could be stored in a computer?

In an effort to class things up I offer this dramatic yet classroom appropriate scene from "Tenement":