# 程序代写 Analysis of Algorithms, I – cscodehelp代写

Analysis of Algorithms, I

CSOR W4231.002

Computer Science Department

Copyright By cscodehelp代写 加微信 cscodehelp

Columbia University Network flows

1 Flow networks Applications

2 The residual graph and augmenting paths

3 The Ford-Fulkerson algorithm for max flow

4 Correctness of the Ford-Fulkerson algorithm

5 Application: max bipartite matching

1 Flow networks Applications

2 The residual graph and augmenting paths

3 The Ford-Fulkerson algorithm for max flow

4 Correctness of the Ford-Fulkerson algorithm

5 Application: max bipartite matching

Modeling transportation networks

Source: Communications of the ACM, Vol. 57, No. 8

Can model a fluid network or a highway system by a graph: edges carry traffic, nodes are switches where traffic gets diverted.

Flow networks

A flow network G = (V, E) is a directed graph such that

1. Every edge has a capacity ce ≥ 0. 2. Thereisasinglesources∈V.

3. Thereisasinglesinkt∈V.

A1: integer capacities A2: noedgeenterss A3: noedgeleavest

Two more assumptions for the purposes of the analysis

A4: If (u,v)∈E then (v,u)̸∈E.

A5: Everyv∈V −{s,t}isonsomes-tpath. Hence G has m ≥ n − 1 edges.

An example flow network

Given a flow network G, an s-t flow f in G is a function f : E → R+.

Intuitively, the flow f(e) on edge e is the amount of traffic that edge e carries.

Two kinds of constraints that every flow must satisfy

1. Capacity constraints: for all e ∈ E, 0 ≤ f(e) ≤ ce. 2. Flow conservation: for all v ∈ V − {s, t},

f(u,v)= f(v,w) (1) (u,v)∈E (v,w)∈E

In words, the flow into node v equals the flow out of v, or

f(e)= f(e) e into v e out of v

A cleaner equation for flow conservation constraints

1. fout(v)= f(e)

e out of v 2.fin(v)= f(e)

So we can rewrite equation (1) as: for all v ∈ V − {s, t}

fin(v) = fout(v) (2)

The value of a flow

Definition 1.

The value of a flow f, denoted by |f|, is

|f| = f(e) = fout(s)

e out of s

Exercise: show that |f| = fin(t).

An example flow of value 20

A flow f of value 20.

A flow of value 30

10/10 10/30 t

A (max) flow of value 30.

Max flow problem

Input: (G, s, t, c) such that

G = (V,E) is a flow network;

s, t ∈ V are the source and sink respectively; c is the (integer-valued) capacity function.

Output: a flow of maximum possible value

s-t cuts in flow networks

Definition 2.

An s-t cut (S, T ) in G is a bipartition of the vertices into two sets S and T , such that s ∈ S and t ∈ T .

A natural upper bound for the max value of a flow

Flow f must cross (S,T) to go from source s to sink t.

So it uses some (at most all) of the capacity of the edges

crossing from S to T.

So, intuitively, the value of the flow cannot exceed

ce e out of S

Max flow and min cut

Definition 3.

The capacity c(S,T) of an s-t cut (S,T) is defined as c(S,T) = ce.

e out of S

△ Note asymmetry in the definition of c(S, T )!

So, intuitively, the value of the max flow is upper bounded by

the capacity of every cut in the flow network, that is,

max|f| ≤ min c(S,T) (3)

(S,T) cut in G

Applications of max-flow and min-cut

Find a set of edges of smallest capacity whose deletion disconnects the network (min cut)

Bipartite matching (max flow) —coming up

Airline scheduling (max flow)

Baseball elimination (max flow)

Distribution of goods to cities (max flow)

Image segmentation (min cut)

Survey design (max flow)

1 Flow networks Applications

2 The residual graph and augmenting paths

3 The Ford-Fulkerson algorithm for max flow

4 Correctness of the Ford-Fulkerson algorithm

5 Application: max bipartite matching

“Undoing” flow

A flow f of value 20.

Goal: undo 10 units of flow along (u, v), divert it along (u, t).

Pushing flow back

s 10/20 10/10

10/10 10/30 t

“Push back” 10 units of flow along (v, u).

Send 10 more units from s to t along the green path edges

(s, v), (v, u), (u, t).

New flow f′ (on the right) with value 30.

Pushing flow forward and backward

By pushing flow back on (v, u), we created an s-t path on which we are pushing flow

forward, on edges with leftover capacity (e.g, (s, v));

backward, on edges that are already carrying flow so as to divert it to a different direction (e.g., (u, v)).

The residual graph Gf

Definition 4.

Given flow network G and flow f, the residual graph Gf has

the same vertices as G;

foreveryedgee=(u,v)∈Ewithf(e)

SoGf has≤2medgesandeverye∈Gf hascf(e)>0.

Example residual graph

20/20 0/20 20 20

s 20/30 t s 20 10 t

0/10 20/20 10 20 vv

Left: a graph G and a flow f of value 20.

Right: the residual graph Gf for flow network G and flow f.

The residual graph Gf as a roadmap for augmenting f

1. Let P be a simple s-t path in Gf.

2. Augment f by pushing extra flow on P .

Question: How much flow can we push on P without violating capacity constraints in Gf ?

The residual graph Gf as a roadmap for augmenting f

1. Let P be a simple s-t path in Gf.

2. Augment f by pushing extra flow on P .

Question: How much flow can we push on P without violating capacity constraints in Gf ?

Definition 5.

The bottleneck capacity c(P) of a simple path P is the minimum residual capacity of any edge of P. In symbols

c(P ) = min cf (e). e∈P

The residual graph Gf as a roadmap for augmenting f

1. Let P be a simple s-t path in Gf.

2. Augment f by pushing extra flow on P .

Question: How much flow can we push on P without violating capacity constraints in Gf ?

Definition 5.

The bottleneck capacity c(P) of a simple path P is the minimum residual capacity of any edge of P. In symbols

c(P ) = min cf (e). e∈P

Answer: The max amount of flow we can safely push on every edge of P is c(P).

The augmented flow f′

Let P be an augmenting path in the residual graph Gf . We obtain an augmented flow f′ as follows:

1. Foraforwardedgee∈P,setf′(e)=f(e)+c(P)

2. Forabackwardedgeer =(u,v)∈P,lete=(v,u)∈G;

set f′(e) = f(e) − c(P)

3. Fore∈EbutnotinP,f′(e)=f(e).

f′ is a flow.

Pseudocode for subroutine Augment

Input: a flow f, and an augmenting path P in Gf Output: the augmented flow f′

Augment(f, P )

foreachedge(u,v)∈P do

if e = (u, v) is a forward edge then

f(e) = f(e) + c(P) else

f (v, u) = f (v, u) − c(P ) end if

2 The residual graph and augmenting paths

3 The Ford-Fulkerson algorithm for max flow

4 Correctness of the Ford-Fulkerson algorithm

5 Application: max bipartite matching

The Ford-Fulkerson algorithm

Ford-Fulkerson(G = (V, E, c), s, t)

for all e ∈ E do f(e) = 0

while there is an s-t path in Gf do

Let P be a simple s-t path in Gf f′ = Augment(f,P)

Set f = f′

SetGf =Gf′

Running time analysis

The algorithm terminates if the following facts are both true. Fact 6.

Every iteration of the while loop returns a flow increased by an integer amount.

There is a finite upper bound to the flow.

Running time analysis

The algorithm terminates if the following facts are both true. Fact 6.

Every iteration of the while loop returns a flow increased by an integer amount.

There is a finite upper bound to the flow.

Proof of Fact 7.

Let U be the largest edge capacity, that is, U = max ce. Then e

|f| ≤ ce ≤ nU. e out of s

f increases by an integer amount after Augment(f, P )

Proof of Fact 6.

It follows from the following claims.

During execution of the Ford-Fulkerson algorithm, the flow values {f(e)} and the residual capacities in Gf are all integers.

Letf beaflowinGandP asimples-tpathinGf with residual capacity c(P ) > 0. Then after Augment(f, P )

|f′| = |f| + c(P) ≥ |f| + 1.

f increases by an integer amount after Augment(f, P )

Proof of Claim 3.

Recall that |f| = fout(s).

1. Since P is an s-t path, it contains some edge out of s,

say (s, u).

2. Since P is simple, it does not contain any edge entering s

(P is in Gf , where there could be edges entering s!).

3. Since no edge enters s in G, (s,u) is a forward edge in Gf,

thus its augmented flow is f (s, u) + c(P ) ≥ f (s, u) + 1.

4. Since no other edge going out of s is updated, it follows

that the value of f′ is

|f′| = |f| + c(P) ≥ |f| + 1.

Running time of Ford-Fulkerson

1. Claim 3 guarantees at most nU iterations.

2. The running time of each iteration is bounded as follows:

O(m + n) to create Gf using adjacency list representation.

O(m + n) to run BFS or DFS to find the augmenting path.

O(n) for Augment(f, P ) since P has at most n − 1 edges.

⇒ Hence one iteration requires O(m) time. The running time of Ford-Fulkerson is O(mnU).

Definition 8 (Pseudo-polynomial algorithms).

An algorithm is pseudo-polynomial if it is polynomial in the size of the input when the numeric part of the input is encoded in unary.

Ford-Fulkerson is a pseudo-polynomial time algorithm.

Problems with pseudo-polynomial running times

1000000 v 1000000

Improved algorithms

FF can be made polynomial: use BFS instead of DFS Edmonds-Karp: O(nm2), Dinitz: O(n2m),

other improvements: O(nm log n), O(n3)

Unit capacities: O(min{m3/2, mn2/3}) [EvenTarjan1975]

Improved for sparse graphs: O ̃(m10/7) [Madry2013]

Integralcapacities:O(min{m3/2,mn2/3)log(n2/m)logU) [GoldbergRao1998]√

Improved: O ̃(m n log2 U) [LeeSidfort2014];

also improves for dense graphs with unit capacities

Realcapacities:O(nmlog(n2/m)) Improved: O(nm) [Orlin2013]

2 The residual graph and augmenting paths

3 The Ford-Fulkerson algorithm for max flow

4 Correctness of the Ford-Fulkerson algorithm

5 Application: max bipartite matching

A natural upper bound for the max value of a flow

Ans-tcut(S,T)inGisabipartitionoftheverticesinto two sets S and T, such that s ∈ S and t ∈ T.

The capacity c(S,T) of s-t cut (S,T) is

e out of S

Then intuitively

max|f| ≤ min c(S,T) f (S,T) cut in G

Roadmap for proving optimality of Ford- that |f| = fout(s). We will prove the following.

1. For any flow f, the value of the flow |f| cannot exceed the

capacity of any cut in G.

2. Let f be the flow upon termination of the Ford-Fulkerson algorithm. We will exhibit a specific cut (S∗, T ∗) such that the value of f equals the capacity of (S∗, T ∗). In symbols,

|f| = c(S∗,T∗)

From 1., 2., we can conclude that f is a maximum flow. And(S∗,T∗)isacutofminimumcapacity.

Ford-Fulkerson terminates when ̸ ∃ s-t path in Gf

Consider the residual graph Gf upon termination of the algorithm. Let (S∗, T ∗) be the cut in Gf where

S∗ is the set of nodes reachable from the source s; T∗ contains every other node.

Is (S∗,T∗) also a cut in G?

On the cut (S∗,T∗)

1. (S∗,T∗)isans-tcut: thatis,s∈S∗,t∈T∗. Why?

2. In Gf, no edge crosses from S∗ to T∗. Why?

3. Hence,ife=(x,y)∈Ewithx∈S∗ andy∈T∗,then f(e) = ce (thus e ̸∈ Ef).

4. Similarly, if e′ = (u,v) ∈ E with u ∈ T∗ and v ∈ S∗, then f(e′) = 0. Why?

On the cut (S∗,T∗)

1. (S∗,T∗)isans-tcut: thatis,s∈S∗,t∈T∗. Why? Because there is no s-t path in Gf .

2. In Gf, no edge crosses from S∗ to T∗. Why?

If (u,v) crosses from S∗ to T∗, thus u ∈ S∗,v ∈ T∗, then ∃

s-v path in Gf . Hence v ∈ S∗; contradiction.

3. Hence,ife=(x,y)∈Ewithx∈S∗ andy∈T∗,then

f(e) = ce (thus e ̸∈ Ef).

4. Similarly, if e′ = (u,v) ∈ E with u ∈ T∗ and v ∈ S∗, then

f(e′) = 0. Why?

If f(e′) > 0, then (v,u) ∈ Ef, with cf(v,u) = f(e′) > 0. Contradicts our second observation.

Our observations on (S∗, T ∗) in a diagram

In G, every edge e crossing from S* to T* satisfies

f(e)=ce (of course, such e does not appear in Gf).

Every edge e′ in G crossing from T* to S* satisfies f(e′)=0.

f(e1)=ce1 f(e2)=ce2

Net flow across a cut

Definition 9.

The net flow across an s-t cut (S, T ) is the amount of flow leaving the cut minus the amount of flow entering the cut

fout(S) − fin(S), (5) 1. fout(S)= f(e)

2. fin(S)=

e out of S

f(e) e into S

Net flow across (S∗, T ∗) equals capacity of (S∗, T ∗)

f(e1)=ce1 f(e2)=ce2

fout(S∗) − fin(S∗) = f(e) − e out of S∗

= ce−0 e out of S∗

= c(S∗,T∗)

f(e) e into S∗

Roadmap revisited

Let f be the flow upon termination of the Ford-Fulkerson algorithm.

1. Exhibit a specific s-t cut (S∗, T ∗) in G such that the |f| = c(S∗,T∗).

Not quite there yet!

We exhibited (S∗,T∗) with net flow equal to its capacity.

We need to relate the net flow across (S∗,T∗) to |f|

(that is, the flow out of s).

In particular, if we showed them equal, then we’d have

|f| = c(S∗,T∗).

2. Show that |f| cannot exceed the capacity of any cut in G. 3. Conclude that f is a maximum flow.

net flow across any s-t cut = |f|

Recall that

fout(S)= f(e)

e out of S

fin(S)= f(e)

net flow across (S,T) fout(S)−fin(S)

Let f be any s-t flow, and (S,T) any s-t cut. Then |f| = fout(S) − fin(S).

Proof of Lemma 10

First, rewrite the flow out of s in terms of the flow on the vertices on S:

|f| = fout(s)=fout(v)−fin(v) (7) v∈S

fin(s)=0;

for every v ∈ S − {s}, the terms in the right-hand side of (7) cancel out because of flow conservation constraints.

Next, rewrite the right-hand side of equation 7 in terms of the edges that participate in these sums.

There are three types of edges.

Proof of Lemma 10 (cont’d)

1. Edges with both endpoints in S: such edges appear once in the first sum in equation 7 and once in the second, hence their flows cancel out.

2. Edges with the tail in S and head in T (out of S): such edges contribute to the first sum, fout(v), in equation 7

3. Edges with the tail in T and head in S (into S): such edges

so they appear with a +.

contribute to the second sum, fin(v), in equation 7 so

In effect, the right-hand side of equation 7 becomes

f(e)− f(e). e out of S e into S

they appear with a −.

The lemma follows.

The value of a flow cannot exceed capacity of any cut

Corollary 11.

Let f be any s-t flow and (S,T) any s-t cut. Then |f| ≤ c(S,T).

|f| = fout(S)−fin(S) ≤ fout(S) ≤ c(S,T).

Putting everything together

By Corollary 11, the value of a flow cannot exceed the capacity of any cut; in particular,

|f| ≤ c(S∗,T∗).

By Lemma 10, |f| equals the net flow across any s-t cut;

in particular,

|f| = fout(S∗) − fin(S∗).

From(6),thenetflowacross(S∗,T∗)equalsc(S∗,T∗).

Hence the above becomes

|f| = fout(S∗)−fin(S∗) = c(S∗,T∗).

⇒ Thus the flow computed by Ford-Fulkerson is a maximum flow because it cannot be increased anymore.

The max-flow min-cut theorem

Theorem 12.

If f is an s-t flow such that there is no s-t path in Gf, then there is an s-t cut (S∗,T∗) in G such that |f| = c(S∗,T∗). Therefore, f is a max flow and (S∗,T∗) is a cut of min capacity.

Theorem 13 (Max-flow Min-cut).

In every flow network, the maximum value of an s-t flow equals the minimum capacity of an s-t cut.

Integrality theorem

Recall the following claim.

During execution of the Ford-Fulkerson algorithm, the flow values {f(e)} and the residual capacities in Gf are all integers.

Combine with Theorem 12 to conclude:

Theorem 14 (Integrality theorem).

If all capacities in a flow network are integers, then there is a maximum flow for which every flow value f(e) is an integer.

2 The residual graph and augmenting paths

3 The Ford-Fulkerson algorithm for max flow

4 Correctness of the Ford-Fulkerson algorithm

5 Application: max bipartite matching

Bipartite Matching

x1 y1 x1 y1

x2 y2 x2 y2

x3 y3 x3 y3

x4 y4 x4 y4

x5 y5 x5 y5 XYXY

Definition 15.

A matching M is a subset of edges where every vertex in X ∪ Y appears at most once.

Example: {(x1, y2), (x2, y3), (x3, y4), (x5, y5)} is a matching. Perfect matching: every vertex in X ∪ Y appears exactly once.

Not always possible: e.g., |X| ≠ |Y |. Maximum matching still desirable in applications.

If we had an algorithm to find maximum matching then we could also find a perfect matching, if one exists (why?).

Finding maximum matchings in bipartite graphs

Idea: Use the Ford-Fulkerson algorithm to find maximum (or perfect) matchings in bipartite graphs.

Strategy: reformulate the problem as a max flow problem which we know how to solve (reduction).

To this end, we need to transform our input bipartite graph into a flow network.

A diagram of the algorithm for max bipartite matching

Algorithm for max bipartite matching

Reduction R

Ford-Fulkerson

bipartite G

input to max bipartite matching

input to MaxFlow

Transform G into a flow network G’ = R(G)

max |f| = k

1. The reduction R must be efficient (polynomial in the size of G).

2. G and G′ should be equivalent, in the sense that G has a max matching of size k if and only if the max flow in G′ has value k.

Deriving a flow network given a bipartite graph

Given a bipartite graph G = (X ∪ Y, E), we construct a flow network G′ as follows.

Add a source s.

Addasinkt.

Add(s,x)edgesforallx∈X.

Add(y,t)edgesforally∈Y.

Directalle∈EfromXtoY.

Assign to every edge capacity of 1.

The flow network for the example bipartite graph

x5 y5 XY

Computing matchings in G from flows in G′

G=(X∪Y,E)isthebipartitegraph G′ is the derived flow network

The size of the maximum matching in G equals the value of the maximum flow in G′. The edges of the matching are the edges that carry flow from X to Y in G′.

Proof of Claim 5

The claim follows if we show the following two statements (why?).

1. (⇒ Forward direction) For any matching M in G, we can construct a flow f in G′ with value equal to the size of M, that is, |f| = |M|.

2. (⇐ Reverse direction) Given a max flow f′ in G′, we can construct a matching M′ in G, with size equal to the value of the max flow, that is, |M′| = |f′|.

(1.⇒)FromamatchingM toaflowf with|f|=|M|

Let |M| = k.

Gx1 y1 G′ x1 y1 ce=1

x2 y2 x2 y2

x3 y3 s x3 y3 t x4 y4 x4 y4

x5 y5 x5 y5 XYXY

Given matching M (the red edges in G), construct an integral flow f in G′, such that the value of f equals the number of edges in M.

(1.⇒)FromamatchingM toaflowf with|f|=|M|

Let |M| = k. Send one unit of flow along each of the k edge-disjoint s-t paths that use the edges in M; then |f| = k.

x50/1y5 XYXY

x2 1/1 1/1 0/1

s x31/1 y3 t

0/1×40/1 y4 0/1

Given matching M (the red edges in G), construct the integral flow f in G′. Then the value of f equals the number of edges in M.

(2. ⇐) From max flow f′ to M′ with |M′| = |f′|

y1 Gx1 y1 0/1

x2 1/1 1/1 0/1

y2 1/1 1/1

x5 y5 XY

x31/1 x4 0/1

Given integral max flow f′ in G′, construct a matching M′ in G so that the number of edges in M′ equals the value of f′.

From max flow f′ to matching M′ with |M′| = |f′|

Givenamaxflowf′ inG′ with|f′|=k,wewanttoselectaset of edges M′ in G so that M′ is a matching of size k.

By the integrality theorem, there is an integer-valued flow f of value k.

Then for every edge e, f(e) = 0 or f(e) = 1 (why?). Define the following matching M′:

M′ =e=(x,y):x∈X,y∈Y andf(e)=1.

Obtaining a matching M′ from an integral flow f

y1 Gx1 y1 0/1

程序代写 CS代考 加微信: cscodehelp QQ: 2235208643 Email: kyit630461@163.com