# May the 4th

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?

MTV Shows