Reading: Sections 7.1-7.2(upto Thm 7.1), handouts and Chapter 8.
Problems: From the text 7.1.1*, 7.1.7, 7.2.1, 7.2.3, 7.2.11**, 8.1.5, 8.2.2(do only the 3rd graph)
* For part (f), if you decide D is strongly connected,
it is not necessary to give a directed path for all 56 ordered pairs
of vertices; just show that a directed path exists for each ordered pair.
** Assume that D is simple, otherwise it's not true.
and
8. Apply the depth-first-search algorithm for finding strongly
connected components to the directed graph whose
vertices and arcs are listed below.
Draw the depth-first-search tree you obtain.
Draw the backedges, crossedges and forwardedges with dashed lines
and mark them with b, c or f to indicate
which kind of non-tree edge they are.
Label the nodes with their depth-first search numbers (n[]'s)
and their dlow[]'s values.
List the vertices in each strongly connected component.
Where there is a choice of vertex to be made in the search, select the
next vertex alphabetically.
9. Show that if t is not reachable from s in a network N then the value of a maximum flow of N is 0 and the capacity of a minimum cut is 0.
10. Perform the Ford-Fulkerson algorithm on the network below to find a maximum flow. Label the nodes in breadth-first order to find an augmenting path. Use one copy of the network for each labeling iteration and ``highlight'' the augmenting path found. In the last iteration, draw the minimum cut that corresponds to the maximum flow. If you don't want to copy the network yourself click here for a page with 10 copies of the network.
