CS计算机代考程序代写 algorithm Network Flow

Network Flow
Ford – Fulkerson algorithm
2021-02-22 CSC373 Winter 2021 – Sam Toueg 1

Example and Main Concepts
2021-02-22 CSC373 Winter 2021 – Sam Toueg 2

Network Flow
Flow Network F = ($,&,’,() 25
0 15 1
10
*
• ! = ($, &): directed graph ( • (∈$:noincomingedge
5
+ 20
• •
* ∈ $: no outgoing edge
+: capacity function & → R!”
Ø +(., /) capacity of edge (., /) ∈ &
15
30
2
15 10
2021-02-22 CSC373 Winter 2021 – Sam Toueg
3

Network Flow
Flow Network F = ($, &, ‘, ()
• ! = ($, &): directed graph (
• ( ∈ $: no incoming edge
• * ∈ $: no outgoing edge
• +: capacity function & → R!”
Ø +(., /) capacity of edge (., /) ∈ & Flow *: , → . that respects
Aflow! withvalue” ! =20
20/25 0 5/5
0/15
+
15/15 10/15
1 5/10 0/10 *
15/30 15/20 2
1. Capacity constraints: ∀7 ∈ &: 0 ≤ ; 7 ≤ +(7)
2. Flowconservation:∀/∈$−{(,*}: ∑#$%&'(; 7 =∑#)*+,*(; 7
Notation
• ;-.//=∑#)*+,$%0(;7
• ;12/=∑#$%&'(;7
• Valueofflow;is/ ; =;-./ (
2021-02-22 CSC373 Winter 2021 – Sam Toueg !!” ” = !#$% ” = 13 4

Max Flow Problem
• Problem
ØInput: flow network F = ($, &, ‘, () & ØOutput: flow * of max value, i.e., ∀ 0low * , 4 *
≥ 4(*′)
u
s 30 t
20
10
10
20
2021-02-22
CSC373 Winter 2021 – Sam Toueg
5
v

Max Flow Problem
• Problem
ØInput: flow network F = ($, &, ‘, () & ØOutput: flow * of max value, i.e., ∀ 0low * , 4 *
Suppose we start by sending 20 units of flow along this path
≥ 4(*′)
u
%&/30 t
%&/20
But this is NOT a max flow!
%&/20 s
0/10
0/10
2021-02-22
CSC373 Winter 2021 – Sam Toueg
7
v

Max Flow Problem
• Problem
ØInput: flow network F = ($, &, ‘, () &
ØOutput: flow * of max value, i.e., ∀ 0low * , 4 * ≥ 4(*′)
Suppose we start by sending A max flow
20 units of flow along this path Note: 10 fewer units of flow on * → ”
uu
%&/20 s
0/10
0/10 %&/30
%&/20
t
s
%&/20 (&/10 (&/30
(&/10 %&/20
t
2021-02-22
CSC373 Winter 2021 – Sam Toueg
8
vv

Max Flow Problem
• Problem
ØInput: flow network F = ($, &, ‘, () &
ØOutput: flow * of max value, i.e., ∀ 0low * , 4 * ≥ 4(*′)
A max flow
Note: 10 fewer units of flow on * → ”
uu
%&/20 0/10 s %&/30
(&/10 %&/20
t
s
%&/20 (&/10 (&/30
(&/10 %&/20
t
vv
2021-02-22 CSC373 Winter 2021 – Sam Toueg
10

Max Flow Problem
• Problem
ØInput: flow network F = ($, &, ‘, () &
ØOutput: flow * of max value, i.e., ∀ 0low * , 4 * ≥ 4(*′)
We can send a “reverse” flow of 10 A max flow unitsalong”→*! Note: 10fewerunitsofflowon*→”
uu
%&/20 0/10 s (&%&/30
(&/10 %&/20
t
s
%&/20 (&/10 (&/30
(&/10 %&/20
t
vv
2021-02-22 CSC373 Winter 2021 – Sam Toueg
11

Max Flow Problem
• Problem
ØInput: flow network F = ($, &, ‘, () &
ØOutput: flow * of max value, i.e., ∀ 0low * , 4 * ≥ 4(*′)
We can send a “reverse” flow of 10 units along ” → * !
So now we get an optimal flow uu
%&/20 (&/10 s (&%&/30
(&/10 %&/20
t
s
%&/20 (&/10 (&/30
(&/10 %&/20
t
vv
2021-02-22 CSC373 Winter 2021 – Sam Toueg
12

Residual Graph
Residual graph $, of flow *:
• !3 has the same vertices as !
• Foreachedgee=(.,/)in!,!3 hasatmosttwoedges:
•
1. Forward edge 7 = (.,/) with residual capacity + 7 − ; 7 > 0 Ø We can send this much additional flow on 7
2. Reverse edge 74#( = (/, .) with residual capacity ;(7) > 0
Ø The maximum “reverse” flow that we can send on edge 7; this is the
maximum amount we can reduce the flow on 7, which is ; 7
We added a (forward or reverse) edge to !3 only if its residual capacity > 0!
u
s 20/30 t
u s%&(& t
forward
reverse
Flow !
20/20
Residual graph -&
%&
(&
0/10
0/10 20/20
(&
%&
2021-02-22
CSC373 Winter 2021 – Sam Toueg
13
v
v

Augmenting Paths
• Let!bean”⤳$pathintheresidualgraph%)
• bottleneck !, / : smallest residual capacity among all edges in !
• “Augment” flow / by “sending” bottleneck !, / units of flow along !
Ø What does it mean to send 1 > 0 units of flow along !? For each forward edge 7 ∈ C, increase the flow on 7 by D For each reverse edge 74#( ∈ C, decrease the flow on 7 by D
• Let’s first argue that the new flow /′ is better than /
an augmenting path u
augmented flow u
forward
reverse
Flow ! !′ 20/20
Residual graph -&
s%&(& t
10/10
s 10/30 t
%&
(&
(&
%&
10/10 2021-02-22
20/20
v
v
CSC373 Winter 2021 – Sam Toueg
24

Augmenting Paths
• Let!bean”⤳$pathintheresidualgraph%)
• bottleneck !, / : smallest residual capacity among all edges in !
• “Augment” flow / by “sending” bottleneck !, / units of flow along !
Ø What does it mean to send 1 > 0 units of flow along !? For each forward edge 7 ∈ C, increase the flow on 7 by D For each reverse edge 74#( ∈ C, decrease the flow on 7 by D
• Let’s first argue that the new flow /′ is better than /
Ø Note that the first edge (, . of C in !3 must be a forward edge
(because the original graph ! has no edge into (!) ØSo;′((,.)=; (,. +DwithD>0
⇒/;5 ≥/;+D
2021-02-22 CSC373 Winter 2021 – Sam Toueg 25

Augmenting Paths
• Let!bean”⤳$pathintheresidualgraph%)
• bottleneck !, / : smallest residual capacity among all edges in !
• “Augment” flow / by “sending” bottleneck !, / units of flow along !
Ø What does it mean to send 1 > 0 units of flow along !? For each forward edge 7 ∈ C, increase the flow on 7 by D For each reverse edge 74#( ∈ C, decrease the flow on 7 by D
• Let’s now argue that the new flow /′ is a valid flow
• (1) Capacity constraints:
Ø If we increased the flow on 7, we did so by at most the residual capacity of forwardedge7in!3,whichis+ 7 −; 7
⇒thenewflow;5(7)isatmost; 7 + + 7 −; 7 =+(7)
Ø If we decreased the flow on 7, we did so by at most the residual capacity of
reverse edge 74#( in !3, which is ; 7 ⇒thenewflow;5(7)isatleast; 7 −; 7 =0
2021-02-22 CSC373 Winter 2021 – Sam Toueg 27

Augmenting Paths
• (2) Flow conservation: Augmenting path in residual graph -&:
svt
FF FR
RF RR
+0 +0
−0 −0
In -: +0 v
both in and out edges increase by 0
no change
no change
both in and out edges decrease by 0
4 possible cases:
v
v
v
−0 +0 −0
2021-02-22
CSC373 Winter 2021 – Sam Toueg
30

Augmenting Paths
• (2) Flow conservation: Augmenting path in residual graph -&:
svt
FF FR
RF RR
Flow ! 20/20
Residual graph -& 0/10 %&
u
(&
F
R
u
s 20/30 t s %&(& t
0/10
+0 +0
−0 −0
20/20 (&
%&
v
In -: +0
v
both in and out edges
increase by 0 no change
no change
both in and out edges decrease by 0
4 possible cases:
v v
v v
−0 +0 −0
2021-02-22
CSC373 Winter 2021 – Sam Toueg
31

The Algorithm
2021-02-22 CSC373 Winter 2021 – Sam Toueg 32

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(.,/)of!do; .,/ =0 construct !3
while!3 hasan(⤳*pathdo:
C ← any simple ( ⤳ * path in !3 ; ← augment(;, C)
update !3
F = ($, &, ‘, ()
return ;
!00/151 -&0151
0/25 0/10 25
( 0/5 0/15 0/10 * ( 5 15 10
10
*
30
0/15
0/30 15 CSC373 Winter 2021 – Sam Toueg
+ 0/20 2
+ 20 2
2021-02-22
33

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(.,/)of!do; .,/ =0 construct !3
while!3 hasan(⤳*pathdo:
C ← any simple ( ⤳ * path in !3 ; ← augment(;, C)
update !3
return ;
!00/151 -&0151
10 ( 0/5 0/15 0/10 * ( 5 15 10
bottleneck in augmenting path 0/25 0/10 25
0/15
0/30 15 CSC373 Winter 2021 – Sam Toueg
*
30
+ 0/20 2
+ 20 2
2021-02-22
38

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(.,/)of!do; .,/ =0 construct !3
while!3 hasan(⤳*pathdo:
C ← any simple ( ⤳ * path in !3 ; ← augment(;, C)
update !3
return ;
!00/151 -&0151
5/25 0/10 25
( 0/5 0/15 0/10 * ( 5 15 10
10
*
30
0/15
0/30 15 CSC373 Winter 2021 – Sam Toueg
+ 0/20 2 augmenting flow !
+ 20 2
2021-02-22
40

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(.,/)of!do; .,/ =0 construct !3
while!3 hasan(⤳*pathdo:
C ← any simple ( ⤳ * path in !3 ; ← augment(;, C)
update !3
return ;
!00/151 -&0151
5/25 0/10 25
( 5/5 0/15 0/10 * ( 5 15 10
10
*
30
0/15
0/30 15 CSC373 Winter 2021 – Sam Toueg
+ 0/20 2 augmenting flow !
+ 20 2
2021-02-22
41

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(.,/)of!do; .,/ =0 construct !3
while!3 hasan(⤳*pathdo:
C ← any simple ( ⤳ * path in !3 ; ← augment(;, C)
update !3
return ;
!00/151 -&0151
5/25 0/10 25
( 5/5 0/15 0/10 * ( 5 15 10
10
*
30
0/15
0/30 15 CSC373 Winter 2021 – Sam Toueg
+ 5/20 2 augmenting flow !
+ 20 2
2021-02-22
42

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(.,/)of!do; .,/ =0 construct !3
while!3 hasan(⤳*pathdo:
C ← any simple ( ⤳ * path in !3 ; ← augment(;, C)
update !3
now update -& !00/151 -&0151
10 ( 5/5 0/15 0/10 * ( 5 15 10
return ;
5/25 0/10 25
0/15
5/30 15 CSC373 Winter 2021 – Sam Toueg
*
30
+ 5/20 2 augmented flow
+ 20 2
2021-02-22
44

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(.,/)of!do; .,/ =0 construct !3
while!3 hasan(⤳*pathdo:
C ← any simple ( ⤳ * path in !3 ; ← augment(;, C)
update !3
now update -& !00/151 -&50151
return ;
5/25 0/10 20
10 30
45
( 5/5 0/15 0/10 * ( 5 15 10
*
0/15
5/30 15 CSC373 Winter 2021 – Sam Toueg
+ 5/20 2 augmented flow
+ 20 2
2021-02-22

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(.,/)of!do; .,/ =0 construct !3
while!3 hasan(⤳*pathdo:
C ← any simple ( ⤳ * path in !3 ; ← augment(;, C)
update !3
find another augmentation path in -& !00/151 -&50151
return ;
5/25 0/10 20
10 25
( 5/5 0/15 0/10 * ( 5 15 10
*
0/15
5/30 15 CSC373 Winter 2021 – Sam Toueg
+ 5/20 2
5 5
+ 15 2
2021-02-22
49

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(.,/)of!do; .,/ =0 construct !3
while!3 hasan(⤳*pathdo:
C ← any simple ( ⤳ * path in !3 ; ← augment(;, C)
update !3
find another augmentation path in -& !00/151 -&50151
return ;
5/25 0/10 20
10 25
( 5/5 0/15 0/10 * ( 5 15 10
*
5
0/15
5/30 15 CSC373 Winter 2021 – Sam Toueg
+ 5/20 2
+ 15 2 5
2021-02-22
50

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(.,/)of!do; .,/ =0 construct !3
while!3 hasan(⤳*pathdo:
C ← any simple ( ⤳ * path in !3 ; ← augment(;, C)
update !3
return ;
! 010/151 -&50151
15/25 10/10 20
( 5/5 0/15 0/10 * ( 5 15 10
10 25
*
5
0/15
5/30 15 CSC373 Winter 2021 – Sam Toueg
+ 5/20 2 augmented flow
+ 15 2 5
2021-02-22
51

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(.,/)of!do; .,/ =0 construct !3
while!3 hasan(⤳*pathdo:
C ← any simple ( ⤳ * path in !3 ; ← augment(;, C)
update !3
return ;
! 010/151
now update -& -&50151
15/25
( 5/5 0/15 0/10 * ( 5 15 10
0/15
10/10 20 5/30 15
10 25
*
5
+ 5/20 2 augmented flow
+ 15 2 5
2021-02-22
CSC373 Winter 2021 – Sam Toueg
52

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(.,/)of!do; .,/ =0 construct !3
while!3 hasan(⤳*pathdo:
C ← any simple ( ⤳ * path in !3 ; ← augment(;, C)
update !3
find another augmentation path in -& 10
return ;
! 010/151
-&15051 10/10 10
10 ( 5/5 0/15 0/10 * ( 5 15 10
15/25
*
0/15
5/30 15 CSC373 Winter 2021 – Sam Toueg
25
+ 5/20 2
5 5
+ 15 2
2021-02-22
56

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(.,/)of!do; .,/ =0 construct !3
while!3 hasan(⤳*pathdo:
C ← any simple ( ⤳ * path in !3 ; ← augment(;, C)
update !3
find another augmentation path in -& 10
return ;
! 010/151
-&15051 10/10 10
10 ( 5/5 0/15 0/10 * ( 5 15 10
15/25
*
0/15
5/30 15 CSC373 Winter 2021 – Sam Toueg
25
+ 5/20 2
5 5
+ 15 2
2021-02-22
57

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(.,/)of!do; .,/ =0 construct !3
while!3 hasan(⤳*pathdo:
C ← any simple ( ⤳ * path in !3 ; ← augment(;, C)
update !3
find another augmentation path in -& 10
return ;
! 010/151
-&15051 10/10 10
10
*
25
5
15/25
( 5/5 0/15 0/10 * ( 5 15 10
0/15
5/30 15 CSC373 Winter 2021 – Sam Toueg
+ 5/20 2
+ 15 2 5
2021-02-22
58

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(.,/)of!do; .,/ =0 construct !3
while!3 hasan(⤳*pathdo:
C ← any simple ( ⤳ * path in !3 ; ← augment(;, C)
update !3
return ;
! 010/151
10 -&15051
10
*
25
5
15/25
( 5/5 0/15 0/10 * ( 5 15 10
15/15
10/10 10 20/30 15
+ 20/20 2 augmented flow
+ 15 2 5
2021-02-22
CSC373 Winter 2021 – Sam Toueg
59

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(.,/)of!do; .,/ =0 construct !3
while!3 hasan(⤳*pathdo:
C ← any simple ( ⤳ * path in !3 ; ← augment(;, C)
update !3
now update -&
10
return ;
! 010/151
-&15051 10/10 10
10
*
25
5
15/25
( 5/5 0/15 0/10 * ( 5 15 10
15/15
20/30 15 CSC373 Winter 2021 – Sam Toueg
+ 20/20 2 augmented flow
+ 15 2 5
2021-02-22
60

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(.,/)of!do; .,/ =0 construct !3
!
-& 15 10
051 5 1510
10
while!3 hasan(⤳*pathdo:
C ← any simple ( ⤳ * path in !3 ; ← augment(;, C)
update !3
return ;
find another augmentation path in -& 10
0 10/15 1
( 5/50/150/10 * (
15/15
+
15/25
10/10
* 2 15+220
20/30
10
20/20
2021-02-22
CSC373 Winter 2021 – Sam Toueg
64
20

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(.,/)of!do; .,/ =0 construct !3
while!3 hasan(⤳*pathdo:
C ← any simple ( ⤳ * path in !3 ; ← augment(;, C)
update !3
return ;
10
051 5 1510
!
-& 15 10
10
0 15/15 1
( 5/50/155/10 * (
15/15
+
20/25
10/10
* 2 15+220
25/30
10
20/20 augmented flow
20
2021-02-22
CSC373 Winter 2021 – Sam Toueg
66

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(.,/)of!do; .,/ =0 construct !3
!
-& 15 10
051 5 1510
10
while!3 hasan(⤳*pathdo:
C ← any simple ( ⤳ * path in !3 ; ← augment(;, C)
update !3
return ;
now update -&
10
0 15/15 1
( 5/50/155/10 * (
15/15
+
20/25
10/10
* 2 15+220
25/30
10
20/20 augmented flow
20
2021-02-22
CSC373 Winter 2021 – Sam Toueg
67

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(.,/)of!do; .,/ =0 construct !3
!
-& 20 5
01
while!3 hasan(⤳*pathdo:
C ← any simple ( ⤳ * path in !3 ; ← augment(;, C)
update !3
return ;
find another augmentation path in -& 15
0 15/15 1
( 5/50/155/10 * (
20/25
10/10
10 5 15 5
* 2 15+225
20
5
15/15
+
25/30
5
20/20
2021-02-22
CSC373 Winter 2021 – Sam Toueg
72

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(.,/)of!do; .,/ =0 construct !3
while!3 hasan(⤳*pathdo:
C ← any simple ( ⤳ * path in !3 ; ← augment(;, C)
update !3
return; ” ! =20+15=35
there is no : ⤳ < path in -& Finito! Return ! 15 * 2 15+225 20 ! -& 20 5 01 0 15/15 1 ( 5/50/155/10 * ( 20/25 10/10 10 5 15 5 5 15/15 + 25/30 5 20/20 2021-02-22 CSC373 Winter 2021 - Sam Toueg 73 Ford-Fulkerson Algorithm Ford-Fulkerson(F): foreachedge(.,/)of!do; .,/ =0 construct !3 while!3 hasan(⤳*pathdo: C ← any simple ( ⤳ * path in !3 ; ← augment(;, C) update !3 return ; nodes reachable from :: ? = {:, D} not reachable from :: A = {F, G, H, <} 15 :−< cut (?, A) * 2 15+225 20 ! -& 20 5 01 0 15/15 1 ( 5/50/155/10 * ( 20/25 10/10 10 5 15 5 5 15/15 + 25/30 5 20/20 2021-02-22 CSC373 Winter 2021 - Sam Toueg 74

Related Posts