ICS 163, Spring 2010, Homework 1
due Wednesday, April 7, 2010


(1) Suppose that a web site consists of three pages, a.html, b.html, and c.html.
Page a.html has links to both b.html and c.html.
Page b.html has links to both a.html and b.html.
And page c.html has only a link back to a.html.
Draw an adjacency matrix (http://en.wikipedia.org/wiki/Adjacency_matrix)
for a directed graph representing this web site. You may assign index numbers to
the vertices arbitrarily; state separately what index you used for each vertex.


(2) Describe the same graph as in question 1, using the dictionary-based
representation of Guido van Rossum from http://www.python.org/doc/essays/graphs/
You may use either the web page names or the index numbers you used
in question 1 to represent each vertex.


(3) For any fixed graph, there may be many different orders in which
depth-first-search could visit the vertices, depending on which vertex
the search starts from and what order the neighbors of each vertex are
listed in. For the graph from question 1, describe an ordering that
could not possibly be generated in this way by DFS.


(4) Let G be a larger graph, formed by adding the following edges and
vertices to the graph in question 1:
- A vertex x.html and an edge from x.html to a.html
- A vertex y.html and an edge from b.html to y.html
- A vertex z.html and an edge from c.html to z.html
- Edges in both directions between y.html and z.html
What are the strongly connected components of G?


(5) Transposing a matrix means flipping it along a diagonal from upper
left to lower right; for instance, the transpose of the matrix
[ 0 1 1 0 ]
[ 1 0 1 0 ]
[ 1 0 0 0 ]
[ 0 0 1 0 ]

is the matrix
[ 0 1 1 0 ]
[ 1 0 0 0 ]
[ 1 1 0 1 ]
[ 0 0 0 0 ].

If two graphs G and H have adjacency matrices that are the transposes
of each other, then what does that mean in terms of how the edges and
vertices of G and H are related to each other