君，已阅读到文档的结尾了呢~~
breass悖论（第一阶段）
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
第三届“ScienceWord杯”数学中国数学建模网络挑战赛b题特等奖论文
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口当前位置： >>
运筹学图论
第五章图与网络分析重点: 重点: 理解图与网络的基本概念 图与网络的基本概念： 理解图与网络的基本概念：掌握 最小树、最短路、最大流问题的解法 问题的解法。 最小树、最短路、最大流问题的解法。 重点掌握DIJKSTRA DIJKSTRA法 FLOYD法 重点掌握DIJKSTRA法、FLOYD法、 最大流的标号法、 最大流的标号法、最
小载集最大流量 定理和最小费用最大流算法。 定理和最小费用最大流算法。图论著名问题七桥问题ACD问题：一个散步者能否走过七座桥， 问题：一个散步者能否走过七座桥，且每座桥只 走过一次，最后回到出发点。 走过一次，最后回到出发点。B中国邮路问题 一个邮递员送信， 一个邮递员送信，要走完他所负责的全部街道 分送信件，最后返回邮局。 分送信件，最后返回邮局。邮递员都会本能地以尽 可能少的行程完成送信任务。问题：他如何走？ 可能少的行程完成送信任务。问题：他如何走？ 路口； 点：路口； 两路口之间道路， 边：两路口之间道路，第 i 条道路长 ei 。 问题转化为： 问题转化为： 求一个圈，过每边至少一次，并使圈的长度最短。 求一个圈，过每边至少一次，并使圈的长度最短。四色猜想 能否用四种颜色给地图染色， 能否用四种颜色给地图染色，使相邻的国家有 不同的颜色。 不同的颜色。 国家； 点：国家； 两个国家有公共边界。 边：两个国家有公共边界。 问题转化为： 问题转化为：能否用四种颜色给平面图的点染 使有公共边的点有不同的颜色。 色，使有公共边的点有不同的颜色。§1图的基本概念有甲、 戊五个球队， 例：有甲、乙、丙、丁、戊五个球队，各队之 间比赛情况如表： 间比赛情况如表： 甲 甲 乙 丙 丁 戊 × 负 胜 负 负 乙 胜 × 负 丙 负 胜 × 负 胜 × 胜 负 × 丁 胜 戊 胜点：球队； 球队； 连线： 连线：两个球队之间比赛过 如甲胜乙， 如甲胜乙，可表示为v5 v1 v3v1v2v4v2研究对象（陆地、路口、国家、球队）； 点：研究对象（陆地、路口、国家、球队）； 点间连线： 点间连线：对象之间的特定关系 对称关系：用不带箭头的连线表示，称为边。 对称关系：用不带箭头的连线表示，称为边。 双行道路、边界； 桥、双行道路、边界； 非对称关系：用带箭头的连线表示，称为弧。 非对称关系：用带箭头的连线表示，称为弧。 甲队胜乙队、 甲队胜乙队、有方向的道路 点及边（或弧）组成。 图：点及边（或弧）组成。1.1图的定义 图的定义定义1 一个图， 定义1：一个图，是由非空集合 V( G ) = { vi } 和 V(G) 元素的有序对（或无序对） 中 元素的有序对（或无序对）的集合 E( G ) = { ek } 所组成的二元组（ 所构成。 所组成的二元组（ V(G)， E(G) ）所构成。记为 ， G = （ V(G)， E(G) ） ， 简记 其中 G =（V，E） （ ， ） V = { vi } 称为点集，vi 为点 。 称为点集， 称为边集， 为边（或弧）。 E = { ek } 称为边集， ek为边（或弧）。为有限图。 当 V，E 为有限集时，称 G 为有限图。否则称为 ， 为有限集时， 无限图。 无限图。 无向图： 无向图：由点及边构成 ，边 [ vi，vj ]有向图：由点及弧构成， 有向图：由点及弧构成，弧（ vi，vj ） 的顶点个数， 图 G 中点集 V 的顶点个数，记为 P (G) ，边数 记为 q(G)，简记 P，q 。 ， ，1.2图论中常用术语 图论中常用术语1.相邻与关联 相邻与关联 的端点， 若边 e = [u，v]∈E，称 u，v 是 e 的端点，也称 u， ， ∈ ， ， ， v 是相邻的。称 e 是点 u（及点 v）的关联边。 是相邻的。 （ ）的关联边。 若两条边有一个公共的端点，则称这两条边相邻。 若两条边有一个公共的端点，则称这两条边相邻。vie vi，vj 相邻vjvie1 vk e2 e1 与 e2 相邻vje 与 vi，vj 关联点?点，相邻点?边关联边?边，相邻2.简单图与多重图 简单图与多重图 某条边两个端点相同，称这条边为环 某条边两个端点相同，称这条边为环。 若两点之间有多于一条的边，称这些边为多重边。 若两点之间有多于一条的边，称这些边为多重边。 多重边v1 e1 v2 e2 e3v4 e4 e5v3简单图：无环、无多重边的图。 简单图：无环、无多重边的图。 多重图：无环、但允许有多重边。 多重图：无环、但允许有多重边。3.次与悬挂点、孤立点 次与悬挂点、 次与悬挂点 为端点的边的数目， 图 G 中以点 v 为端点的边的数目，称为 v 在 G 中 的次， 的次， 记为 d( v ) 。v1 e1 v2 e2 e3 v3v4 e4的点为悬 次为 1 的点为悬 d( v1) = 2， ， 挂点， 挂点，悬挂点的 d( v2 ) = 3， ， 关联边称为悬挂 关联边称为悬挂 d( v3 ) = 4，边，次为 0 的点 ， 称为孤立点。 孤立点 e5 d( v4 ) = 1 称为孤立点。定理1 定理1 图 G =（V，E）中，所有点的次之和为边数 （ ， ） 的两倍， 的两倍， 即∑d (v ) = 2qv ∈V4.奇点与偶点 奇点与偶点 次为奇数的点称为奇点，否则称为偶点。 次为奇数的点称为奇点，否则称为偶点。 定理2 定理 任一图中奇点的个数为偶数。 任一图中奇点的个数为偶数。5.链与圈 链与圈 给定一个图 G =（V，E）， 中的一个点、边交 ），G （ ， ）， 中的一个点 错序列（ ），如果 错序列（vi1，ei1，vi2，ei2，…，vik-1，eik-1，vik），如果 ， 满足 eit = [ vit，vit+1 ]（ t = 1，2，…，k-1）， （ ， ， ， ）， 则称为一条联接 vi1 和 vik 的链，记为 ? =（vi1，vi2，…，vik）。 （ ，链（vi1，vi2，…，vik）中，若 vi1 = vik ，称之为一 ， 个圈，记为 C = （vi1，vi2，…，vik-1， vi1 ） 。 ， （ 初等链：链中点都不同。 边能否相同？） 初等链：链中点都不同。 边能否相同？） 简单链：链中边都不同。 简单链：链中边都不同。v1 e1 v3 e2 e5 v5 v7 e7 v6 v8 有向图中，不考虑 有向图中， 弧的方向， 弧的方向，有类似 的定义。 链（圈）的定义。 当链（ 当链（圈）上弧的 方向一致时， 方向一致时，称为 路（回路）。 回路）。e3 v2 e8e4 v4e6 e9找出简单链、初等链、简单圈、 找出简单链、初等链、简单圈、初等圈6.子图与支撑子图 子图与支撑子图 定义2 ），若图 ′ （ ′ 定义 给定图 G =（V，E），若图 G′ =（V′，E′）， （ ， ）， ′ 其中 V′? V，E′ ={uv|uv∈E，u，v ∈V ′}，则称 G′ 是 ′? ， ′ ∈ ， ， ， ′ G 的子图。 的子图。 定义3 ），若图 ′ （ ， ′ 定义 给定图 G =（V，E），若图 G′ =（V，E′）， （ ， ）， 其中 E′ ? E，则称 G′ 是 G 的一个支撑子图。 支撑子图 的一个支撑子图。 ′ ， ′子图 （a） （b）（c）7.割集 . ），点的子集 ∈ ， 给定图 G= （V，E），点的子集 S∈V，T ∈V，定 ， ）， ， 义 G 中边的集合 [ S,T ]G = { uv | u ∈ s，v ∈ t }为一个 ， 为一个 割集。 割集。 若 X ∈V是 V 的真子集，即 X ∪ X = V , X ∩ X = Φ, 是 的真子集，[ X , X ] G 常记为 Φ（X）。 ）。v1 v2v4， ） ？ v3 若 X = { v1 }， Φ（X）=？ 若X={v1，v2}， Φ（X）=？ ， ） ？v6v58.网络 . 若对图 G =（V，E）中每条边 [ vi，vj ] 赋予一个 （ ， ） 的权， 数 wij，则称 wij 为边 [ vi，vj ] 的权，并称图 G 为网络 （或赋权图）。 或赋权图）。 网络：无向网络、有向网络。 网络：无向网络、有向网络。 9.连通图 . 中任意两点都有链相连， 为连通图。 图G中任意两点都有链相连，则图 为连通图。 中任意两点都有链相连 则图G为连通图 任一不连通图可分为多个连通分图。 任一不连通图可分为多个连通分图。1.3图的矩阵表示 图的矩阵表示图的矩阵表示方法有：权矩阵、邻接矩阵、 图的矩阵表示方法有：权矩阵、邻接矩阵、关联 矩阵、回路矩阵、割集矩阵等。 矩阵、回路矩阵、割集矩阵等。1.权矩阵 ），边 网络 G =（V, E），边 [ vi , vj ] 的权为 wij ，构造 （ ）， 矩阵A = (a ij ) n×n , 其中 ?wij a ij = ? ?0 [v i , v j ] ∈ E 其它的权矩阵。 称矩阵 A 为网络 G 的权矩阵。 例：7 v1 9 4 2 4 v2 v5 5 6 v4 v3 8其权矩阵为： 其权矩阵为：3?0 ?9 ? A = ?2 ? ?4 ?7 ?9 0 3 4 02 3 0 8 54 4 8 0 67? 0? ? 5? ? 6? 0? ?2.邻接矩阵 . ），P 图 G =（V，E）， = n，构造矩阵 （ ， ）， ，A = (a ij ) n×n , 其中 ?1 a ij = ? ?0例：v1[v i , v j ] ∈ E 其它的邻接矩阵。 称矩阵 A 为 G 的邻接矩阵。v5当 G 为无向图 邻接矩阵为 时，邻接矩阵为 对称矩阵 矩阵。 对称矩阵。其邻接矩阵为： 其邻接矩阵为：v4 v3v2?0 ?0 ? A = ?1 ? ?0 ?0 ?1 0 0 0 00 1 0 1 01 1 0 0 11? 0? ? 1? ? 0? 0? ?1.4图的同构 图的同构定义4 设图G=（V，E）与G’=（V’，E’），若它们 定义4 设图 （ ， ） （ ， ），若它们 ）， 的点之间存在一一对应，并且保持同样的相邻关系， 的点之间存在一一对应，并且保持同样的相邻关系， 则称G与 同构 记为G≌ 。 同构。 则称 与G’同构。记为 ≌G’。v1v2?abv1 v2 v3a b d cv3v4cdv4§22.1树及其性质 树及其性质定义1： 定义 ：最小树问题无圈的连通图称为树。 表示。 无圈的连通图称为树。树一般用 T 表示。 定理1： 定理 ： 任给树 T = (V，E)，若P(T)≥2，则 T 中至少 ， ， ， 有两个悬挂点。 有两个悬挂点。 证明： 证明：设 ?=（v1，v2，…，vk）是 G 中含边数最多的 （ ， 一条初等链， 是连通的， 一条初等链，因 P(T)≥ 2，并且 T 是连通的，故链 ? 中 ， 至少有一条边， 至少有一条边，从而 v1 与 vk 是不同的 。是悬挂点， 现证 v1 是悬挂点，即 d(v1) = 1。 。 反证法： 反证法：如 d(v1)≥ 2，则存在边 [v1，vm]，使 m≠2。 ， ， 。 假设v 不在?上 假设 m不在 上，v1 vm v2 vk那么（ 链边数多一条， 那么（vm，v1，v2，…，vk）比 ? 链边数多一条， ， 与 ? 是边数最多的链矛盾。 是边数最多的链矛盾。 若 vm 在 ? 上,v1 v2 vm vk是圈， 是树矛盾。 （v1，v2，…， vm， v1）是圈，与 T 是树矛盾。 ， 是悬挂点。 所以必有 d(v1) = 1，即 v1 是悬挂点。 ， 同理可证： 也是悬挂点。 至少有两个悬挂点。 同理可证：vk 也是悬挂点。所以 T 至少有两个悬挂点。定理2 定理图 T=(V，E)， p = n， q = m，则下列关于 ， ， ， ，边数=点数 边数 点数-1 点数树的说法是等价的。 树的说法是等价的。是一个树。 （1）T是一个树。 ） 是一个树 无圈， （2）T无圈，且 m = n-1。 ） 无圈 。 连通， （3）T连通，且 m = n-1。 ） 连通 。 （4）T无圈，但每加一条新边即得唯一一个圈。 无圈， ） 无圈 但每加一条新边即得唯一一个圈。 连通， （5）T连通，但每丢掉一条边就不连通。 ） 连通 但每丢掉一条边就不连通。 中任意两点， （6）T中任意两点，有唯一链相连。 ） 中任意两点 有唯一链相连。 证明：（ ） （ ） 证明：（1）→（2） ：（ 是树， 连通且无圈。 由于 T 是树，由定义知 T 连通且无圈。只须证 明 m = n-1。 。归纳法： 是树， 归纳法：当 n = 2 时，由于 T 是树，所以两点间显然 有且仅有一条边， 有且仅有一条边，满足 m = n-1。 。 时命题成立， 个顶点时， 假设 n = k-1 时命题成立，即有 k-1 个顶点时，T 条边。 有 k-2 条边。 连通无圈， 当 n= k 时，因为 T 连通无圈，k 个顶点中至少有 为悬挂点。 一个点次为 1。设此点为 u，即 u 为悬挂点。 。 ， 设连接点 u 的悬挂边为 [v，u]，从 T 中去掉 [v，u] ， ， ， 的连通性， 边及点 u ，不会影响 T 的连通性，得图 T?，T?为有 k? ? 1 个顶点的树，所以 T?有 k-2 条边，再把 [ v，u]、点 个顶点的树， 条边， ? ， 、 u 加上去，可知当 T 有 k 个顶点时有 k-1 条边。 加上去，是连通图。 （2）→（3） 只须证 T 是连通图。 ） （ ） 反证法: 反证法 不连通， 个连通分图（ 设 T不连通，可以分为 l 个连通分图（l ≥ 2）， 不连通 ）， 个顶点， 设第 i 个分图有 ni 个顶点，则∑ ni = ni= 1l个分图是树， 条边， 因为第 i 个分图是树，所以有 ni-1 条边，l 个分 图共有边数为： 图共有边数为：∑ (ni =1li? 1) = n ? l & n ? 1与已知矛盾。 为连通图。 与已知矛盾。所以 T 为连通图。2.2图的支撑树 图的支撑树定义2 定义 设图 T = [V，E′] 是图 G=（V，E）的支撑子 ， ′ （ ， ） 是一个树， 的一个支撑树。 图，如果 T 是一个树，则称 T 是 G 的一个支撑树。v3 v5 v3 v5v1v6v1v6 v2 v4 （b） ）v2v4 （a） ）（b）是（a）的一个支撑树。 ） ）的一个支撑树。定理3 定理3 有支撑树的充分必要条件是图G是连通的 是连通的。 图 G 有支撑树的充分必要条件是图 是连通的。 证明：必要性是显然的。 证明：必要性是显然的。 充分性： 是连通的， 不含圈， 充分性： 设 G 是连通的，如果 G 不含圈，则G本身 本身 一个树，从而是它自身的一个支撑树。 是 一个树，从而是它自身的一个支撑树。 现设 G 含圈，从圈中任意去掉一条边，得 G 的一 含圈，从圈中任意去掉一条边， 个支撑子图 G1，如 G1 不含圈，则 G1 是 G 的一个支 不含圈， 撑树； 撑树； 含圈， 中任取一圈， 如 G1 含圈，则从 G1 中任取一圈，从圈中再任意 去掉一条边， 如此重复， 去掉一条边，得 G 的一个支撑子图 G2，如此重复， 终可得 G 的一个不含圈的支撑子图 Gk，于是 Gk 是G 的一个支撑树。 的一个支撑树。求图的支撑树的方法（一）破圈法（二）避圈法 在图中任取一条边 e1，找一条与 e1 不构成圈的边 e2，再找一条与 { e1，e2 } 不构成圈的边 e3。一般设已 ， ， ， 有 { e1，e2，…，ek }，找一条与 { e1，e2，…，ek } 中 重复这个过程， 任何一些边不构成圈的边 ek+1，重复这个过程，直到 不能进行为止。 不能进行为止。 v v5 3v1v6v2v42.3最小支撑树问题 最小支撑树问题 最小支撑树定义3 设有连通图 G = (V,E)，G 的任一边 ek = [vi,vj ] 定义 ， 有一个非负权 w( ek ) = wij（wij≥ 0）,T= (V,E′) 是G 的 ） ′ 一个支撑树， 一个支撑树，称w (T ) =的权。 为树 T 的权。[ v i , v j ]∈ T∑wij如果支撑树 T* 的权 w(T*)是 G 的所有支撑树的权 是 中最小的， 的最小支撑树（ 中最小的，则称 T* 是 G 的最小支撑树（简称最小 树）。即 ）。即w(T *) = min w(T )T最小支撑树问题， 最小树。 最小支撑树问题，即求网络 G 的最小树。求最小支撑树的算法避圈法（ （一）避圈法（Kruskal） ） 思想：在图中取一条最小权的边，以后每一步中， 思想：在图中取一条最小权的边，以后每一步中， 总从未被选取的边中选一条权最小的边， 总从未被选取的边中选一条权最小的边，并使之与已 选取的边不构成圈（每一步中， 选取的边不构成圈（每一步中，如果有两条或两条以 上的边都是最小权的边，则从中任选一条）。 上的边都是最小权的边，则从中任选一条）。 Kruskal算法步骤： 算法步骤： 算法步骤 的边按权由小到大排好， 第 1 步：把 G = ( V，E ) 的边按权由小到大排好， ， 即要求 w (e1) ≤ w (e2 ) ≤ …≤ w (em)图 G，p = n ，q = m， ， ， 令i=1 ，j=0 ， E0= Φ，检查过的边数 取的边数最小树的边集第 2 步：如果（V，Ei-1∪ e i）含圈，Ei = Ei-1，转 如果（ ， 含圈， 第 3 步，否则转第 4 步；不要这条边第 3 步：i 换成 i+1，如果 i ≤ m，转第 2 步，否则 ， ， 结束， 没有最小树； 结束，G 没有最小树；取定这条边第 4 步：令 Ei = Ei-1 ∪ e i，j 换成 j+1，若 j = n-1， ， ， 结束，（ ， 是所求最小树，否则转第3步 结束，（V，Ei）是所求最小树，否则转第 步。 ，（某工厂内联结六个车间的道路如图示。 例： 某工厂内联结六个车间的道路如图示。已知每 条道路的长， 条道路的长，要求沿道路架设联结六个车间的电话线 使电话线的总长最小。 网，使电话线的总长最小。v36 75v54v1513 4v6v22v4将各边按权从小到大排为： 解：将各边按权从小到大排为： w23 ≤ w24 ≤ w45 ≤ w 56 ≤ w 46 ≤ w12 ≤ w35 ≤ w13 ≤ w25 i =1 ，j = 0 ，E0 = Φ ，n = 6 ，m = 9 无圈， （V， E0 ∪ e23）无圈， ， E1=E0 ∪ e23 ={ e23 }， ， j=1 &n-1 i = 2,（V, E1 ∪ e24）无圈，v1 无圈， （ E2 = E1 ∪ e24 = {e 23, e24 }， ， j = 2 &n-15 6 1 7 3 4v35v54v6v22v42.3 最小支撑树问题 最小支撑树问题i = 3,（V， E2 ∪ e45）无圈， 无圈， （ ， E3 = E2 ∪ e45 = {e23, e24 , e45}， ， j = 3 & n-1 i = 4,（V， E3 ∪ e56）无圈， 无圈， （ ， E4 = E3 ∪ e56 ={ e23, e24 , e45 , e56 }， ， j = 4 &n-1,6 1Kruskal算法 算法v375v54 3 4v1v6i = 5,（V， E4 ∪ e46）含圈，5 含圈， （ ， E5 = E4,v22v42.3 最小支撑树问题 最小支撑树问题结束。 e45 , e56 , e12}， j = 5 = n-1,结束。 ， 结束 是所求的最小树。 （V，E6）是所求的最小树。 ， 电话线总长最小方 案如图， 单位。 案如图，总长 15 单位。Kruskal算法 算法i = 6,（V， E5 ∪ e12）无圈，E6 = E5 ∪ e12 = {e23, e24 , 无圈， （ ，v365v54 3 4v1517v6v22v4Dijkstra算法 （避圈法） 算法 避圈法） 定理4 定理 T 是网络 G = (V,E,W) 的最小树的充要条件是， 的最小树的充要条件是，对于任意边 e ∈E，e 惟一决定一个 G 中边的割集 ， 的其它边都不属于T， ?(e)，除了边 e 外， ?(e) 的其它边都不属于 ，且 e ， 中的最小权边。 是 ? (e)中的最小权边。 中的最小权边 思想： 个独立割集中（ 思想：在 n-1 个独立割集中（这 n-1 个独立割集由网 络中不同的点集所确定）， ），取每个割集的一条最小权 络中不同的点集所确定），取每个割集的一条最小权 构成一个支撑树，由定理4， 棵最小树。 边，构成一个支撑树，由定理 ，它是一 棵最小树。 Dijkstra算法步骤： 算法步骤： 算法步骤 第 1 步： X 0 = {v1 }, X 0 = V \ X 0 , E 0 = Φ , i = 0,2.3 最小支撑树问题 最小支撑树问题第 2 步：在 Xi 所确定的割集 Φ ( Xi )中选一条最小权 中选一条最小权 边 ek，ek = [ v?,vk ]， ? ， v?∈ xi ， ?v k ∈ Xi, 令 E i +1 = E i ∪ e k , X i +1 = X i ∪ {v k }, X i +1 = X i \ {v k },。（V， 第 3 步：若 Xi+1 = V，结束。（ ，Ei+1）是所求的最 ，结束。（ 小树。否则， 小树。否则，把 i 换成 i+1，返回第 2 步。 ，例：用dijkstra算法求解本例 算法求解本例X 0 = {v1 }, X 0 = {v 2 , v 3 , v 4 , v 5 , v 6 }i = 0, 在 Φ = (X 0 )中选边 e 12 , E 1 = E 0 ∪ e 12 = {e 12 } X 1 = X 0 ∪ {v 2 } = {v 1 , v 2 }, X 1 = {v 3 , v 4 , v 5 , v 6 }i = 1, 在Φ = (X1 )中选边 e 23 , E 2 = E 1 ∪ e 23 = {e12 , e 23 } X 2 = X 1 ∪ {v 3 } = {v 1 , v 2 , v 3 }, X 2 = {v 4 , v 5 , v 6 }v365v54 3 4v1517v6v22v4i = 2, 在 Φ = (X 2 )中选边 e 24 , E 3 = E 2 ∪ e 24 = {e 12 , e 23 , e 24 }, X 3 = X 2 ∪ {v 4 } = {v 1 , v 2 , v 3 , v 4 }, X 3 = {v 5 , v 6 },i = 3, 在 Φ = (X 3 )中选边 e 45 , E 4 = E 3 ∪ e 45 = {e12 , e 23 , e 24 , e 45 }, = {v1 , v 2 , v 3 , v 4 , v 5 },v365v54 3 4X 4 = X 3 ∪ {v 5 } X 4 = {v 6 },v1517v6v22v4i = 4, 在 Φ = (X 4 )中选边 e56 ,X 5 = X 4 ∪ {v 6 } = {v1 , v 2 , v3 , v 4 , v 5 , v 6 } = V ,是所求最小树。 （V，E5）是所求最小树。 ，E 5 = E 4 ∪ e 56 = {e12 , e23 , e24 , e 45 , e 56 },v365v54 3 4v1517v6v22v4v365v54v15173 4v6v22v4（二）破圈法 任取一个圈，从圈中去掉一条权最大的边（ 任取一个圈，从圈中去掉一条权最大的边（如果 有两条或两条以上的边都是权最大的边， 有两条或两条以上的边都是权最大的边，则任意去掉 其中一条）。在余下的图中，重复这个步骤， 其中一条）。在余下的图中，重复这个步骤，直到得 ）。在余下的图中 到一个不含圈的图为止，这时的图便是最小树。 到一个不含圈的图为止，这时的图便是最小树。v3 6 v1 5 v2 2 v4 1 7 3 4 5 v5 4 v6§3 最短路问题3.1最短路问题 最短路问题下图为单行线交通网， 例 下图为单行线交通网，每弧旁的数字表示通 出发， 过这条线所需的费用。 过这条线所需的费用。现在某人要从 v1 出发，通过 求使总费用最小的旅行路线。 这个交通网到 v8 去，求使总费用最小的旅行路线。v26 2 3 11v56 10 3 102 6v93 4从 v1 到 v8 的 旅行路线 ? 旅行路线总费 用?v1v324v8v4v62最短路问题中， 最短路问题中， v7不考虑有向环、并行弧。 不考虑有向环、并行弧。定义），任意弧 给定有向网络 D =（V,A,W），任意弧 aij ∈A， （ ）， ， 有权 w( aij )= wij，给定 D 中的两个顶点 vs，vt 。设 P 的一条路， 的权（长度） 是 D 中从 vs 到 vt 的一条路，定义路 P 的权（长度）是 P 中所有弧的权之和，记为 w( P )。最短路问题就是 中所有弧的权之和， 。最短路问题就是 的路中， 要在所有从 vs 到 vt 的路中，求一条路 P0 ，使w(P 0 ) = min w(P)P的最短路。 称 P0 是从 vs 到 vt 的最短路。路 P0 的权称为从 vs 路长， 到 vt 的路长，记为 Ust。3.2 Dijkstra算法（wij ≥ 0） 算法（ 算法 ）当所有w 本算法是用来求给定点s到 当所有 ij≥0 时，本算法是用来求给定点 到 任一个点i最短路的公认的最好方法 最短路的公认的最好方法。 任一个点 最短路的公认的最好方法。思想： 思想： 最短路的子路也是最短路。 最短路的子路也是最短路。 如下图，如果R→C→O→W为从 到W的一最 如下图，如果 为从R到 的一最 为从 短路P， 为从R沿 到 的最短路 的最短路。 短路 ，则R→C→O为从 沿P到O的最短路。 为从T R C O W算法进行时，对每一个节点进行标号， 算法进行时，对每一个节点进行标号，标号种类 分为临时标号（ 标号 和永久标号（ 标号 标号） 标号） 分为临时标号（T标号）和永久标号（P标号）。 节点i的临时标号记为 节点 的临时标号记为T(i)，它表示从发点 到节点 的临时标号记为 ，它表示从发点s到节点 i的最短距离的上界；节点 的永久标号记为 的永久标号记为P(i)， 的最短距离的上界；节点i的永久标号记为 ， 它表示从发点s到节点 的实际最短距离。 到节点i的实际最短距离 它表示从发点 到节点 的实际最短距离。 算法的每一步要把节点的T类标号改为 类标号。 算法的每一步要把节点的 类标号改为P类标号 类标号改为 类标号。 当收点i获得 类标号时， 就得到从发点s到收点 获得P类标号时 到收点i 当收点 获得 类标号时 ， 就得到从发点 到收点 的最短路线。 的最短路线。T标号 标号前点标号， 前点标号，表示 v1 到 v4 的最短路上 v4 的前一点是 v1 。v261,6 3,51v51, ∞ 2, 6 2 6v931, ∞2 3v10,0 1 P标 标 号v321,3 6 103 4 10 4 2v8 v75, 12 1, ∞v41,1v65,10 1, ∞ 4,111, ∞ 5, 9 表示 v1 到 v4 的最短路路 长步骤： 步骤：第 1 步：令 u0 = 0，uj = wsj （1≤ j≤ n ） ， ≤ ≤ 若 asj ?A，则令 wsj = +∞ , ， ∞ X0 = { vs } ，X0 =V \ X0， K = 0, λ j = s ( 0 ≤ j ≤ n ) 第 2 步：( 选永久标号 ) 在 Xk 中选一点 vi ，满足 u i = min { u j }v j ∈X k如果u ∞ 停止， 中各点没有路； 如果 i =+∞，停止，从vs到Xk中各点没有路； 否则， 否则，转第 3 步。， 第 3 步： 令 Xk +1 = Xk ∪ { vi }， X k +1 = X k \ {v i } 结束， 如果 Xk+1 Φ，结束，vs 到所有点的最短路已经 = 求得；否则， 求得；否则，转第 4 步。 ：（修改临时标号 修改临时标号） 第 4 步：（修改临时标号） 对所有 v j ∈ X k +1 , 如果 ui+ wij & uj ， 否则， 不变； 令λ j = i，uj = ui + wij，否则， λ j，uj不变；把 k ， 换成k+1，返回第 2 步。 ， 换成的最短路。 例 用Dijkstra算法求前面例子中从 v1 到 v8 的最短路。 算法求前面例子中从 解：u1= 0, u2= 6, u3=3, u4=1, u5=u6=u7=u8=u9=+∞ ∞ λ j =1 （j =2，3，…，9） ， ， ， ） X0 = {v1}， X0= {v2，v3，…，v9} ， ， K=0 ∵ min {u2, u3, u4, u5, u6, u7, u8, u9}6 = min {6, 3, 1, ∞, ∞, ∞, ∞, ∞} 2 v2 1 v5 2 6 6 4 10 3 v8 v9 3= 1= u4v13 v 32 得永久标号， 1 ∴ 点 v4 得永久标号， λ4 =1 ，X1={v1,v4}， v 4 ， 7 10 v ， 2 X1 ={v2,v3, v5,v6 ,v7,v8 ,v49}， v6在所有v 在所有 j∈X1中， 修改临时标号 u6= 11 ，λ 6 = 4，其余标号不变。 ，其余标号不变。 K=1 ∵ min{u2, u3, u5, u6, u7 ,u8, u9} = min{6, 3, ∞, 11, ∞, ∞, ∞}= 3= u3 得永久标号， ∴ 点v3得永久标号，λ3=1，X2={v1,v4 ,v3}， ， ， X2 ={v2, v5, v6, v7, v8, v9} 在所有 vj∈X2 中， 修改临时标号 u2= 5 ， λ2=3，其余标号不变。 ，其余标号不变。v1 1 v4 6 2 3 v 3 2 10 v6 2 6 4 10 4 v7 3 v8 v2 1 v5 2 6 v9 3K= 2 ∵ min {u2, u5, u6, u7, u8, u9} = min {5, ∞, 11, ∞, ∞, ∞}= 5= u2 得永久标号， ∴ 点 v2 得永久标号， λ2 = 3 ， X3={v1, v4, v3, v2}， X3 ={v5, v6, v7, v8, v9} ， 在所有 vj∈ X3 中， 其余标号不变。 修改临时标号 u5= 6 ，λ5 = 2 ，其余标号不变。v2 1 v5 2 v9 6 6 4 10 v6 10 4 2 v7 3 v8 3 6 2 v1 1 v4 3 v 3 2K=3 ∵ min{u5, u6, u7, u8, u9} = min{6, 11, ∞, ∞, ∞}= 6= u5 得永久标号， ∴ 点 v5 得永久标号， λ5 = 2 ， X3={v1, v4 , v3, v2, v5}， X3={v6, v7, v8, v9}， ， ， 在所有 vj∈ X4 中，修改临时标号 u6= 10, λ6=5 ; u7=9, λ7=5 ; u8= 12, λ8=5v1 1 v4 6 2 3 v 3 2 10 v6 2 6 4 10 4 v7 3 v8 v2 1 v5 2 6 v9 3K=4 ∵ min{u6, u7, u8, u9} = min{10, 9, 12, ∞} =9= u7 得永久标号， ∴ 点 v7 得永久标号， λ7 = 5 ， X4={v1, v4, v3, v2, v5,v7}， X4={v6, v8, v9}， ， ， 临时标号不变。 在 vj∈X4中，临时标号不变。v2 6 2 v1 1 v4 3 v 3 2 10 v6 2 6 4 10 4 v7 3 v8 1 v5 2 6 v9 3K=5 ∵ min{u6, u8, u9}= min{10, 12, ∞} =10=u6 得永久标号， ∴ 点 v6 得永久标号， λ6= 5 ， X5={v1, v4, v3, v2, v5, v7, v6}， X5={v8, v9}， ， ， 临时标号不变。 点 v8，v9 临时标号不变。 K=6 ∵ min{u8, u9}= min{12, ∞} =12 = u8 ∴ 点 v8 得永久标号， 得永久标号， λ8 = 5 ， 即从 v1 到 v8 的最短 ， 路长为 u8 = 12， 的最短路为： 从v1到v8的最短路为： P1,8 =P(v1,v3,v2,v5, v8）6 v1 v2?2 21?6 4 10 v6 10 2v52 6 3 4 v7v9 3? ?1 v43 v 3?v8问题： 本例中， 的最短路？ 问题：①本例中，v1到v9的最短路？ ②无向网络 wij vi ③负权弧时。 负权弧时。 1 v1 2 v3 多个点对之间最短路？ ④多个点对之间最短路？ -3 wij vj vi wij vj无向网络中，最短路 最短链 最短链。 无向网络中，最短路→最短链。v2Dijkstra算法失效 算法失效3.3 Floyd算法 算法(n) 网络D=（ ），令 网络 （V, A, W），令U = (uij)n×n， u ij 表示 D ）， ×的最短路的长度。 中 vi 到 vj 的最短路的长度。 考虑 D 中任意两点 vi，vj ，如将 D 中 vi，vj 以外 的点都删掉，得只剩 vi，vj 的一个子网络 D0，记 的点都删掉，u(0) ij? w ij =? ?∞当(v i , v j )∈ A 否则wij 为弧 vi，vj ) 的权。 为弧( 的权。相关联的弧， 在 D0 中加入 v1 及 D 中与 vi，vj，v1 相关联的弧，(1) 得 D1，D1 中 vi 到 vj 的最短路长记为 u ij ，则一定有u(1) ij= min u{(0) ij,u(0) i1+u(0) 1j}vjviui1(0)uij(0)u1j(0)v1 再在D 再在 1中加入 v2 及 D 中与 vi，vj，v1，v2 相关联(2) 的弧， 的弧，得 D2，D2 中 vi 到 vj 的最短路长记为 u ij ，则一定有v2ui2(1) u2j(1) uij(0) ui1(0)vivju1j(0)v1(2) (1) (1) u ij = min u ij , u i2 + u (1) 2j{}递推， 个点逐个加入子网络， 递推，D 中 n 个点逐个加入子网络，终得 D 中 vi 到 vj 的最短路路长(n) u ij = u ij如果计算结果希望给出具体的最短路的路径， 如果计算结果希望给出具体的最短路的路径，则 构造路径矩阵 S = ( sij ) n × n , sij 表示 vi 到 vj 的最短路的 第一条弧的终点。 第一条弧的终点。如s(n) ij= tvi从 vi 到 vj 的最短路 的第一条弧为 ( vi，vt ) vj s(n) tj= mD中vi到vj的最 中 短路vtvm从 vt 到 vj 的最短 路的第一条弧算法步骤： 算法步骤：(0) 第 1 步： U = U (0) S (0) = (s ij ) n × n , (0) 其中 s ij = j (i = 1,2,..., j = 1,2,..., n)(k) 第 2 步： 计算 U (k) = ( u ij ) (k) S (k) = ( s ij ) n×n n×n(k = 1,2,3,..., n) (k = 1,2,3,..., n)(k) (k (k 其中 u ij = min u ij -1) , u ik -1) + u (k -1) kj (k ? s ij -1) ? = ? (k -1) ? s ik ?{}(n) S (n) = (s ij ) n × n(k) s ij(k) (k 当 u ij ≤ u ik -1) + u (k -1) kj (k) (k u ij & u ik -1) + u (k -1) kj(n) 当 k = n 时， U (n) = (u ij ) n×n 第 3 步：的最短路路长； 其中，元素 uij(n) 就是 vi 到 vj 的最短路路长；元素 sij(n) 其中， 的最短路的第一条弧的终点。 就是 vi 到 vj 的最短路的第一条弧的终点。求如下网络中各点对间最短路的路长。 例 求如下网络中各点对间最短路的路长。v1454 -2 -3v2 解 ： v52 6v3 8 的第一行、 （1）用U(0)的第一行、第 ） 一列来修正其余的u 一列来修正其余的 ij ，即 S (0) = 作(1) (0) (0) (0) u ij = min u ij , u i1 + u 1jv4?0 5 ∞ ?∞ 0 6 ? U(0) = ? ∞ ∞ 0 ? ?4 ∞ 8 ?4 ∞ ∞ ??1 ?1 ? ?1 ? ?1 ?1 ? 2 2 2 2 2 3 3 3 3 3∞ ∞? ? ∞ ? 3? ∞ 2? ? 0 ∞? ?2 0 ? ?4 4 4 4 4 5? 5? ? 5? ? 5? 5? ?{}0 5 ∝ ∝ ∝ U(1) = ∝ 0 4 9 6 ∝ -3 2 ∝S(1)∝ ∝ 0 ∝ 8 04 9 ∝ -2 0同时， 同时，在修正 u 处修改 s(1) ij (1) ij?1 ?1 ? = ?1 ? ?1 ?1 ?(0) i12 3 4 5? ? 2 3 4 5? 2 3 4 5? ? 1 3 4 5? 1 3 4 5? ?=ss (1) = s (0) = 1 42 41的第二行、 （2）用 U(1) 的第二行、第二列修正其余的 uij， ）0 5 ∝ ∝ ∝ U(1) = ∝ 0 4 9 6 ∝ -3 2 ∝ 0 5 11 ∝ U(2) = ∝ 0 4 9 ∝ ∝ 0 ∝ 8 0 2 2 6 6 ∝ -3 8 0 ∝ ∝ 0 ∝4 9 ∝ -2 04 9 15 -2 0S(2)?1 ?1 ? = ?1 ? ?1 ?1 ?2 2 2 1 12 3 3 34 4 4 4? 1 2(1) (2) 1 4 s? = s 42 45 1 2 ? S (1) = ? 1 2 ? ?1 1 (2) (1) s 53 = s 52 = 1 ? 1 1 ?2? ? 5? 5? ? 1? 5? ?s S s == 2 = 2 = S(2) 13 (2)(1) 15 12 (1) 123 4 =1 3 4 3 3 3 4 4 45? 5? ? 5? ? 5? 5? ?的第三行、 （3）用 U(2) 的第三行、第三列修正其余的 uij， ）?0 ?∞ ? (2) U =?∞ ? ?4 ?4 ?5 0 ∞ 9 911 ∞ 6 0 8 ∞ ∞ 015 ? 22? ? ?3? 2? ? 6? 0? ?U (3) = U (2)S(3)=S(2)的第四行、 （4）用 U(3) 的第四行、第四列修正其余的 uij ）?0 ?∞ ? U(3) = ? ∞ ? ?4 ?4 ?5 0 ∞ 9 9∞ 2? ? 6 ∞ ? 3? 0 ∞ 2? ? 8 0 6? 15 ? 2 0 ? ? 11?0 ?∞ ? U(4) = ? ∞ ? ?4 ?2 ?5 0 ∞ 9711 ∞ 2 ? ? 6 ∞ ? 3? 0 ∞ 2? ? 8 0 6? 6 ?2 0 ? ?S(3)?1 ?1 ? = ?1 ? ?1 ?1 ?2 2 2 1 12 3 3 3 14 4 4 4 42? ? 5? 5? ? 1? 5? ?S (4)?1 ?1 ? = ?1 ? ?1 ?4 ?2 2 2 12 3 3 34 4 4 4 44 42? 5? ? 5? ? 1? 5? ?的第五行、 （5）用 U(4) 的第五行、第五列修正其余的 uij ）?0 ?∞ ? U(4) = ? ∞ ? ?4 ? ?25 0 ∞ 9 711 ∞ 2 ? ? 6 ∞ ? 3? 0 ∞ 2? ? 8 0 6? 6 ?2 0 ? ??0 ? -1 ? U(5) = ? 4 ? ?4 ?2 ?5 08003 -5 0 8 0 6 ?29 9 72? ? ? 3? 2? ? 6? 0? ?S (4)?1 ?1 ? = ?1 ? ?1 ?4 ?2 2 2 1 42 3 3 3 44 4 4 4 42? 5? ? 5? ? 1? 5? ?S (5)?1 ?5 ? = ?5 ? ?1 ?4 ?2 2 2 5 5 3 1 4 3 42 2? 5 5? ? 5 5? ? 4 1? 4 5? ?从 v1 到 v3 的最短路长度u(5) 13=8(5) (5) ∵ s 13 = 2 , s (5) = 5 , s 53 = 4 , s (5) = 3 , 路径： 路径： 23 43 ∴ 从 v 1到 v 3的最短路的路径是P13 = P(v 1 , v 2 , v 5 , v 4 , v 3 )从 v5 到 v2 的 最短路长度及 路径？ 路径？?0 ??1 ? (5) U =? 4 ? ?4 ?2 ?5 0 9 9 78 0 3 ?5 0 0 8 02? ?3? ? 2? ? 6? 6 ?2 0 ? ?S(5)?1 ?5 ? = ?5 ? ?1 ?4 ?2 2 2 2? ? 2 5 5 5? 5 3 5 5? ? 1 3 4 1? 4 4 4 5? ?应用举例： 应用举例：设备更新问题某企业使用一台设备，在每 年年初，企业领导部门就要决定是购置新的，还是继 续使用旧的。若购置新设备，需要支付一定的购置费 用；若继续使用旧设备，则需支付一定的维修费用。 现在的问题是如何制定一个几年之内的设备更新计划， 使得总的支付费用最少。现以二手车问题为例。莎拉购买二手车的数据 最后一年卖出的价值 拥有年份的开车和保养的 购买 费用（美元） （美元） 价格 1 2 3 4 1 2 3 4
00 00 300025,00017,000 10,500 10,500 (Origin) 0 5,500 1 5,500 2 10,500 5,500 3 5,500 4 (Destination)17,000应用：设某台新设备的年效益及年均维修费用、 应用：设某台新设备的年效益及年均维修费用、更新 净费用如下表，试确定今后五年内的更新策略， 净费用如下表，试确定今后五年内的更新策略，使总 效益最大。（ 。（设 效益最大。（设α=1） ） 役龄 0 1 2 3 4 5项目 5 4.5 4 3.75 3 2.5 效益IK(t) 运行费OK(t) 0.5 1 1.5 2 2.5 3 更新费CK(t) 0.5 1.5 2.2 2.5 3 3.512.25 5.8 ① 3 ② 3 8 5.8 ③ 8 15.75 5-0.5-1.5 5-0.5+4.5-1-2.2 5-0.5+4.5-1+4-1.5-2.5 315.25 5.8 ④ 3 10.5 8 ⑤ 4.5 ⑥5-0.5+4.5-1+4-1.5+3.75-3 5-0.5+4.5-1+4-1.5+3.75-2+3-2.5§4网络最大流问题的交通网如下： 例 连接某产品产地 v1 和销地 v6 的交通网如下：制定一个运输方 案，使从 v1 到 v6 v2 的产品数量最多。 的产品数量最多。 10 55 23 51 63v4112v184133 176 2v6这条运输线的 3 最大通过能力 v 3v5 运输数量问题：这个运输网络中， 问题：这个运输网络中，从 v1 到 v6 的最大输送量是 多少？ 多少？4.1 基本概念与定理1.网络与流 网络与流 定义1 给定一个有向图D=(V, A)，在V中指定一点 定义 给定一个有向图 ， 中指定一点 称为发点， 称为收点， vs 称为发点，指定另一点 vt 称为收点，其余点称中间 任意弧(v 点。任意弧 i, vj) ∈A，有Cij≥0，称为弧的容量。称 D ， ，称为弧的容量。 为一个容量网络。 为一个容量网络。记为 D =（V，A，C）。 （ ， ， ）。 定义在弧集A上的一个函数 流: 定义在弧集 上的一个函数 f = { f (vi , vj ) }， ， 并称 f ( vi , vj ) 为弧 ( vi , vj ) 上的流量 ( 简记 fij ) 。如 ( a ) 图是一个 网络 弧旁数字： 弧旁数字：容量v105 3 3v4v182114 5 6v17v3v56（a）如 ( b ) 图是网络上的 5 一个流 一个流v1v2 2 1 1 v32 3v4 6 v6 2 v5弧旁数字： 弧旁数字：流量33 （b） ）v2 10.5 vs 5.5 v1 2.24.3 1.0 3.3v4 8.6 v5 5.4 v3viCij . fijvj8.72.可行流与最大流 可行流与最大流 定义2 满足下述条件的流 f 称为可行流 称为可行流: 定义 1) 容量限制条件 对每一弧 ( vi , vj ) ∈ A 容量限制条件: 0 ≤ fij ≤ Cij2) 平衡条件 对中间点 vi ( i ≠ s, t )，有 平衡条件: ，(v i , v j ) ∈ A∑f ij ?(vj∑∑ff, v i )∈ Aji= 0vs 总是存在的 : (如fij = 0)vt :sj (v s , v j )∈ Atj (v t , v j )∈ A∑f??js (v j , v s )∈ Ajt (v j , v t )∈ A∑f= V(f)净输出量 净输入量∑f= ? V(f)V(f)称为可行流 f 的流量，即发点的净输出量。 称为可行流 的流量，即发点的净输出量。 3.增广链 增广链 对可行流 f = { fij } 非饱和弧： 非饱和弧：fij & Cij 饱和弧： 饱和弧： fij = Cij 非零流弧： 非零流弧：fij & 0 零流弧： 零流弧： fij = 03.增广链 增广链 链的方向： 的一条链， 链的方向：若 ? 是联结 vs 和 vt 的一条链，定 义链的方向是从v 义链的方向是从 s 到 vt 。 前向弧：弧的方向与链的方向一致 一致。 前向弧：弧的方向与链的方向一致。 前向弧全体记为 ?+。 后向弧：弧的方向与链的方向相反。 后向弧：弧的方向与链的方向相反。 相反 后向弧全体记为 ?-。v2 10.5 v1 8.3 v3 6.3 v5 4.1 5.1 3.2 3.3 17.2 5.2 v4 11.6 v6?+=? ?-=?定义3 设 f 是一个可行流， ? 是从 vs 到 vt 的一条链， 是一个可行流， 的一条链， 定义 满足下列条件， 若 ? 满足下列条件，称之为 ( 关于可行流 f 的 ) 一条 增广链。 增广链。 前向弧是 非饱和弧 + ( v, v ) ∈ ? 0≤f &Ci j ij ij( vi, vj ) ∈ ?8. 4 v1 v20 & fij ≤ Cij 5. 0?后向弧是 非零流弧 3. 3 v4v35. 4 v5一条增广链4.截集与截量 截集与截量 设S，T?V，S∩T=Φ ， ， ? ， ∩ Φ 始点在 S，终点在 T 中的 ， 所有弧的集合，记为（ 所有弧的集合，记为（S, T）。 ）。 ST定义4 网络 D=(V, A, C)，若点集 被剖分为两个非 定义 ，若点集V 空集合V 则把弧集(V 空集合 1和V1，使vs∈V1，vt∈V1，则把弧集 1, V1)称 称 为是分离v 的截集。 为是分离 s 和vt的截集。v210.55.4 3.0v411.2 3.3V1 = ( v1, v2, v3 )v18.34.1 5.1v6 (V ,V ) = ? 1 117.6v36.3v5定义5 给一截集（V1, V1），把截集（V1, V1）中所 给一截集（ ），把截集 把截集（ 定义 有弧的容量之和称为这个截集的容量（简称为截量）， 有弧的容量之和称为这个截集的容量（简称为截量）， 记为 C (V1, V1）， 即C (V1 , V1 ) =∑( vi , v j )∈(V1 ,V1 )Cij任何一个可行流的流量V( 任何一个可行流的流量 f ) 都不会超过任一截 集的容量。 集的容量。即V ( f ) ≤ C (V1 , V1 )必是最大流， 若 V ( f ) = C (V1 ,V1 )， f 必是最大流， (V1 ,V1 ) 必是最小截集。 必是最小截集。* * * * * *定理1 是最大流， 定理 可行流 f * 是最大流，当且仅当不存在关于 f * 的 增广链。 增广链。 证明： 是最大流， 中存在关于f 证明：若f *是最大流，设D中存在关于 *的增广链 ?， 中存在关于 ， 令θ = min{min(c ij ? f ij ), min f ij }* *?+?_由增广链的定义，可知 θ & 0，令 由增广链的定义， ，? f ij * + θ ? * = ? f ij ? θ ? f * ? ij (v i , v j ) ∈ ? + (v i , v j ) ∈ ? (v i , v j ) ? ?f ij*不难验证， 不难验证，{ fij**}是一 是一 个可行流， 个可行流，且v( f ** ) = v( f * ) +θ & v( f * )这与f 是最大流的假设矛盾。 这与 *是最大流的假设矛盾。现在设D中不存在关于 的增广链， 现在设 中不存在关于f *的增广链，证明 f * 是最大 中不存在关于 流。 令 vs ∈ V1* 若 vi ∈ V1*，且 fij* & Cij，则令 vj ∈ V1* ， 若 vi ∈ V1* ，且 fji* & 0，则令 vj ∈ V1* ， 记 V1*= V \ V1*， 则 vt ∈ V1* ，f ij*前向饱和弧和 后向零流弧* *?C ij ? =? ?0 ?(v i , v j ) ∈ (V1 ,V 1 )*(v i , v j ) ∈ (V 1 ,V1 )*所以v 必是最大流。 所以 ( f * ) =C(V1*, V1*)，于是 f *必是最大流。 ，定理2 最大流最小截定理 最大流最小截定理) 定理 (最大流最小截定理 任一个网络 D 中，从 vs 到 vt 的最大流的流量等于 的最小截集的容量。 分离 vs，vt 的最小截集的容量。 4.2 寻求最大流的标号法（Ford―Fulkerson） 寻求最大流的标号法（ ） 出发（ 从任一个可行流 f 出发（若网络中没有给定 f ， 则从零流开始），经过标号过程 调整过程。 ），经过标号过程与 则从零流开始），经过标号过程与调整过程。 1.标号过程 标号过程 标号： 前点标记 前点标记， 标号：(前点标记，前点到该 点的这条弧的流量可调整量) 点的这条弧的流量可调整量? ?已检查 ?标号点? 网络中的点? ?未检查 ? ?未标号点开始， 标上（ ， ）， ），v 标号未检查的点 的点， 开始，vs 标上（0，∞）， s 是标号未检查的点， 其余点都是未标号点。一般地， 其余点都是未标号点。一般地，取一个标号未检查的 点 vi ，对一切未标号的点 vj 。 (1) 若弧 i, vj)上，fij&Cij，则给 vj 标号 l (vj ) )， 若弧(v 标号(i, 上 ， (2) 若弧 j, vi)上，fji&0，则给 vj 标号 -i，l ( vj ) )， 若弧(v 标号( ， 上 ， ，fij&Cij vi vj (i , ?(vj)) ?(vj) = min[?(vi),Cij -fij], ? vi fij&0 vj (-i , ?(v )) j?(vj) = min [?(vi), fji] ?重复上述步骤， 被标号， 重复上述步骤，一旦 vt 被标号，则得到一条 vs 到 vt 的增广链。若所有标号都已检查过，而 vt 尚未标号， 的增广链。若所有标号都已检查过， 尚未标号， 结束。当前可行流即最大流。 结束。当前可行流即最大流。2.调整过程 调整过程 （1）找增广链 ） 开始，反向追踪， 从 vt 开始，反向追踪，找出增广链 ?， ， （2）流量调整 上进行流量调整。 并在 ? 上进行流量调整。 令调整量 θ 是 ?(vt)，构造新的可行流 f ?。 ，令 f ij*? f ij * + θ ? * = ? f ij ? θ ? f * ? ij(v i , v j ) ∈ ? + (v i , v j ) ∈ ? (v i , v j ) ? ?去掉所有的标号，对新的可行流f 去掉所有的标号，对新的可行流 ′ = { fij ′ }，重新 ， 进入标号过程。 进入标号过程。（ ） v2 -1,1） (4,3) 例 用标号法求下 图网络的最大流。 图网络的最大流。 (3,3) 弧旁的数字是(C 弧旁的数字是 ij, v (1,1) s fij )。 。 (1,1) (0,∞) ∞(5,1)v4 (5,3) (3,0) (2,1) vt(3,1)解： 标上（ ）； （1）给 vs 标上（0,∞）； ）(s,4) v1(2,2)v3（-2,1） ）在弧(v 标号(s, （2）检查 vs，在弧 s, v1)上，给 v1 标号 4 ) ） 上 （3）检查 1，在弧 v2, v1 ) 上，给 v2 标号 (-1, 1) ）检查v 在弧( （4）检查 2，在弧 v3, v2 )上，给v3 标号 ( -2, 1 ) ）检查v 在弧( 上 标号( （5）检查 3，在弧 v3, vt )上，给vt标号 3, 1 ) ）检查v 在弧( 上 得到标号，标号过程结束。 vt 得到标号，标号过程结束。2.调整过程 调整过程 v2 (3,3) vs (5, 2) v1(4,3) (1, 0) (1, 0)v4 (5,3) (3,0) vt(2, 2) (2,2) v3增广链为? =( vs, v1, v2, v3, vt )，调整量 θ = 1 ，新的 ， 如图所示： 可行流 f ′ 如图所示： 去掉各点标号， 开始，重新标号。 去掉各点标号，从 vs 开始，重新标号。v2 (3,3) vs （0,∞） ） (5,2 ) （s,3） ）(4,3) (1,0 ) (1,0 )v4 (5,3) (3,0) vt(2,2 ) v1 v3(2,2) 标号过程无法进行， 即为最大流。 标号过程无法进行，所以 f ′ 即为最大流。 V(f ′)= 3 + 2 = 5 思考题： 、找出最小截及其截量？ 思考题：1、找出最小截及其截量？ 2、若本题中未给出初始流量，如何求网络 、若本题中未给出初始流量， 最大流？ 最大流？解：设初始可行流为 fij = 0，如图所示： ，如图所示： v2 3, 0 vs (0, ∞) 5, 0 (s, 5) v1 2,0 1, 0 4,0 1, 0 3, 0 v4 5, 0 vt(3, 2)2, 0 v3(1, 2)标号， 标号，得到一增广链 vs→v1 →v3 →vt，调整量 θ = 2，得到新的可行流如图所示： ，得到新的可行流如图所示：(s, 3) v2 3, 0 (0, ∞) vs 5, 2 v1 (s, 3) 1, 04, 0 1, 0v4(2, 3) 5, 0 3, 0 2, 2 v(4, 3) t2, 2v3重新标号，得到增广链v 重新标号，得到增广链 s→v2 →v4 →vt，调整量 θ = 3，得到新的可行流如图所示： ，得到新的可行流如图所示：v2 3, 3 vs (0, ∞) 5, 2 v1 （s, 3） ） 1, 04, 3 1, 0v4 5, 3 3, 0 2, 2 vt2, 2v3继续标号，找不到增广链，当前流即为最大流。 继续标号，找不到增广链，当前流即为最大流。 V( f *)= 3 + 2 = 5练习1： 练习 ： (1) 用标号法求下网络中从点 1到v7的最大流。 用标号法求下网络中从点v 的最大流。 v2 6 v1 9 v3 3 2 5 4 7 v4 1 7 3 v6 6 v5 4 v7每条弧旁的数字为该段弧的容量。 每条弧旁的数字为该段弧的容量。 (2) 上面网络中弧表示单行道，试确定 2v3段道路的 上面网络中弧表示单行道，试确定v 方向。 方向。练习2： 练习 ： 下图中, 为油井， 为脱水处厂， 下图中 点1, 2, 3为油井，点7, 8为脱水处厂，点4、 为油井 为脱水处厂 、 5、6为泵站 弧为管道 弧旁数字为管道通过的最大能 为泵站, 、 为泵站 弧为管道, 小时)， 力(吨/小时 ，求从油井每小时能输送到脱水处理厂的 吨 小时 最大流量。 最大流量。 ① ② 20 10 20 ③ 15 50 10 ⑦ ④ 4 10 ⑥ 50 20 ⑤ 30 30 20 ⑧第五节最小费用最大流问题网络D=(V,A,C),每一弧 i,vj)∈A，给出（vi,vj）上 每一弧(v ∈ ，给出（ 网络 每一弧 单位流的费用b(v ，（简记 单位流的费用 i,vj)≥0，（简记 ij）。 ，（简记b 最小费用最大流问题： 最小费用最大流问题： 求一个最大流 f，使流的总费用 b( f ) = ∑ bij fij ， ( vi ,v j )∈A 取最小值。 取最小值。 费用最小的初始可行流 费用最小的增广链 费用最小的另一可行流8,4,4 v1 v25,0,3?v33,3,3 v45, 3,2 v5弧旁数字（ 弧旁数字（Cij，fij，bij）增加一单位流量时，费用增加多少？ 增加一单位流量时，费用增加多少？ 在一个已知某可行流的容量费用网络中如何求得 费用最小的增广链？ 费用最小的增广链？ 5.1求解原理 求解原理 设对可行流f 存在增广链?，当沿?以 调整f， 设对可行流 存在增广链 ，当沿 以θ=1调整 ，得 调整 显然V(f ')=V(f )+1)，两流的费用之 新的可行流 f ' 时，(显然 显然 ， 差b( f )-b(f′ ) =bij ( f ij' ? f ij ) + ∑ bij ( f ij' ? f ij ) ∑?+ ???+ ??= ∑ bij ? ∑ bij+1-1称为增广链 的费用。 称为增广链 ? 的费用。 最小费用最大流的求解原理 若f 是流值为V（f ）的所有可行流中费用最小者，而 是流值为 （ 的所有可行流中费用最小者， ? 是关于 的所有增广链中费用最小的增广链 则沿 以θ 是关于f 的所有增广链中费用最小的增广链,则沿 则沿? 就是流量为V(f )+ θ的所有可 去调整 f ，得可行流 f ′，f ′就是流量为 行流中费用最小的可行流。这样， 是最大流时， 行流中费用最小的可行流。这样，当 f ′是最大流时， f ′ 就是所求的最小费用最大流。 就是所求的最小费用最大流。两个问题： 两个问题： 1、初始最小费用流如何求得？ 、初始最小费用流如何求得？ 2、如何在已知 f 是流量为 f ) 的最小费用流的情 是流量为V( 、 况下，求出关于f 的最小费用增广链。 况下，求出关于 的最小费用增广链。 求已知最小费用流的最小费用增广链 构造赋权有向图W( f ),它的顶点是 的顶点,W(f )中 构造赋权有向图 它的顶点是D的顶点 中 它的顶点是 的顶点 弧及其权w 按弧（ 中的情形分为： 弧及其权 ij 按弧（vi，vj）在D中的情形分为： 中的情形分为 ? 若(vi , vj)∈A，且fij=0（零弧）， vi ∈ ， （零弧） 则(vi , vj)∈W( f )，且wij = bij ∈ ， vi 3.0 4 4费用vj vj5.5 ? 若(vi , vj )∈A，且fij=cij（饱和弧） vi 饱和弧） ∈ ， vi 则(vj , vi )∈W(f ),且wji= - bij ∈ 且 ? 若(vi , vj)∈A，且0＜fij&cij， ∈ ， ＜ 则(vi , vj)∈W(f ) ，且wij= bij ∈ 及( vj , vi )∈W(f )，且wji= - bij ∈ ， vi vi vi 3 -3 3.2 4 4 -4 vj vj vj vj vj新网络W( f )称为流 的（费用）长度网络。 称为流f 费用）长度网络。 新网络 称为流 由增广链费用的概念及网络W( f )的定义，知在网 的定义， 由增广链费用的概念及网络 的定义 中寻求关于可行流f 络D中寻求关于可行流 的最小费用增广链，等价于在 中寻求关于可行流 的最小费用增广链， 网络W( f )寻求从 s到vt的最短路。 寻求从v 的最短路。 网络 寻求从5.2最小费用最大流算法 最小费用最大流算法第1步：确定初始可行流 0 =0，令k=0； 步 确定初始可行流f ， ； 次调整得到的最小费用流为f 第2步：记经 k 次调整得到的最小费用流为 k， 步 构造增量网络W（ 构造增量网络 （f k）； 第3步：在W（f k）中，寻找 s到vt的最短路。 寻找v 的最短路。 步 （ 即最短路路长是∞)， 若不存在最短路 (即最短路路长是 ，则f k 就是最 即最短路路长是 小费用最大流； 小费用最大流； 若存在最短路，则此最短路即为原网络 中相应的 若存在最短路，则此最短路即为原网络D中相应的 可增广链?，转入第4步 可增广链 ，转入第 步。上对f 第4步：在增广链 上对 k 按下式进行调整，调整量θ 步 在增广链?上对 按下式进行调整，调整量θ 为 θ = min? k k ? ? min (c ij -f ij ) , min f ij ? + ?? ? ?f ijk + 1 令? f ijk + θ ? ? = ? f ijk ? θ ? f ijk ? ?(v i ,v j ) ∈ u (v i , v j ) ? u+(v i , v j ) ∈ u -返回第2步 得新的可行流 f k+1 , 返回第 步。例: 求下图所示网络的 最小费用最大流。 最小费用最大流。弧旁 (4,10) 数字为（bij，cij）。v1(2,5)(1,7)(6,2)vt(2,4)vs(1,8)v2解:（1）取初始可行流 = 0； （ ）取初始可行流f ；0(3,10) v1 1 6 2 v2 3 0 (a) w(f )v3vt 2（2）按算法要求构造长 ） 度网络W(f 0 )，求出从 s vs 度网络 ，求出从v 的最短路。 到vt的最短路。 14v3v11 6 2（3）在原网络 中，与这条最 4 ）在原网络D中 短路对应的增广链为 ? =（vs, v2, v1, vt）。 （vs 1 v2 v1 （4,10） ） vs (1,8) v2 （3,10） ） （1,7） ） （6,2） ） （2,5） ） (2,4) v3 vtvt 23 0 (a) w(f )v3上进行调整， （4）在?上进行调整， ） 上进行调整 如图(b) θ = 5，得f 1，如图 ， 所示。 所示。v1 4 vs 1 v21 6 2 3 0 (a) w(f ) 1 -1 6vt （10,0） ） 2 vs v3 (8,5)v1（7,5） ） （2,0） ）vt (4,0)（5,5） ） v2 v3 (10,0) (b) V(f 1 ) = 5 （7,7） ） （2, 0） ） （5, 5） ） v2 (d) (10, 0) V( f 2)=7 v3v1 4 vs 1 -1 -2 v2vt (10, 2) vs 2 v3 (8, 5)v1vt (4, 0)3 （c） W(f (1)) ）v1 4 vs 1 v2 v1 4 vs 1 -4 -1 -2 v21 6 2 3 0 (a) w(f ) -1 6vt （10, 2） ） 2 vs v3 (8, 5)v1(7, 7) （2, 0） ）vt (4, 0) v3（5, 5） ） v2 (d) vt 2 v3 (10,2) vs (5,5) (8,8) v2 (10,3) (f) V( f 3)=10 v3 v1 (10, 0) V( f 2)=7 (7,7) (2,0) vt (4,3)3 (e) w(f 2 )v1 4 vs 1 v2 v1 4 vs -1 v2 -4 -2 31 6 2 3 0 (a) w(f ) -1 6vt 2 v3 (10, 2) vs (8, 8)v1(7, 7) （2, 0） ）vt (4, 3) v3（5, 5） ） v2 v1 (10, 3) vs -2 v3 (8, 8) v2 (10, 4) (h) V( f 4)=11 (10, 3) (f) V( f 3)=10 (7, 7) （2, 0） ） （5, 4） ） v3 vt (4, 4)vt 2-3 (g) W( f 3)v1 4 vs 1 v21 6 2 3 0 (a) w(f )vt （10, 3） ） 2 vs v3 (8, 8)v1（7, 7） ） （2, 0） ）vt (4, 4)（5, 4） ） v2 v3 (10, 4) (h) V( f 4)=11v14 -4 -1 -2 2-16 3vt-2vs图(i)中，不存在从 s到vt 中 不存在从v 的最短路，所以f 的最短路，所以 4为最小费用 最大流。 最大流。v2-3 ） （i） W(f 4)v3问题： 问题： 中的v 最短路？ （1）如何求网络 （f k）中的 s到vt最短路？ ）如何求网络W（ 的最短路？ （2）如何判断无 s到vt的最短路？ ）如何判断无v练习1： 练习 ： 求下图所示网络的最小费用最大流， 求下图所示网络的最小费用最大流，每弧旁的数 字是( 字是 bij , cij ) 。 (3, 3) (1, 4) (2, 1) (2, 5) (2, 1) (3, 5) (4, 2) (1, 3) (4, 2)vsvt练习2： 练习 ： 下表给出某运输问题的产销平衡表与单位运价表。 下表给出某运输问题的产销平衡表与单位运价表。 将此问题转化为最小费用最大流问题，画出网络图并求 将此问题转化为最小费用最大流问题， 数值解。 数值解。产地 销地1 20 30 42 24 22 53 5 20 6产量 8 7A B 销量不受容量限制，最小总费用为240 。 不受容量限制，最小总费用为(20,8) A (0,8) s (30,7) (0,7) B (22,7) (5,8) (24,8)1(0,4) (0,5)2t(0,6) (20,8) 3弧旁数字为( 弧旁数字为 bij, cij )应用举例： 应用举例： 1.某地的电力公司有三个发电站，他们负责5个城市 某地的电力公司有三个发电站，他们负责 个城市 某地的电力公司有三个发电站 的供电任务，其输电网络如图所示。右图可知， 的供电任务，其输电网络如图所示。右图可知，城市 8由于经济的发展，要求供应电力 由于经济的发展， 由于经济的发展 要求供应电力65MW，3个发电站 ， 个发电站 在满足城市4、 、 、 的用电需要后 的用电需要后， 在满足城市 、5、6、7的用电需要后，他们还分别剩 余15MW、10MW和40MW，输电网络剩余的输电能 、 和 ， 力共有65MW，与城市 的用电需求量刚好相等。问 的用电需求量刚好相等。 力共有 ，与城市8的用电需求量刚好相等 题是输电网络的输电能力是否满足输电65MW的电力， 题是输电网络的输电能力是否满足输电 的电力， 的电力 如不满足，需要增建哪些输电线路？ 如不满足，需要增建哪些输电线路？10MW 1 10 15MW 15 2 30 40MW 3 20 4010⑤20 10S15 40④15⑥15 45⑧⑦2.某木材公司不久将在一个 树 某木材公司不久将在一个 区域的八片树林中砍伐树木。 区域的八片树林中砍伐树木。 林 因此， 因此，它必须建设一个土路 1 系统， 系统，使得每一片树林都能 2 达到其他任何一片树林。 达到其他任何一片树林。每 3 4 两片树林间的距离如右表所 5 单位：公里）。 示（单位：公里）。 6 管理者需要确定哪些树 林之间需要铺路， 林之间需要铺路，使得连接 所有树林的路的总长度最短。 所有树林的路的总长度最短。两片树林之间的距离 1 2 1.3 -0.9 1.8 1.2 2.6 2.3 1.1 3 2.1 0.9 -2.6 1.7 2.5 1.9 1.0 4 0.9 1.8 2.6 -0.7 1.6 1.5 0.9 5 0.7 1.2 1.7 0.7 -0.9 1.1 0.8 6 1.8 2.6 2.5 1.6 0.9 -0.6 1.0 7 2.0 2.3 1.9 1.5 1.1 0.6 -0.5 8 1.5 1.1 1.0 0.9 0.8 1.0 0.5 ---1.3 2.1 0.9 0.7 1.8 7 2.0 8 1.5(1)将此问题转化为图论问题求解并说明原因。 将此问题转化为图论问题求解并说明原因。 将此问题转化为图论问题求解并说明原因 (2)运用所学习过的方法求解此问题，给出最优的铺路方案。 运用所学习过的方法求解此问题，给出最优的铺路方案。 运用所学习过的方法求解此问题
基于运筹学图论的物流网络优化研究 【摘 要】 针对现有物流园区功能发挥不足的问题, 依据物流网络系统特点, 提出以区位优势为依托, 以经济关联为核心的网络优化...西华大学能源与环境学院学生上机实验报告 西华大学上机实验报告课程名称:运筹学 指导教师:施浩然 实验名称:图论、动态规划求解 年级/专业:2009/水利水电工程 姓名:丁...目前图论在物理、化学、运筹学、计算机科学、电 子学、信息论、控制论、网络理论、社会科学及经济管理等几乎所有学科领域都 有应用。 2、平面图和印刷电路板的设计...近二十年来,信息科学、生命科学等现代高科技对人类社会产生了巨大影响, 运筹学工作者还关注到其中一些运筹学起作用的新的工作方向。例如,将全局最 优化、 图论、...图论的方法_军事/政治_人文社科_专业资料。首先,画出街道的拓扑图结构如下:(...一般情况下,在运筹学里面,求最小相对于求最大而言要容易一些,而且,求最大也...运筹学7-9 网络计划技术 图论方法 马尔科分析_数学_自然科学_专业资料。第七章 网络计划技术 复习建议 本章在历年考试中,处于相当重要的地位,建议学员全面掌握,...经过学习我了解到运筹学的具体内容 包括:规划论(包括线性规划、非线性规划、整数规划和动态规划) 、库存论、 图论、决策论、对策论、排队论、博弈论、可靠性理论...2014运筹学-04-1图论-讲... 暂无评价 53页 2下载券 运筹学试卷1 4页 免费...运筹学试题 考试时间: 第 十六 周题 名: 号一二三四五六七八九十 总分 ...运筹学选择_理学_高等教育_教育专区。运筹学 06603 题库一 一、单项选择题(本...戈莫利 D. 康尼格 20.运筹学图论所研究的图 A. 点、边表示事物 B. 点、...图论基础知识汇总(适合建模)_理学_高等教育_教育专区。图与网络模型及方法§1 ...图与网络是运筹学(Operations Research)中的一个经典和重要的分支,所研究的 ...
All rights reserved Powered by
copyright &copyright 。文档资料库内容来自网络，如有侵犯请联系客服。