Problem Set 15

Consider the graph shown below.

graph TB
    A((1))-->B((2))
    A-->C((3))
    B-->D((4))
    C-->E((5))
    D-->B
    E-->C
    D-->A

1. Is this a directed or undirected graph?
2. Is this a strongly connected graph?
3. Is 5 reachable from 2? If so, what path can you follow?
4. Write out an edge list for this graph.
5. Write out an adjacency list for this graph.
6. Write out an adjacency map for this graph.
7. Write out an adjacency matrix for this graph.
8. Can you compute a topological ordering for this graph? If so, what is it? If not, why is it not possible?
9. Write out the transitive closure for this graph.
10. What are the incoming neighbors of node 3?
11. What are the outgoing neighbors of node 1?