Suppose we wish to store an n n boolean matrix (0 and 1 elements only). We could represent it by the bits themselves, or we could represent the matrix by listing the positions of the 1s as pairs of integers, each integer requiring [log₂ n] bits. The former is suitable for dense matrices; the latter is suitable for sparse matrices. How sparse must the matrix be (i.e., what fraction of the elements should be 1s) for the sparse representation to save space?

Represent the transition matrices of the following graphs: