CSE 373: Data Structures and Algorithms

Autumn 1994

Assignment 8 Solution

  
1.  Problem 9.1 from the text.

    The answer is not unique, here are some of them:

    s, G, D, H, A, B, E, I, F, C, t.
    s, G, H, D, A, B, E, I, F, C, t.
    s, G, D, A, B, H, E, I, F, C, t.

2.  Problem 9.2 from the text.

    Assuming the same adjacensy list, the topological order produced 
    when a stack is used is -- s, G, H, D, A, E, I, F, B, C, t.  Because 
    a topological sort processes vertices in the same manner as a breadth
    first search it tends to produce a more natural ordering.

3.  Problem 9.5 from the text.

    a)  vertices  	path			weight
	A -> B		A, B			5
	A -> C		A, C			3
	A -> D 		A, B, G, E, D		9
	A -> E 		A, B, G, E		7
	A -> F 		A, B, G, E, F		8
	A -> G 		A, B, G			6

    b)  vertices	path			weight
	B -> A 		B, C, D, A		3
	B -> C		B, C			1
	B -> D 		B, C, D			2
	B -> E		B, E			1
	B -> F		B, E, F			2
	B -> G		B, G			1

4.  Problem 9.11 from the text.

    The maximum flow is 11.