CptS 223 – Advanced Data Structures Homework 6 Due: 5:00pm, May 1, 2009 (Late deadline: 5:00pm, May 4, 2009) Total Points: 45 You may submit your solution via email to [email protected] (preferred), or you may submit hardcopy in class or to my office (EME 227) by the above deadline. If you submit via email, please use PDF or other common electronic format. Questions 1-8 refer to the following graph G. 1. (5 points) Give the shortest path and path cost from v1 to every other vertex in graph G. 2. (8 points) Show the maximum flow network in G with source v1 and sink v6. Also show the final residual graph (the one with no augmenting paths) for your maximum flow. Be sure to show the both the forward and back capacities in the residual graph. 3. (4 points) Give a topological sort of graph G after removing edge v3 v4 and assuming the edges are unweighted. 4. (5 points) Show the minimum spanning tree of G assuming the edges are undirected. 5. (2 points) Give the articulation points in graph G assuming the edges are undirected and unweighted. 6. (5 points) Show the depth-first spanning forest (similar to that in Figure 9.75) that results from running depth-first search on graph G assuming the edges are unweighted. Be sure to show tree edges as solid arrows and forward/back/cross edges as dashed arrows. When there is a choice as to which vertex to visit next, always prefer the lower-numbered vertex. 7. (3 points) Give the strongly-connected components of graph G assuming the edges are unweighted. v1 v4 v5 v3 v2 v6 5 3 2 2 6 1 7 4 5 38. (5 points) Give the Euler circuit of graph G starting from v1 assuming the edges are undirected and unweighted. When there is a choice as to which vertex to visit next, always prefer the lower-numbered vertex. 9. (8 points) Consider the following two decision problems. • Partition: Given a set A of integers, can you partition the set into two subsets A1 and A2 such that the sum of the elements of A1 equals the sum of the elements of A2, i.e., A1 ∪ A2 = A, A1 ∩ A2 = ∅, and ∑i∈A1 i = ∑i∈A2 i ? • Subset-Sum: Given a set A of integers and an integer K, can you find a subset A1 of A whose elements sum to K, i.e., ∑i∈A1 i = K? Assuming Partition is NP-Complete, prove that Subset-Sum is
View Full Document
Unlocking...