Problem-Set-11 - The 11th homework of Jan Stelovsky\'s class. PDF

Preview

Summary

The 11th homework of Jan Stelovsky's class....

Description

ICS 311 Fall 2019, Problem Set 11, Topic 20 Your Name Here: Due by 11:55pm Monday 12/03 This is a 30 point homework: Points earned beyond 25 are applied as extra credit.

#1. Peer Credit Assignment 1 Point Extra Credit for replying Please list the names of the other members of your peer group for class the past week (11/28) and the number of points you think they deserve for their participation in group work that day. ● You have a total of 7 points to allocate across all of your peers. ● You can distribute the points equally, give them all to one person, or do something in between. ● You need not allocate all the points available to you. ● You cannot allocate any points to yourself! Points allocated to yourself will not be recorded.

2. (10 pts) Tracing Edmund-Karp (a) Run Edmunds-Karp on the following graph with s as the source and t as the sink. ● Draw the flow graphs on the left hand side of the page with current flow indicated, and the residual graphs on the right hand side of the page. ● Mark the shortest augmenting path in the residual graph with thicker lines, and use it to update flow in the flow graph. ● Repeat, redrawing both updated graphs on a new line, until you can't find an augmenting path. (b) When you can't update the graph any more, write the value of the flow |f| that was achieved, and draw a line in the final graph showing a min cut that corresponds to this max flow.

The graph and a template are below, and the corresponding Google Drawing template is provided: follow this layout. Flow graphs:

Residual graphs:

6 9

3 2

4 2 2

3

3

Flow graphs:

Residual graphs:

2 4/6 3

0/9

0/3 0/2

4/4

4

9

2

4 2

0/2 0/2

0/3

2

3

0/3

3

2 4/6

4 3

0/9

0/3 2/2

4/4

2

4 2

0/2 0/2

2 1

2/3

9

2/3

2

1 2

1 5/6

5 3

1/9

0/3 2/2

4/4

1

2 1

1/2

1

0/2

3/3

3

3/3

5/6 1/9

0/3 2/2

4/4 1/2 0/2

3/3

|f| = 7

8

3/3

2

3

4

3. (10 pts) Vertex Capacities This is the extra credit problem you started in class, but you will complete the proof. Suppose that, in addition to edge capacities, a flow network G* has vertex capacities. We will extend the capacity function c to work on vertices as well as edges: c*(u,v) gives the usual edge capacity and c*(v) gives the amount of flow that can pass through v. But we don’t want to write a new algorithm. We want to transform a flow network G*=(V*,E*) with c* that defines both edge and vertex capacities into an equivalent ordinary flow network G=(V,E) and c that is defined only on edges (without vertex capacities) such that a maximum flow in G has the same value as a maximum flow in G*. Then we can run the algorithms we already have. In class we identified this transformation: given G*=(V*,E*) and c*, compute G=(V,E) and c as follows: For each vertex v ∈ G* with capacity c, make vertices v1 and v2 ∈ G and a new edge (v1, v2) with capacity c (the same as v). Then rewire the graph so that all edges into v in G* now go to v1 in G, and all edges out of v in G* now come out of v2 in G (that is, replace (u, v) with (u, v1) and (v, u) with (v2, u)). Finally, make s 1 and t2 be the new source and target vertices of G. G*

G

Prove that this solution is correct; that is, a solution computed on G will be a correct solution for G*, as follows (your proofs should use formal notation and algebra to be precise, not just English): (a) Given a flow f computed on G, describe how you would construct a flow f* on G*. First, start by merging v1 and v2 into one vertex. Because of this, all of the edges going into v1 become edges going into v (∑𝑢∈𝑣 f(v, u) = ∑ 𝑢∈𝑣 f(𝑣2 , u)) while all the edges going out of v2 become edges going out of v (∑𝑢∈𝑣 f(u, v) = ∑ 𝑢∈𝑣 f(𝑢, 𝑣1 )). The capacity of vertex v is equal to the capacity of a flow between v1 and v2, and when the middle edge is removed, the flows aren’t affected at all because the edges going in and out all are redirected to the new vertex.

(b) Show that when flows computed on G are converted to flows in G*, edge capacities c*(u,v) in G* are respected. The edge capacities are respected because they don ’t change at all. Flows leaving v2 have to be less than or equal to c(v1, v2) on G; this also holds true for G*. Flows leaving v have to be less than or equal to c(v). (c) Show that when flows computed on G are converted to flows in G*, vertex capacities c*(v) in G* are respected. Vertex capacities c*(v) in G* are respected because like the edge capacities, they don’t change. Flows on G entering v1 don’t change when they turn into flows entering v. Note this equation: c(v1, v2) = c(v) (d) Show that when flows computed on G are converted to flows in G*, conservation constraints are respected. Conservation constraints are respected because as stated before, the flows don ’t change. We have said previously that the edge and vertex capacities computed on G are the same as the ones on G*, and all the flows have not changed. Since these flows respected the conservation restraint in G, they will respect the conservation restraints in G*. (e) Finally, show flow equality |f| = |f*|: a flow in G has the same value as a flow in G*. A flow in G has the same value as a flow in G* because none of the values of the flows have changed when G was converted to G*. The flow quality is maintained when the vertices are combined and the edges are removed.

4. (10 pts) Escape Puzzle An nxn grid is an undirected graph consisting of n rows and n columns of vertices, as shown in the figure below. We denote the vertex in the ith row and the jth column by (i,j). All vertices in a grid have exactly four neighbors, except for the boundary vertices, which are the points ( i,j) for which i = 1, j = 1, i = n, or j = n. The escape puzzle begins with m ≤ n2 starting points (x1,y1), (x2,y2), ..., (xm,ym), shown as dots in the figure to the right. Each dot can escape by taking a path from the point to the boundary that does not cross any occupied points, but no two dots can share the same edge on their escape. We want to determine whether all m dots can escape. For example, the grid in the left figure has an escape (shown in grey), but the grid in the right figure does not.

Describe an efficient algorithm that utilizes network flow to solve the escape problem. Analyze its running time. (Hint: You will need to apply more than one problem transformation to get a viable flow graph for the problem. One of the above problems is relevant, and the Kardashians might help you too - but they don’t know the answer.)

First, create a start vertex and establish paths to all the starting points of capacity 0. We will take inspiration from the in-class Kardashian problem and make the capacity constraints of all the edges 1. Then, run the Ford-Fulkerson method to find the maximum number of paths that the starting vertex can use to get to the end to solve the escape problem. Because we’ve essentially constructed a bipartite graph and have used maximum bipartite matching, the runtime of this method which uses the Ford-Fulkerson method is O(VE)....