CSC373编程代写、代写Java，Python程序

日期：2022-03-14 08:06

CSC373Week 5: Dynamic Programming (contd)Network Flow (start)

373W22 1

Karan Singh, Nathan Wiebe

*slides adapted from Nisarg Shah

Recap

373W22 2

Some more DP

Traveling salesman problem (TSP)

Start of network flow

Problem statement

Ford-Fulkerson algorithm

Running time

Correctness using max-flow, min-cut

This Lecture

373W22 3

Network flow in polynomial time

Edmonds-Karp algorithm (shortest augmenting path)

Applications of network flow

Bipartite matching & Hall’s theorem

Edge-disjoint paths & Menger’s theorem

Multiple sources/sinks

Circulation networks

Lower bounds on flows

Survey design

Image segmentation

Ford-Fulkerson Recap

373W22 4

Define the residual graph of flow

has the same vertices as

For each edge e = (, ) in , has at most two edges

o Forward edge = (, ) with capacity ?

We can send this much additional flow on

o Reverse edge = (,) with capacity ()

The maximum “reverse” flow we can send is the maximum amount by which we can

reduce flow on , which is ()

o We only add each edge if its capacity > 0

Ford-Fulkerson Recap

373W22 5

Example!

Flow Residual graph

Ford-Fulkerson Recap

373W22 6

MaxFlow():

// initialize:

Set = 0 for all in

// while there is an - path in :

While = FindPath(s, t,Residual(, ))!=None:

= Augment(,)

UpdateResidual(,)

EndWhile

Return

Ford-Fulkerson Recap

373W22 7

Running time:

#Augmentations:

o At every step, flow and capacities remain integers

o For path in , bottleneck , > 0 implies bottleneck , ≥ 1

o Each augmentation increases flow by at least 1

o At most = ∑ leaving () augmentations

Time for an augmentation:

o has vertices and at most 2 edges

o Finding an - path in takes ( + ) time

Total time: ( + ? )

Edmonds-Karp Algorithm

373W22 8

At every step, find the shortest path from to in , and

augment.

MaxFlow():

// initialize:

Set = 0 for all in

// Find shortest - path in & augment:

While = BFS(s, t,Residual(, ))!=None:

= Augment(,)

UpdateResidual(,)

EndWhile

Return

Minimum number of edges

Proof

373W22 9

() = shortest distance of from in residual graph

Lemma 1: During the execution of the algorithm, () does

not decrease for any .

Proof:

Suppose augmentation → decreases () for some

Choose the with the smallest in ′

o Say = in ′, so ≥ + 1 in

Look at node just before on a shortest path → in ′

o = ? 1 in ′

o () didn’t decrease, so ≤ ? 1 in

() = shortest distance of from in residual graph

Lemma 1: During the execution of the algorithm, () does

not decrease for any .

? In , (, ) must be missing

? We must have added (, ) by

selecting (,) in augmenting path

? But is a shortest path, so it cannot

have edge , with >

Proof

373W22 11

Call edge (, ) critical in an augmentation step if

It’s part of the augmenting path and its capacity is equal to bottleneck(, )

Augmentation step removes and adds (if missing)

Lemma 2: Between any two steps in which (, ) is critical,

() increases by at least 2

Proof of Edmonds-Karp running time

Each () can go from 0 to (Lemma 1)

So, each edge (, ) can be critical at most /2 times (Lemma 2)

So, there can be at most ? /2 augmentation steps

Each augmentation takes () time to perform

Hence, 2 operations in total!

Proof

373W22 12

Lemma 2: Between any two steps in which (, ) is critical,

() increases by at least 2

Proof:

Suppose (, ) was critical in

o So, the augmentation step must have removed it

Let = () in

o Because , is part of a shortest path, = + 1 in

For (, ) to be critical again, it must be added back at some point

o Suppose ′ → ′′ steps adds it back

o Augmenting path in must have selected (,)

o In ′: = + 1 ≥ + 1 + 1 = + 2

Lemma 1 on

Edmonds-Karp Proof Overview

373W22 13

Note:

Some graphs require Ω() augmentation steps

But we may be able to reduce the time to run each augmentation

step

Two algorithms use this idea to reduce run time

Dinitz’s algorithm [1970] ?(2)

Sleator–Tarjan algorithm [1983] ?( log)

o Using the dynamic trees data structure

373W22 14

Network Flow Applications

373W22 15

Rail network connecting Soviet Union with Eastern European countries

(Tolstoǐ 1930s)

373W22 16

Rail network connecting Soviet Union with Eastern European countries

(Tolstoǐ 1930s)

Min-cut

Integrality Theorem

373W22 17

Before we look at applications, we need the following special property of the

max-flow computed by Ford-Fulkerson and its variants

Observation:

If edge capacities are integers, then the max-flow computed by Ford-Fulkerson and its variants

are also integral (i.e., the flow on each edge is an integer).

Easy to check that each augmentation step preserves integral flow

Bipartite Matching

373W22 18

Problem

Given a bipartite graph = ( ∪ ,), find a maximum cardinality matching

We do not know any efficient greedy or dynamic programming algorithm for this

problem.

But it can be reduced to max-flow.

Bipartite Matching

373W22 19

Create a directed flow graph where we…

Add a source node and target node

Add edges, all of capacity 1:

o → for each ∈ , → for each ∈

o → for each , ∈

Bipartite Matching

373W22 20

Observation

There is a 1-1 correspondence between matchings of size in the original graph and flows

with value in the corresponding flow network.

Proof: (matching ? integral flow)

Take a matching = 1, 1 , … , , of size

Construct the corresponding unique flow where…

o Edges → , → , and → have flow 1, for all = 1, … ,

o The rest of the edges have flow 0

This flow has value