第十一章图与网络模型 §1图与网络的基本概念 §2最短路问题 §3最小生成树问题 §4最大流问题 §5最小费用最大流问题 管理蓦
管 理 运 筹 学 1 第十一章 图与网络模型 §1 图与网络的基本概念 §2 最短路问题 §3 最小生成树问题 §4 最大流问题 §5 最小费用最大流问题
§1图与网络的基本概念 图论中图是由点和边构成,可以反映一些对象之间的关系。 例如:在一个人群中,对相互认识这个关系我们可以用图 来表示,图11-1就是一个表示这种关系的图 e (v3)孙 赵 (v2)钱 李 (v7)陈 周 (6吴 图11-1 运筹
管 理 运 筹 学 2 §1 图与网络的基本概念 图论中图是由点和边构成，可以反映一些对象之间的关系。 例如：在一个人群中，对相互认识这个关系我们可以用图 来表示，图11-1就是一个表示这种关系的图。 (v1 ) 赵 (v2 )钱 (v3 )孙 (v4 ) 李 (v5 ) 周 (v6 )吴 (v7 )陈 e2 e1 e3 e4 e5 图11-1
§1图与网络的基本概念 当然图论不仅仅是要描述对象之间关系,还要研究特定关 系之间的内在规律,一般情况下图中点的相对位置如何、点与 点之间联线的长短曲直,对于反映对象之间的关系并不是重要 的,如对赵等七人的相互认识关系我们也可以用图11-2来表示, 可见图论中的图与几何图、工程图是不一样的。 赵(v2钱孙()李)周(s陈(v) 图11-2 管理蓦
管 理 运 筹 学 3 §1 图与网络的基本概念 当然图论不仅仅是要描述对象之间关系，还要研究特定关 系之间的内在规律，一般情况下图中点的相对位置如何、点与 点之间联线的长短曲直，对于反映对象之间的关系并不是重要 的，如对赵等七人的相互认识关系我们也可以用图11-2来表示， 可见图论中的图与几何图、工程图是不一样的。 (v1 ) 赵 (v2 )钱 孙(v3 ) 李(v4 ) 周(v5 ) 吴(v6 ) 陈(v7 ) e2 e1 e3 e4 e5 图11-2
§1图与网络的基本概念 如果我们把上面例子中的“相互认识”关系改为“认识” 的关系,那么只用两点之间的联线就很难刻画他们之间的关 系了,这是我们引入一个带箭头的联线,称为弧。图113就 是一个反映这七人“认识”关系的图。相互认识用两条反向 的弧表示。 (v2)钱 赵 李 (v3)孙 (v7)陈 ()吴 周 图11-3
管 理 运 筹 学 4 §1 图与网络的基本概念 a1 a2 a3 a4 a14 a7 a8 a9 a a6 5 a10 a12 a11 a13 a15 (v1 ) 赵 (v2 )钱 (v3 )孙 (v4 ) 李 (v5 ) 周 (v6 )吴 (v7 )陈 图11-3 如果我们把上面例子中的“相互认识”关系改为“认识” 的关系，那么只用两点之间的联线就很难刻画他们之间的关 系了，这是我们引入一个带箭头的联线，称为弧。图11-3就 是一个反映这七人“认识”关系的图。相互认识用两条反向 的弧表示
§1图与网络的基本概念 无向图 由点和边构成的图,记作G=(V,E)。 有向图 由点和弧构成的图,记作D=(V,A)。 连通图: 对无向图G,若任何两个不同的点之间,至少存在一条链,则G为 连通图 回路: 若路的第一个点和最后一个点相同,则该路为回路。 赋权图: 对个无向图G的每、条边(vy),相应地有一个数wg,则称图G 为赋权图,w1称为边(y)上的校。 网络: 在赋权的有向图D中指定一点,称为发点,指定另二点称为收点 其它点称为中间点,并把D中的每一条弧的赋权数称为弧的容量,D就 称为网络。 管理蓦
管 理 运 筹 学 5 §1 图与网络的基本概念 ▪ 无向图： 由点和边构成的图，记作G=（V，E）。 • 有向图： 由点和弧构成的图，记作D=（V，A）。 • 连通图： 对无向图G，若任何两个不同的点之间，至少存在一条链，则G为 连通图。 • 回路： 若路的第一个点和最后一个点相同，则该路为回路。 • 赋权图： 对一个无向图G的每一条边(vi ,vj )，相应地有一个数wij，则称图G 为赋权图，wij称为边(vi ,vj )上的权。 • 网络： 在赋权的有向图D中指定一点，称为发点，指定另一点称为收点， 其它点称为中间点，并把D中的每一条弧的赋权数称为弧的容量，D就 称为网络
§2最短路问题 6.2.1最短路问题的网络模型 最短路问题,就是从给定的网络图中找出一点到各点或任意两 点之间距离最短的一条路 最短路问题在实际中具有广泛的应用,如管道铺设、线路选择 等问题,还有些如设备更新、投资等问题也可以归结为求最短 路问题 求最短路有两种算法: 是求从某一点至其它各点之间最短离的狄克斯屈拉 Dijkstra)算法 另一种是求网络图上任意两点之间最短路的 Floyd(弗洛伊德) 矩阵算法。 管理蓦
管 理 运 筹 学 6 §2 最短路问题 最短路问题在实际中具有广泛的应用，如管道铺设、线路选择 等问题，还有些如设备更新、投资等问题也可以归结为求最短 路问题 求最短路有两种算法： 一是求从某一点至其它各点之间最短离的 狄克斯屈拉 (Dijkstra)算法 另一种是求网络图上任意两点之间最短路的Floyd(弗洛伊德) 矩阵算法。 最短路问题，就是从给定的网络图中找出一点到各点或任意两 点之间距离最短的一条路 6.2.1最短路问题的网络模型
§2最短路问题 最短路问题:对一个赋权的有向图D中的指定的两个点V和V找到一条 从v到的路,使得这条路上所有弧的权数的总和最小,这条路被称 之为从V到V的最短路。这条路上所有弧的权数的总和被称为从到v 的距离。 、求解最短路的 Dijkstra算法(双标号法) 步骤: 1给出点V以标号(0,s) 2找出已标号的点的集合I,没标号的点的集合J以及弧的集合 (,v)v∈1,V∈ 3.如果上述弧的集合是空集,则计算结束。如果v已标号(Lnk),则v 到v的距离为1,而从ⅴ到v的最短路径,则可以从k反向追踪到起点 v而得到。如果v未标号,则可以断言不存在从v到v的有向路。如果 上述的弧的集合不是空集,则转下一步 4.对上述弧的集合中的每一条弧,计算s=-+ci。在所有的s中,找到其 值为最小的弧。不妨设此弧为(VV),则给此弧的终点以双标号 (sa,c),返回步骤2
管 理 运 筹 学 7 §2 最短路问题 • 最短路问题：对一个赋权的有向图D中的指定的两个点Vs和Vt找到一条 从 Vs 到 Vt 的路，使得这条路上所有弧的权数的总和最小，这条路被称 之为从Vs到Vt的最短路。这条路上所有弧的权数的总和被称为从Vs到Vt 的距离。 一、求解最短路的Dijkstra算法(双标号法） 步骤： 1.给出点V1以标号(0,s) 2.找出已标号的点的集合I，没标号的点的集合J以及弧的集合 3. 如果上述弧的集合是空集，则计算结束。如果vt已标号（l t ,kt），则vs 到vt的距离为l t，而从vs到vt的最短路径，则可以从kt 反向追踪到起点 vs 而得到。如果vt未标号，则可以断言不存在从vs到vt的有向路。如果 上述的弧的集合不是空集，则转下一步。 4. 对上述弧的集合中的每一条弧，计算sij=li+cij 。在所有的sij中，找到其 值为最小的弧。不妨设此弧为（Vc ,Vd），则给此弧的终点以双标号 （scd,c）,返回步骤2。 {( , ) | , } i j i j v v v I v J
§2最短路问题 例1求下图中v到v的最短路 6 2 3 解:采用 Dijkstra算法,可解得最短路径为v→v34→v6 各点的标号图如下: 3,1) 8,4) 7 6 3,3)5 5 (0,s 5 2. 5 管理蓦
管 理 运 筹 学 8 §2 最短路问题 例1 求下图中v1到v6的最短路 解：采用Dijkstra算法，可解得最短路径为v1 v3 v4 v6 各点的标号图如下： v2 3 5 2 7 5 3 1 5 2 1 v1 v6 v v5 3 v4 (3,1) v2 3 5 2 7 5 3 1 5 2 1 V1 （0,s) v5 (8,4) v6 (2,1) v3 (3,3) v4
§2最短路问题 【例】用 Dijkstra算法求图6-6所示v到v的最短路及最短路长 18,3 420 2 29 ① 1010 0,0 3 824 ⑦295 9,2 16 5 12 32 ④ 517 12.1 16,3 图6-6 v1到v的最短路为:p17={v,v2,吟3,"5,v},最短路长为L17=29 理蓦总
管 理 运 筹 学 9 §2 最短路问题 ② ③ ④ ⑤ ⑥ ⑦ 6 10 12 3 2 14 7 6 5 8 11 16 5 图6－6 9 0,0 6 10 12 9 20 9,2 18 6,1 ① 16 12,1 17 16,3 24 32 18,3 29 29,5 【例】用Dijkstra算法求图6－6 所示v1到v7的最短路及最短路长 v1 到v7的最短路为：p17=｛v1 , v2 , v3 , v5 , v7｝，最短路长为L17=29 14
§2最短路问题 【例】求图6-10所示v到各点的最短路及最短距离 6,3 1218 6 6 28 0,0① 55/3,4 912851624 ⑧185 6 2 13 612 2 24 ④ 810 2,1 6,3 图6-10 所有点都已标号,点上的标号就是v1到该点的最短距离,最短路 线就是红色的链。 10
管 理 运 筹 学 10 【例】求图6-10所示v1到各点的最短路及最短距离 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 4 5 2 6 1 7 8 3 9 3 2 6 12 16 18 0,0 4 5 2 2,1 3 10 3,4 9 6 12 6 4,1 11 6,3 6,3 18 8 12 24 8,5 24 18,5 所有点都已标号，点上的标号就是v1到该点的最短距离，最短路 线就是红色的链。 图6-10 §2 最短路问题