最大流问题[稻谷书苑]

1、第第1页页 第八章第八章图与网络分析图与网络分析 图的基本概念与模型图的基本概念与模型 树图和图的最小部分树树图和图的最小部分树 最短路问题最短路问题 网络最大流问题网络最大流问题 最小费用最大流问题最小费用最大流问题 第第2页页 第八章第八章图与网络分析图与网络分析 图的基本概念与模型图的基本概念与模型 树图和图的最小部分树树图和图的最小部分树 最短路问题最短路问题 网络最大流问题网络最大流问题 最小费用最大流问题最小费用最大流问题 第第3页页 网络最大流问题网络最大流问题 50年代福特（年代福特（Ford）、富克逊（）、富克逊（Fulkerson）建立）建立 的的“网络流理论网络流理论”，

2、是网络应用的重要组成部分。，是网络应用的重要组成部分。 如同我们可以把一个实际的道路地图抽象成一个如同我们可以把一个实际的道路地图抽象成一个有向有向 图图来计算两点之间的来计算两点之间的最短路径最短路径，我们也可以将一个，我们也可以将一个有向图有向图 看作一个看作一个流网络流网络来解决另一类型的问题。来解决另一类型的问题。 流网络比较适合用来流网络比较适合用来模拟液体流经管道模拟液体流经管道、电流电流在电路在电路 网络中的运动、网络中的运动、信息信息网络中信息的传递等等类似的过程。网络中信息的传递等等类似的过程。 第第4页页 问题的提出问题的提出 在一个在一个输油管网输油管网中，有生产石油的中

3、，有生产石油的油井油井、储存石油的、储存石油的油油 库库、转运石油的中间、转运石油的中间泵站泵站，同时，还有各种口径不同的，同时，还有各种口径不同的输油输油 管管。当一个输油管网给定后，单位时间内最多可把多少石油。当一个输油管网给定后，单位时间内最多可把多少石油 从油井输送到油库？具体方案如何？从油井输送到油库？具体方案如何？ 分析：分析：就输油管网络问题，可用就输油管网络问题，可用顶点顶点表示油井、油表示油井、油 库和中间泵站，用库和中间泵站，用有向边有向边表示输油管，用有向边上表示输油管，用有向边上 的的权权表示单位时间沿相应的输油管可以输送石油的表示单位时间沿相应的输油管可以输送石油的

4、最大数量（最大数量（容量容量）。）。 第第5页页 如果我们把图看做输油管道网，如果我们把图看做输油管道网， 为起点，为起点， 为终点，为终点， 为中转站，为中转站，边上的数表示该管道的最边上的数表示该管道的最 大输油能力大输油能力，问应该如何安排各管道输油量，才能，问应该如何安排各管道输油量，才能 使从使从 到到 的的总输油量最大总输油量最大？ t v s v 1234 ,v v v v t v s v 问题的提出问题的提出 管道网络中每边的最大通过能力即管道网络中每边的最大通过能力即容量容量是有限的，实际是有限的，实际流流 量量也不一定等于容量，上述问题就是要讨论如何充分利用也不一定等于容量

5、，上述问题就是要讨论如何充分利用 装置的能力，以取得最好效果（流量最大），这类问题通装置的能力，以取得最好效果（流量最大），这类问题通 常称为常称为最大流问题最大流问题。 vs v1v3 vt v2v4 8 7 9 9 5 6 2 5 10 第第6页页 容量容量 发点（源）发点（源） 收点（汇）收点（汇） 中间点中间点 容量网络容量网络 ( ,) ij Dv v的每条弧上有非负数 的点的点一个入次为一个入次为0 s v 的点的点一个出次为一个出次为0 t v 其余点其余点 ( , ,)DV A C ij c 网络有向图网络有向图D=D=（V V，A A，C C） 网络上流的基本概念网络上流的基

6、本概念 vs v1v3 vt v2v4 8 7 9 9 5 6 2 5 10 流流 ( ,) ijij v vf对D中任一弧都给定一个实际流量 ij ff 集合集合 (1) (2) 满足下面条件的流： 容量限制条件 中间点平衡条件 ijij cf 0 j ij k ki ff 输出量输出量中间点的输入量中间点的输入量 ( )( ) sjjt jj v fstv fff 用表示网络中从的流量 vs v1v3 vt v2v4 8(8) 7(5) 9(4) 9(9) 5(5) 6(1) 2(0) 5(4) 10(8) 00f 任何网络必存在可行流，如流量为 的可行流： 运输问题中，每个运运输问题中，

7、每个运 输方案就是一个流输方案就是一个流 可行流可行流 第第8页页 ( ) ij fv f在容量网络中，寻求一个流使其流量最大 网络最大流问题网络最大流问题 ijij cf 0 ( ) 0 ( ) ijji v f ff v f ( , ) tj v vA ()is (, )is t ()i t 且满足 此为一个此为一个特殊的线性规划问题特殊的线性规划问题，将会看到利用图的特点，将会看到利用图的特点， 解决这个问题的方法要比单纯形法较为直观方便。解决这个问题的方法要比单纯形法较为直观方便。 第第9页页 设设 是是网络网络D=D=（V V，A A，C C）的）的一个可行流一个可行流 （v1，v2

8、）是饱和的是饱和的 2、如果、如果0fij0，该弧是该弧是非非0弧弧； （v1，v2）是非是非0弧弧 3、如果、如果fij ij= =0，该弧是 ，该弧是0 0流弧流弧； 弧关于流的分类弧关于流的分类 ij ff v1v2 v1v2 第第11页页 链及可增广链链及可增广链 链链 在最大流问题中，研究的是有向网络图。但是在求最大流在最大流问题中，研究的是有向网络图。但是在求最大流 的方法中，则要使用无向网络中的链。的方法中，则要使用无向网络中的链。 , stst vvvv D中，若 为从 到 的一条链，给 定向为从 到 前向弧集：与 同向 后向弧集：与 反向， vs v1v3 vt v2v4 8

9、(8) 7(5) 9(4) 9(9) 5(5) 6(1) 2(0) 5(4) 10(8) ( ,) ( ,) ijij ijij ij fv v ffv v f 非增广链上的弧 (,) (,) min0 ijijij ij ijij ij cfv v fv v ()( )v fv f 11 fc 3 0f 22 fc 0( ,) 0( ,) ijijij ijijij st f fcv v fcv v fvv 是可行流， 每一个 若 每一个 则称 为关于可行流 的从 到 的可增广链。 非非0流弧流弧 可增广链可增广链 1 0 n f nn fc vs v1v3 vt v2v4 8(8) 7(5

10、) 9(4) 9(9) 5(5) 6(1) 2(0) 5(4) 10(8) 非饱和弧非饱和弧 第第13页页 11 VV 割集和割集的容量割集和割集的容量 )( 111 VVVV和 11 ,VvVv ts 1 V 1 V ),( 11 VV 设有网络设有网络D=VD=V，A A，CC，点，点v vs s与点与点v vt t的是集合的是集合V V中的任意两中的任意两 点，若点集点，若点集V V被剖分成两个非空集合被剖分成两个非空集合 ，使，使 ，记以，记以中的点为中的点为始点始点， 的的A A中弧的集合记为中弧的集合记为 则称这个弧的集合则称这个弧的集合是分离点是分离点v vs s与点与点v vt

11、 t的的割集割集（又称截集）。（又称截集）。 中的点为中的点为终点终点 割集的容量割集的容量是割集中各弧的容量之和，用是割集中各弧的容量之和，用 表示。表示。 11 ( ,)c V V 1324 ( ,),(,)v vv v 112134 , , t Vs v vVv v v 割集的容量为割集的容量为9+9=189+9=18 割集割集 K K 割集的意义割集的意义：若把某一割集的弧从网络中丢去，：若把某一割集的弧从网络中丢去， 则则从从vs到到vt便不存路，即便不存路，即割集是从割集是从vs到到vt的必经之的必经之 道！道！这里这里(v3,v2)不属于此割集不属于此割集 vs v1v3 vt

12、v2v4 8(8) 7(5) 9(4) 5(5) 6(1) 2(0) 5(4) 10(8) 9(9) 考虑考虑KK的不同画法的不同画法 vs v1v3 vt v2v4 8(8) 7(5) 9(4) 9(9) 5(5) 6(1) 2(0) 5(4) 10(8) 1234 ,v v v v t 34 (, ),(, )vtvt 12 ( ,),( ,)s vs v 1 , s v s 2 ,s v 12 ,s v v 13 ,s v v 24 ,s v v 123 ,s v v v 124 ,s v v v 1234 ,s v v v v 234 ,v v v t 134 ,v v v t 134

13、 ,v v v t 24 ,v v t 13 ,v v t 1234 ,v v v v t 4, v t t 21213 ( ,),(,),(,)s vv vv v 124 ( ,),(,)s vvv 1324 (,),(,)v vvv 212323 ( ,),(,),(,),(, )s vv vv vv t 1434 ( ,),(,),(, )s vvvvt 243 (,),(, )vvv t 13434 ( ,),(,),(, )v vvvvt 15 21 17 18 19 24 14 25 15 V V 割集割集割集容量割集容量 由于有限网络的割集只有有限多个，则截集容量的集由于有限网络

14、的割集只有有限多个，则截集容量的集 合合是有限的实数集合，令是有限的实数集合，令 称割集容量为称割集容量为C0 0的割集为的割集为D D的最小割集。（的最小割集。（瓶颈瓶颈） 11 (,)C V V 011 ( ,)Cmin C V V 第第15页页 1111 11 ( , ,), ( ),( ,),( ,) ( )( ,) st st fDV A Cvv W fV Vv vV V W fC V V 设 为网络的任一可行流( 为发点为收点）， 流量为是分离的任一割集，割集容量为C 则有 基本定理基本定理(可行流与割集的关系可行流与割集的关系) 最大流最大流-最小割定理：最小割定理： 的最小割的

15、容量的最小割的容量分离分离 的最大流的流量的最大流的流量到到从从 中，中，任一个网络任一个网络 ts ts vv vv G , 的的可可增增广广链链到到不不存存在在从从 是是最最大大流流可可行行流流 ts vv f 第第16页页 这样就得到了一个这样就得到了一个寻求最大流的方法寻求最大流的方法(算法思想算法思想)： 从一个从一个可行流可行流开始，寻求关于这个可行流的开始，寻求关于这个可行流的可增可增 广链广链，若存在，则可以经过调整，得到一个新的，若存在，则可以经过调整，得到一个新的 可行流，其流量比原来的可行流要大，重复这个可行流，其流量比原来的可行流要大，重复这个 过程，直到不存在关于该流

16、的可增广链时过程，直到不存在关于该流的可增广链时 就得到了最大流。就得到了最大流。 沿着这条链从沿着这条链从 vs 到到 vt 输送流，还有潜力可挖，输送流，还有潜力可挖， 只需按照只需按照调整方法调整方法，就可以把流量提高，调整后，就可以把流量提高，调整后 的流，在各点仍满足平衡条件及容量限制条件，的流，在各点仍满足平衡条件及容量限制条件， 即仍为可行流。即仍为可行流。 可增广链可增广链的实际意义的实际意义 求解最大流的标号算法：求解最大流的标号算法： 1.() 1( ,) 2,: ( ) ,min,(,) ( ) 0,min,(,) (3)(2 s iij ji ijijjijijiij

17、ji jijjiiij v vvv avv fccfv bvv ffv 标号过程 寻找可增广链 ： （ ）给 以标号 （ ）对已标号的考虑 的所有未标号的邻接点 若是 发出的前向非饱和弧的终点， 即令标号为；否则不标号 对是 发出的后向非零弧的起点， 即令标号为；否则不标号 重复 ) 2. 1 21 tst ijt ijijt ij vvv f ff f f 直到 若 未得到标号，说明不存在 到 的增广链； 否则按如下方法调整。 调整过程（增加流量）： 增广链上的前向弧 （ ）令增广链上的后向弧 不在增广链上 （ ）去掉所有标号，回到第 步，对可行流重新标号。 ()( ) t w fw f则有

18、 1 v 2 v 3 v b)b)接着检查与相邻接的点接着检查与相邻接的点 1 v 3 v 2 v 4 v 5 v s v t v 6 v )5 , 5( )2 , 3( )2 , 4( )2 , 5( )2 , 4( )4 , 5( )3 , 3( )3 , 3( )0 , 3( )2 , 2( )2 , 2( ),( 已饱和，流量不可再增。再检查已饱和，流量不可再增。再检查 ，可调整量为，可调整量为 4-2=2， 可提供量可提供量+，取调整量，取调整量 1 v2 v 2 min42,2 a) 先给标号先给标号 （，+） 1） 寻找可增广链：寻找可增广链： s v 1 v 3 v 2 v 4

19、 v 5 v s v t v 6 v )5 , 5( )2 , 3( )2 , 4( )2 , 5( )2 , 4( )4 , 5( )3 , 3( )3 , 3( )0 , 3( )2 , 2( )2 , 2( ),( 3 v) 1,( s v c) 下对已标号点（可望调整点）接着向下检查。下对已标号点（可望调整点）接着向下检查。 已饱已饱 和。再检查与和。再检查与 相邻接且未标号的点相邻接且未标号的点 6 v 2 v, 5 v 6 v 给给 标号标号 ，其中，其中 表示表示 的所调整量的所调整量2来自来自 ， 且为正向流（向前流）且为正向流（向前流） 。 )2 ,( s v s v 2 v

20、 s v 2 v )2 ,( s v ) 1 ,( s v 调整量为调整量为 1 v 3 v 2 v 4 v 5 v s v t v 6 v )5 , 5( )2 , 3( )2 , 4( )2 , 5( )2 , 4( )4 , 5( )3 , 3( )3 , 3( )0 , 3( )2 , 2( )2 , 2( ),( )2 ,( s v ) 1 ,( s v 5 min30, 22 )2 ,( 2 v 5 v 给给 标号为标号为 )2 ,( 2 v 1 v 3 v 2 v 4 v 5 v s v t v 6 v )5 , 5( )2 , 3( )2 , 4( )2 , 5( )2 , 4

21、( )4 , 5( )3 , 3( )3 , 3( )0 , 3( )2 , 2( )2 , 2( ),( )2 ,( s v ) 1 ,( s v )2 ,( 2 v 可令调整量为可令调整量为 1 min3, 22 )2 ,( 5 v 给给 标号为标号为 )2 ,( 5 v 1 v表示可控量，反方向流量表示可控量，反方向流量。 5 v , 0 15 f d) 检查与检查与 相邻接且未标号的点相邻接且未标号的点 ， 。而。而 对对 来讲是来讲是 流流 入，现欲增加流出量，应该压缩入，现欲增加流出量，应该压缩 的流入量，只要的流的流入量，只要的流 入量入量 1 v t v 1 v 5 v 1 v

22、 1 v 3 v 2 v 4 v 5 v s v t v 6 v )5 , 5( )2 , 3( )2 , 4( )2 , 5( )2 , 4( )4 , 5( )3 , 3( )3 , 3( )0 , 3( )2 , 2( )2 , 2( ),( )2 ,( s v ) 1 ,( s v )2 ,( 2 v )2 ,( 5 v f) 下面检查与下面检查与 相邻接且未标号的点相邻接且未标号的点 ，同理，调整量：，同理，调整量： 1 v 4 v 4 min52, 22 给给 标号为标号为 ).2 ,( 1 v 4 v )2 ,( 1 v )2 ,( 4 v g) 最后，给最后，给 标号标号 t

23、v).2 ,( 4 v min42, 22 t 1 v 3 v 2 v 4 v 5 v s v t v 6 v )5 , 5( )2 , 3( )2 , 4( )2 , 5( )2 , 4( )4 , 5( )3 , 3( )3 , 3( )0 , 3( )2 , 2( )2 , 2( ),( )2 ,( s v ) 1 ,( s v )2 ,( 2 v )2 ,( 5 v )2 ,( 1 v )2 ,( 4 v 2）调整流量：从）调整流量：从 到到 所画出的所画出的红线红线即为即为可增广链可增广链。沿。沿 该可增广链，从该可增广链，从 倒推，标倒推，标“”号的在实际流量上加上号的在实际流量上

24、加上 该调整量，标该调整量，标“”符号的在实际流量上减去该调整量。符号的在实际流量上减去该调整量。 完完 成调整过程。成调整过程。 s v t v t v 反反 向向 追追 踪踪 1 v 3 v 2 v 4 v 5 v s v t v 6 v )5 , 5( )2 , 3( )2 , 4( )2 , 5( )2 , 4( )4 , 5( )3 , 3( )3 , 3( )0 , 3( )2 , 2( )2 , 2( ),( )2 ,( s v ) 1 ,( s v )2 ,( 2 v )2 ,( 5 v )2 ,( 1 v )2 ,( 4 v 1 v 3 v 2 v 4 v 5 v s v t

25、 v 6 v )5 , 5( )2 , 3( )4 , 4( )4 , 5( )4 , 4( )4 , 5( )3 , 3( ) 1 , 3( )2 , 3( )2 , 2( )2 , 2( ),( )2 ,( s v ) 1 ,( s v )2 ,( 2 v )2 ,( 5 v )2 ,( 1 v )2 ,( 4 v 1 v 3 v 2 v 4 v 5 v s v t v 6 v )5 , 5( )2 , 3( )4 , 4( )4 , 5( )4 , 4( )4 , 5( )3 , 3( ) 1 , 3( )2 , 3( )2 , 2( )2 , 2( ),( ) 1 ,( s v 当标到

26、当标到 时，与时，与 ， 相邻接的点相邻接的点 ， ， 都不满足标都不满足标 号条件，标号无法继续，且没有完成标号。此时最大流量即号条件，标号无法继续，且没有完成标号。此时最大流量即 为所求。为所求。 ) 1 ,( s v s v 3 v 1 v 2 v 6 v t v * 123 54211 sss wfff 3 12456 ,; ,; s t Vv v Vv v v v v v 标号点集 未标号集 1236 1236 ( , )( , ),( ,),( ,) ( , )11 ss ss V Vv vv vv v C V Vccc 割集 割集容量 重新开始标号，寻找可增广链。重新开始标号，寻

27、找可增广链。 第第26页页 网络从发点到收点的各通路中，由容量决网络从发点到收点的各通路中，由容量决 定其通过能力，定其通过能力，最小割最小割则是这此路中的则是这此路中的咽喉部咽喉部 分分，或者叫，或者叫瓶颈瓶颈，其容量最小，它决定了整个，其容量最小，它决定了整个 网络的最大通过能力。要提高整个网络的运输网络的最大通过能力。要提高整个网络的运输 能力，必须首先改造这个咽喉部份的通过能力。能力，必须首先改造这个咽喉部份的通过能力。 最小割的意义最小割的意义 第第27页页 如果我们把图看做输油管道网，如果我们把图看做输油管道网， 为起点，为起点， 为终点，为终点， 为中转站，为中转站，边上的数表示

28、该管道的最边上的数表示该管道的最 大输油能力大输油能力，问应该如何安排各管道输油量，才能，问应该如何安排各管道输油量，才能 使从使从 到到 的的总输油量最大总输油量最大？ t u s u 1234 ,u u u u t u s u 解决问题解决问题 vs v1v3 vt v2v4 8(8) 7(5) 9(4) 9(9) 5(5) 6(1) 2(0) 5(4) 10(8) vs v1v3 vt v2v4 8(8) 7(5) 9(4) 9(9) 5(5) 6(1) 2(0) 5(4) 10(8) ),( (vs,2) (- -v2,2) (v1,1) (- -v3,1) (v4,1) vs v1v

29、3 vt v2v4 8(8) 7(6) 9(5) 9(9) 5(5) 6(0) 2(0) 5(3) 10(9) ),( (vs,1) (- -v2,1) (v1,2) K K W=f *s1+f *s2=8+6=14 324 324 ( , )( , ),( ,) ( , )5 914 t t V Vv vv v C V Vcc 割集 割集容量 第第29页页 下图中，下图中，A,B,C,D,E,FA,B,C,D,E,F分别表示陆地和岛屿，分别表示陆地和岛屿， 表示桥梁及其表示桥梁及其 编号。若河两岸分别为互为敌对的双方部队占领，问至少应切断几座桥梁编号。若河两岸分别为互为敌对的双方部队占领，问

30、至少应切断几座桥梁 （具体指出编号）才能达到阻止对方部队过河的目的。试用图论方法进行分（具体指出编号）才能达到阻止对方部队过河的目的。试用图论方法进行分 析。析。 14 A B C D E F 8 9 11 10 1314 12 7 12 3 4 5 6 最大流问题应用举例最大流问题应用举例 在图中任给可在图中任给可 行流，用标号行流，用标号 法寻找网络最法寻找网络最 大流！大流！ 弧容量：两点间的桥梁数。弧容量：两点间的桥梁数。 A B C D F E 1 2 2 2 1 1 2 2 1 1 2 2 A B C D E F 8 9 11 10 1314 12 7 12 3 4 5 6 转化为

31、求网络最小割转化为求网络最小割 第第31页页 设容量网络设容量网络G G有若干发点，若干个点，有若干发点，若干个点， 可以可以添加两个新点添加两个新点vs s，vt t ，用用容量为容量为 的有向边分别连结的有向边分别连结vs s 与发点，收点与与发点，收点与vt t， 得到新的网络得到新的网络GG，G G 为只有一个发点，为只有一个发点， 一个收点的网络，求解一个收点的网络，求解G G 的最大流问题的最大流问题 即可得到即可得到G G的解。的解。 多发点多收点网络的最大流问题多发点多收点网络的最大流问题 最大流问题应用举例最大流问题应用举例 第第32页页 设有设有5位待业者，位待业者，5项工

32、作，他们各自能胜任工作项工作，他们各自能胜任工作 的情况如图所示，要求设计一个就业方案，使尽的情况如图所示，要求设计一个就业方案，使尽 量多的人能就业量多的人能就业。 1 x 2 x 3 x 4 x 5 x 1 y 2 y 3 y 4 y 5 y 其中其中 51 ,xx 表示工人。表示工人。 51 ,yy 表示工作。表示工作。 最大匹配问题最大匹配问题 1 x 2 x 3 x 4 x 5 x 1 y 2 y 3 y 4 y 5 y 图中最大匹配问题，可以转化为最大流问题求解。在图中最大匹配问题，可以转化为最大流问题求解。在 图中增加两个新点图中增加两个新点 分别作为发点，收点。并用分别作为发点

33、，收点。并用 有向边把它们与原图中顶点相连，令全部边上的容量有向边把它们与原图中顶点相连，令全部边上的容量 均为均为1。当网络流达到最大时，如果。当网络流达到最大时，如果 上的流量为上的流量为1， 就让就让 作作 工作，此即为最大匹配方案。工作，此即为最大匹配方案。 s v t v , s v t v ),( ji yx i x j y 1 x 2 x 3 x 4 x 5 x 1 y 2 y 3 y 4 y 5 y s v t v ),( ) 1 ,( s v )0 , 1 ( )0 , 1 ( )0 , 1 ( )0 , 1 ( )0 , 1 ( )0 , 1 ( )0 , 1 ( ) 1

34、,( 1 x ) 1 ,( 1 y 1 x 2 x 3 x 4 x 5 x 1 y 2 y 3 y 4 y 5 y s v t v ),( )0 , 1 ( )0 , 1 ( )0 , 1 ( )0 , 1 ( ) 1 , 1 ( ) 1 ,( 4 y ) 1 , 1 ( ) 1 , 1 ( 。 ) 1 ,( s v ) 1 ,( 2 x )0 , 1 ( )0 , 1 ( )0 , 1 ( )0 , 1 ( )0 , 1 ( )0 , 1 ( 1 x 2 x 3 x 4 x 5 x 1 y 2 y 3 y 4 y 5 y s v t v )0 , 1 ( )0 , 1 ( )0 , 1 (

35、) 1 , 1 ( ) 1 , 1 ( ) 1 , 1 ( ) 1 , 1 ( ) 1 , 1 ( ) 1 , 1 ( )0 , 1 ( )0 , 1 ( )0 , 1 ( )0 , 1 ( 1 x 2 x 3 x 4 x 5 x 1 y 2 y 3 y 4 y 5 y s v t v ),( )0 , 1 ( )0 , 1 ( )0 , 1 ( ) 1 , 1 ( ) 1 ,( 5 y ) 1 , 1 ( ) 1 , 1 ( ) 1 , 1 ( ) 1 , 1 ( ) 1 , 1 ( ) 1 ,( s v )0 , 1 ( )0 , 1 ( )0 , 1 ( ) 1 ,( 3 x 1 x 2 x 3 x 4 x 5 x 1 y 2 y 3 y 4 y 5 y s v t v ),( )0 , 1 ( )0 , 1 ( ) 1 , 1 ( ) 1 , 1 ( ) 1 , 1 ( ) 1 , 1 ( ) 1 , 1 ( ) 1 , 1 ( )0 , 1 ( ) 1 , 1 ( ) 1 , 1 ( ) 1 , 1 ( )0 , 1 ( )0 , 1 ( )0 , 1 ( 1 x 2 x 3 x 4 x 5 x