Project 4

For this Sage project, please watch the Graph Theory video on the Sage videos page. This video is a bit longer than the others, but teaches the basic theory behind graphs. Using these ideas, complete the following tasks.

1. Use Sage to draw the graph for the following adjacency matrix:

(1)
\begin{align} A=\left(\begin{array}{rrrrrr} 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right) \end{align}

2. For $A$ given above, draw the graph associated to the matrix $A^2, A^3, A^4, A^5$ and $A^6$.

3. Make up two graphs: one on 4 vertices and one on 5 vertices using an adjacency matrices, $C$ and $D$. Have Sage draw your graphs and then draw the graphs for $C^2, C^3, C^4$ and $D^2, D^3, D^4$, etc.. Can you guess how graphs associated to matrix powers of the adjacency matrix are related to the original graph?

4. Draw your own graph on 4 vertices and figure out the adjacency matrix and the incidence matrix. Input the graph into Sage using the adjacency matrix and then the incidence matrix for your graph. Use Sage's features to determine if you created the matrices correctly (i.e. are the two graphs created the exact same?)

5. Take the following proposed incidence matrix and ask Sage to draw the graph associated to it. Explain why you get an error (in other words, can you use Sage's error to figure out why this is NOT an incidence matrix?) Determine a condition on the columns of a matrix to make it an incidence matrix of a graph.

(2)
\begin{align} B=\left(\begin{array}{rrrrr} 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & -1 & 1 \\ 1 & -1 & -1 & 0 & 0 \\ 0 & 1 & 0 & 0 & -1 \\ -1 & 0 & -1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \end{array}\right) \end{align}

6. What graph corresponds to the identity matrix as an adjacency matrix? What about the $0$ matrix?

7. Let $J$ be the $n\times n$ matrix given by all 1's, so $J_{i,j}=1$ for all $i,j$. Draw the graph with adjacency matrix $J-I_n$ (where $I_n$ is the identity matrix) for a few different $n$ values. Explain the graph in words. How many edges are there in this graph?

8. Optional Explorations (because I may not know the answer completely or if there is an answer at all):

a. Is there any property that a graph will have that will force the adjacency matrix to be invertible (or nonsingular)?
b. Is there any property a graph will have that will force the adjacency matrix to be singular?
c. What does it mean for two rows to be exactly the same in an adjacency matrix.
d. Can you easily determine the rank of an incidence matrix? Are there any conditions that force the rank to be less than the number of rows or columns?
e. Do you have any questions to add?

page revision: 2, last edited: 20 Nov 2012 05:42