资源描述：
《图论第12讲.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、图论GraphicTheory阙夏制作1第六章网络流图问题§1网络流图问题和最大流§2割切§3Ford-Fulkerson最大流最小割切定理§42F最大流最小割切标号算法§5Edmonds-Karp修正算法，Dinic算法2§42F标号算法例用2F标号算法求下图的最大流。例sabct957243863§42F标号算法例解1（1）对所有e∈E，有f(e)=0；解sabct(9,0)(5,0)(7,0)(2,0)(4,0)(3,0)(8,0)(6,0)4§42F标号算法例解2（2）给源点s标号(-,∞)，其
2、它顶点均未标号；解sabct(9,0)(5,0)(7,0)(2,0)(4,0)(3,0)(8,0)(6,0)(-,∞)5§42F标号算法例解3（3）选可进行正向或反向标号的顶点进行标号，若当前标号的顶点为t，转（4），如果没有这样的顶点可选时，转入（6）；解sabct(9,0)(5,0)(7,0)(2,0)(4,0)(3,0)(8,0)(6,0)(-,∞)(s+,2)(b+,4)(a+,7)(c+,5)6§42F标号算法例解4（4）对标号过的增流路径进行增流；增流路径为：(s,a,b,c,t)解sabc
3、t(9,0)(5,0)(7,0)(2,0)(4,0)(3,0)(8,0)(6,0)(-,∞)(s+,2)(b+,4)(a+,7)(c+,5)(2,2)(7,2)(4,2)(5,2)δ=min(cij-fij)=27§42F标号算法例解5（5）转（2）（2）给源点s标号(-,∞)，其它顶点均未标号；解sabct(9,0)(5,2)(7,2)(2,2)(4,2)(3,0)(8,0)(6,0)(-,∞)8§42F标号算法例解6（3）选可进行正向或反向标号的顶点进行标号，若当前标号的顶点为t，转（4），如果没有
4、这样的顶点可选时，转入（6）；解sabct(9,0)(5,2)(7,2)(2,2)(4,2)(3,0)(8,0)(6,0)(-,∞)(s+,9)(a+,8)(b+,6)9§42F标号算法例解7（4）对标号过的增流路径进行增流；增流路径为：(s,b,a,t)解sabct(9,0)(5,2)(7,2)(2,2)(4,2)(3,0)(8,0)(6,0)(-,∞)(s+,9)(a+,8)(b+,6)(8,6)(9,6)(6,6)δ=min(cij-fij)=610§42F标号算法例解8（5）转（2）（2）给源点
5、s标号(-,∞)，其它顶点均未标号；解sabct(9,6)(5,2)(7,2)(2,2)(4,2)(3,0)(8,6)(6,6)(-,∞)11§42F标号算法例解9（3）选可进行正向或反向标号的顶点进行标号，若当前标号的顶点为t，转（4），如果没有这样的顶点可选时，转入（6）；解sabct(9,6)(5,2)(7,2)(2,2)(4,2)(3,0)(8,6)(6,6)(-,∞)(s+,3)(b-,2)(a+,2)12§42F标号算法例解10（4）对标号过的增流路径进行增流；增流路径为：(s,b,a,t)
6、解sabct(9,6)(5,2)(7,2)(2,2)(4,2)(3,0)(8,6)(6,6)(-,∞)(s+,3)(b-,2)(a+,2)δ1=min(cij-fij)=2δ2=fji=2δ=min(δ1,δ2)=2(9,8)(7,0)(8,8)13§42F标号算法例解11（5）转（2）（2）给源点s标号(-,∞)，其它顶点均未标号；解sabct(9,8)(5,2)(7,0)(2,2)(4,2)(3,0)(8,8)(6,6)(-,∞)14§42F标号算法例解12（3）选可进行正向或反向标号的顶点进行标号
7、，若当前标号的顶点为t，转（4），如果没有这样的顶点可选时，转入（6）；解sabct(9,8)(5,2)(7,0)(2,2)(4,2)(3,0)(8,8)(6,6)(-,∞)(s+,1)(b+,2)(c+,3)15§42F标号算法例解13（4）对标号过的增流路径进行增流；增流路径为：(s,b,c,t)解sabct(9,8)(5,2)(7,0)(2,2)(4,2)(3,0)(8,8)(6,6)(-,∞)(s+,1)(b+,2)(c+,3)δ=min(cij-fij)=1(9,9)(4,3)(5,3)16§
8、42F标号算法例解14（5）转（2）（2）给源点s标号(-,∞)，其它顶点均未标号；解sabct(9,9)(5,3)(7,0)(2,2)(4,3)(3,0)(8,8)(6,6)(-,∞)17§42F标号算法例解15（3）选可进行正向或反向标号的顶点进行标号，若当前标号的顶点为t，转（4），如果没有这样的顶点可选时，转入（6）；解sabct(9,9)(5,3)(7,0)(2,2)(4,3)(3,0)(8,8)(6,6)(-,∞)(s+,3)(
