# CS计算机代考程序代写 AI algorithm Analysis of Algorithms

Analysis of Algorithms

V. Adamchik CSCI 570 Spring 2020 Lecture 9 University of Southern California

Network Flow

Reading: chapter 7

The Network Flow Problem

Our fourth major algorithm design technique

(greedy, divide-and-conquer, and dynamic programming).

Plan:

The Ford-Fulkerson algorithm Max-Flow Min-Cut Theorem

The Flow Problem

source

Suppose you want to ship natural gas from Alaska to Texas.

Pipes have capacities.

The goal is to send as much gas as possible. How can you do it?

sink

The Max-Flow Problem

21 21531

t

s

32

The MAX Flow Problem

2a1 21531

s b

t

How can you see that the flow is really max?

32 The max-flow here is __.

Greedy Approach

u

s30 t

10 v

20

10

20

Push 20 via s-u-v-t

Canceling Flow

20 u 10

s 30 t

10 v

10

s 10 t 10 v

20

Residual Graph Gf

G

Flow 6

u Cap10 v

Gf

Cap 4

uv

Cap 6

Example: residual graph

a2b

3

3G

1 4d3c3

Push 2 along s-d-b-t and draw the residual graph

s

2

t

Augmenting Path = Path in Gf

Let P be an s−t path in the residual graph Gf.

Let bottleneck(P) be the smallest capacity in Gf on any edge of P.

If bottleneck(P) > 0 then we can increase the flow by sending bottleneck(P) along the path P.

augment(f, P):

b = bottleneck(P)

for each e = (u,v) ∈ P:

if e is a forward edge:

decrease cf(e) by b //add some flow

else:

increase capacity by b //erase some flow

The Ford-Fulkerson Algorithm

Algorithm. Given (G, s, t, c)

start with f(u,v)=0 and Gf = G.

while exists an augmenting path in Gf

find bottleneck

augment the flow along this path

update the residual graph Gf

Example

a4b 286

10 c 9 d 10 Path s-a-c-d-t

10

s

10

t

Example

Path s-c-a-b-t

Path s-c-d-b-t

Path s-c-d-a-b-t

Example

10 a 1 b 3

s12716

9 c 9 d 10

Gf

1 9

t

In graph G edges are with flow/cap notation

G

a 3/4 b

9/10

0/2 7/8

9/10

10/10 s

t

c

9/9

6/6

d 10/10

The Ford-Fulkerson Algorithm Runtime Complexity

Algorithm. Given (G, s, t, c)

start with f(u,v)=0 and Gf = G.

while exists an augmenting path in Gf

find bottleneck

augment the flow along this path

update the residual graph

The worst-case

vct c1c

scu

c=109

O(|f| (E+V))

Proof of Correctness

How do we know the flow is maximum?

t

a 3/4 b 9/10

10 a 1 b 1 39

Gf

s12716

9 c 9 d 10

G

s

10/10 9/10

0/2

7/8 9/9

6/6 d

t

10/10

c

Cuts and Cut Capacity

10 a 4 b 10 s28

t

96

10 c d 10

Cuts and Flows

Consider a graph with some flow and cut

8/10 a 0/4 b

A s 0/2 8/8 2/6

2/10 c 2/9 d 8/10

The flow-out of A is ___

The flow-in to A is ___

The flow across (A,B) is ___

What is a flow value |f| in this graph?

2/10

B

t

Lemma 1

For any flow f and any (A,B) cut

𝑓 = 𝑓(𝑠,𝑣ሻ = 𝑓(𝑢,𝑣ሻ− 𝑓(𝑣,𝑢ሻ 𝑣 𝑢∈𝐴,𝑣∈𝐵 𝑢∈𝐴,𝑣∈𝐵

Lemma 2

For any flow f and any (A,B) cut |f| ≤ cap(A,B)

max 𝑓 ≤ min𝑐𝑎𝑝(𝐴,𝐵ሻ 𝑓 𝐴,𝐵

Max-flow Theorem

Theorem. The Ford-Fulkerson algorithm outputs

the maximum flow.

10/10

s

9/10

a 3/4 b

9/10

0/2

7/8 9/9

t

c

6/6

d 10/10

Discussion Problem 1

Run the Ford-Fulkerson algorithm on the following network:

16 B 12 C

19 49

T

S10 7

13 14 4

FE

How do you find a min-cut ? Is a min-cut unique?

Discussion Problem 2

You have successfully computed a maximum s-t flow for a network G = (V, E) with positive integer edge capacities. Your boss now gives you another network G’ that is identical to G except that the capacity of exactly one edge is decreased by one. You are also explicitly given the edge whose capacity was changed. Describe how you can compute a maximum flow for G’ in linear time.

12/16

S

11/13

B

12/12

C

19/19 0/4 0/9

4/4

T

0/10

7/7

11/14

FE

Discussion Problem 3

If we add the same positive number to the capacity of every directed edge, then the minimum cut (but not its value) remains unchanged. IF it is true, prove it, otherwise provide a counterexample.

Discussion Problem 4

In a daring burglary, someone attempted to steal all the candy bars from the CS department. Luckily, he was quickly detected, and now, the course staff and students will have to keep him from escaping from campus. In order to do so, they can be deployed to monitor strategic routes. Compute the minimum number of students/staff needed and show the monitored routes.

X Y

people tasks

Bipartite Graph

A graph is bipartite if the vertices can be partitioned into two disjoint (also called independent) sets X and Y such that all edges go only between X and Y (no edges go from X to X or from Y to Y). Often writes G = (X, Y, E).

Bipartite Matching

Definition. A subset of edges is a matching if no two edges have a common vertex (mutually disjoint).

Definition. A maximum matching is a matching with the largest possible number of edges

Goal. Find a maximum matching in G.

Solving by Reduction

Given an instance of bipartite matching.

Create an instance of network flow.

The solution to the network flow problem can easily be used to find the solution to the bipartite matching.

Reducing Bipartite Matching to Network Flow

Given bipartite G = (X, Y, E). Let |X|=|Y|=V.

X

Y

Max matching = Max flow

S

1

X

1

Y

1

T

Max matching = Max flow

S

1

X

1

Y

1

T

Runtime Complexity Given bipartite G = (X, Y, E). , |X|=|Y|=V.

Discussion Problem 5

We’re asked to help the captain of the USC tennis team to arrange a series of matches against UCLA’s team. Both teams have n players; the tennis rating of the i-th member of USC’s team is ai and the tennis rating for the k-th member of UCLA’s team is bk. We would like to set up a competition in which each person plays one match against a player from the opposite school. Our goal is to make as many matches as possible in which the USC player has a higher tennis rating than his or her opponent. Give an algorithm to decide which matches to arrange to achieve this objective.

Player

Rating

Team

A

10

Trojans

B

5

Trojans

C

15

Trojans

D

20

Trojans

E

7

Bruins

F

14

Bruins

G

16

Bruins

H

19

Bruins

How to improve

the efficiency of the Ford-Fulkerson Algorithm?

O(|f| (E+V)) v c=109 t

c1c scu

Edmonds-Karp algorithm

Algorithm. Given (G, s, t, c)

1) Start with |f|=0, so f(e)=0

2) Find a shortest augmenting path in Gf

3) Augment flow along this path

4) Repeat until there is no an s-t path in Gf

Theorem.

The runtime complexity of the algorithm is O(V E2).

(without proof)

Runtime history

O(m U) O(n m2)

n = V, m = E, U = |f|

shortest path capacity scaling

preflow-push

splay tree preflow-push

2013 Orlin

O(m n)

Discussion Problem 6

Professor Jones has determined that x priceless artifacts are located in a labyrinth. The labyrinth can be thought of as a graph, with each edge representing a path and each node an intersection of paths. All of the artifacts are in the same treasure room, which is located at one of the intersections. However, the artifacts are extremely burdensome, so Jones can only carry one artifact at a time. There is only one entrance to the labyrinth, which is also a node in the graph. The entrance serves as the only exit as well. All the paths are protected by human-eating vines, which will be woken up after someone passes the path, so Jones can only go through each path once. Give an algorithm that determines how many artifacts Jones can obtain and how he can do it.

4 25

1 s

t 6

3

Discussion Problem 7

We say that two paths are vertex-disjoint if they do

not share any vertices (except s and t).

Given a directed graph G = (V, E) with two distinguished nodes s, t. Design an algorithm to find the maximum number of vertex-disjoint s-t paths in G.

Discussion Problem 8

There are n students in a class. We want to choose a subset of k students as a committee. There has to be m1 number of freshmen, m2 number of sophomores, m3 number of juniors, and m4 number of seniors in the committee. Each student is from one of k departments, where k = m1 +m2 +m3 +m4. Exactly one student from each department has to be chosen for the committee. We are given a list of students, their home departments, and their class (freshman, sophomore, junior, senior). Describe an efficient algorithm based on network flow techniques to select who should be on the committee such that the above constraints are all satisfied.