Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CS 163/265--Graph Algorithm Homework 5
Please answer the following questions, each of which is worth 10 points.
1. (CS 163 students only) Using the graph at the following website, find and label the edges to show a maximum flow. Also, mark the edges belonging to a minimum cut.
https://upload.wikimedia.org/wikipedia/commons/2/26/Network_flow_9_vertices_blank.svg
2. What is the worst-case running time of the Ford-Fulkerson algorithm if all edge capacities are bounded by a constant?
3. Let N be a flow network with n vertices and m edges. Show how to compute an augmenting path with the largest residual capacity in O((n+m) log n) time.
4. In the context of the baseball elimination problem, one can show that if wi+gi ≤ wk+gk and team k is eliminated, then team i is also eliminated. Use this fact to show that among a set of n teams, one can determine all the eliminated teams by solving O(log n) maximum flow problems.
5. In 2006, the city of Beijing, China, instituted a policy that limits residents to own at most one dog per household. Imagine you are running an online pet adoption website for the city. Your website contains pictures of adorable puppies that are available for adoption, and it allows for dogless Beijing residents to click on as many puppies as they like, with the understanding that they can adopt at most one. Suppose now that you have collected the puppy preferences from among n Beijing residents for your m puppies. Describe an efficient algorithm for assigning puppies to residents that provides for the maximum number of puppy adoptions possible while satisfying the constraints that each resident will only adopt a puppy that he or she likes and that no resident can adopt more than one puppy.
6. (CS 265 students only) The city of Irvine, California, allows for residents to own a maximum of three dogs per household without a breeder’s license. Imagine you are running an online pet adoption website for the city, as in the previous exercise, but now for n Irvine residents and m puppies. Describe an efficient algorithm for assigning puppies to residents that provides for the maximum number of puppy adoptions possible while satisfying the constraints that each resident will only adopt puppies that he or she likes and that no resident can adopt more than three puppies.