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


  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":

MTV Shows