运筹学 第6章 图论与网络分析

1、第第6章章 图与网络分析图与网络分析1 图的基本概念与模型图的基本概念与模型2 树图和图的最小部分树树图和图的最小部分树3 最短路问题最短路问题4 网络的最大流网络的最大流5 最小费用流最小费用流1 1 图的基本概念与模型图的基本概念与模型 哥尼斯堡七桥问题哥尼斯堡七桥问题 (Knigsberg Bridge Problem) Leonhard Euler (1707-1783) 在在1736年发表第一年发表第一篇图论方面的论文，奠基了图论中的一些基本篇图论方面的论文，奠基了图论中的一些基本定理定理BACDABCD 20世纪中期，随着计算机和离散数学的发展，图论取得了世纪中期，随着计算机和离散

2、数学的发展，图论取得了很大的进展。很大的进展。 目前图论被广泛地应用于管理科学、计算机科学、信息论、目前图论被广泛地应用于管理科学、计算机科学、信息论、控制论等各领域，并取得了丰硕的成果。控制论等各领域，并取得了丰硕的成果。 图的特点：图的特点： 用点代表研究的对象，用点与点之间的联线表示两个对用点代表研究的对象，用点与点之间的联线表示两个对象间的关系。象间的关系。 图中点的相对位置如何，点与点之间联线的长短曲直，图中点的相对位置如何，点与点之间联线的长短曲直，对反映对象间的关系不重要。故图论中的图与几何图、对反映对象间的关系不重要。故图论中的图与几何图、工程图等是不同的。工程图等是不同的。

3、图用图用G= V, E 表示。表示。V是点集合是点集合; E是边集合。是边集合。端点、关联边、相邻端点、关联边、相邻 若节点若节点vi , vj 之间有一条边之间有一条边 eij=vi ,vj，则称，则称 vi 和和 vj 是是 eij 的端点，而的端点，而 eij 是节点是节点 vi 和和 vj 的关联边。的关联边。 同一条边的两个端点称为相邻节点，具有共同端点的边称同一条边的两个端点称为相邻节点，具有共同端点的边称为相邻边。为相邻边。环、多重边，简单图环、多重边，简单图 若边若边e 的两个端点相重，称该边为环；的两个端点相重，称该边为环； 若两个点之间的边多于一条，称为具有多重边；若两个点

4、之间的边多于一条，称为具有多重边； 对无环、无多重边的图称为简单图。对无环、无多重边的图称为简单图。次、奇点、偶点、孤立点、悬挂点次、奇点、偶点、孤立点、悬挂点 与某一个点与某一个点vi 相关联的边的数目称为次相关联的边的数目称为次(也称度也称度)，记，记d(vi)；图的基本概念图的基本概念多重边多重边环环v1v5v4v3v2e12e34e13e24e45图图6 6. .2 2 简简单单图图无环、无多重边的图称为无环、无多重边的图称为简单图简单图V6孤立孤立点点悬挂悬挂点点v1v5v4v3v2e12e34e13e24e22e13e45图图 6.1l次为奇数的点称为奇点；次为偶数的点称为偶点；次

5、为奇数的点称为奇点；次为偶数的点称为偶点；l次为次为0的点称为孤立点；次为的点称为孤立点；次为1的点称为悬挂点的点称为悬挂点。链、路、圈、回路、连通图链、路、圈、回路、连通图 点和边交错序列点和边交错序列 ，若其中各边，若其中各边 互不相同，且任意互不相同，且任意 和和 均相邻，称均相邻，称 为链；为链； 若链中所有顶点若链中所有顶点 也不相同，这样的链称为路；也不相同，这样的链称为路； 起点与终点重合的链为圈起点与终点重合的链为圈; 起点与终点重合的路为回路；起点与终点重合的路为回路； 若图中每一对顶点之间至少存在一条链，这样的图称为若图中每一对顶点之间至少存在一条链，这样的图称为连通图；否

6、则，称为非连通图；连通图；否则，称为非连通图； kkvevev,110kee,11, tivktvti2,kvvv,10无向图、有向图、弧无向图、有向图、弧 边都没有方向的图，称为无向图，用边都没有方向的图，称为无向图，用G(V, E)表示；在无向表示；在无向图中图中 eij=eji，或，或 (vi, vj)=(vj, vi) 当边都有方向时，称为有向图，用当边都有方向时，称为有向图，用G(V, A)表示；表示； 在有向图中，有向边又称为弧，用在有向图中，有向边又称为弧，用 aij表示，表示，i, j 的顺序是的顺序是不能颠倒的，弧的方向用箭头标识。不能颠倒的，弧的方向用箭头标识。完全图、偶图

7、完全图、偶图 一个简单图若任意两点之间均有边相连，称这样的图为一个简单图若任意两点之间均有边相连，称这样的图为完全图；完全图； 若图的顶点能分成两个互不相交的非空集合若图的顶点能分成两个互不相交的非空集合V1和和V2，使，使在同一个集合中任意两个顶点均不相邻，称为偶图在同一个集合中任意两个顶点均不相邻，称为偶图(也也称二分图称二分图)。子图、部分图子图、部分图 图图G1= V1 , E1 和图和图G2= V2 , E2 ，如果有，如果有 ， 和和 称称G1是是G2的一个子图；的一个子图； 若有若有 ，则称，则称G1是是G2的一个部分图的一个部分图(又称支又称支撑子图撑子图)。21VV 21EE

8、 2121,EEVV2 2 树图和图的最小部分树树图和图的最小部分树 无圈的连通图，称为树，记为无圈的连通图，称为树，记为T(V, E) 2-1 树的性质树的性质 任何树中必存在次为任何树中必存在次为1的点；的点； 具有具有n个顶点的树的边数恰好为个顶点的树的边数恰好为n-1条条; 任何具有任何具有n个点、个点、(n-1)条边的连通图是树图。条边的连通图是树图。2-2 图的最小部分树图的最小部分树 树图的各条边称为树枝。对含有权重的图来讲，树枝总树图的各条边称为树枝。对含有权重的图来讲，树枝总长最小的部分树，称为该图的最小部分树。长最小的部分树，称为该图的最小部分树。 定理定理1：图中任一个点

9、：图中任一个点i，若，若j是与是与i相邻点中距离最近的，则相邻点中距离最近的，则边边i, j一定必含在该图的最小部分树内。一定必含在该图的最小部分树内。 证明：略。证明：略。 推论：把图的所有点分成推论：把图的所有点分成 和和 两个集合，则两个集合之两个集合，则两个集合之间连线的最短边一定包含在最小部分树内。间连线的最短边一定包含在最小部分树内。VV2-3 避圈法和破圈法避圈法和破圈法避圈法的步骤：避圈法的步骤：(1) 从图中任选一点从图中任选一点vi，让，让 ，图中其余点均包含在，图中其余点均包含在 中中(2) 从从 与与 的连线中找出最小边，这条边一定包含在最小的连线中找出最小边，这条边一

10、定包含在最小部分树内，假设为部分树内，假设为 ，将，将 加粗，以标记是最小加粗，以标记是最小部分树内的边；部分树内的边；(3) 令令 ；(4) 重复重复2、3两步，一直到图中所有点均包含在两步，一直到图中所有点均包含在 中为止。中为止。VviVVVjivv ,jivv ,VvVVvVjj,V例：用避圈法，求下图的最小部分树例：用避圈法，求下图的最小部分树v1v5v3v2v4v6237446551破圈法的步骤：破圈法的步骤： 从网络图从网络图N中任取一回路，去掉这个回路中权数最中任取一回路，去掉这个回路中权数最大的边，得一子网络图大的边，得一子网络图N1。在。在N1中再任取一回路，再去中再任取一

11、回路，再去掉回路中权数最大的一条边，得掉回路中权数最大的一条边，得N2。如此继续下去，一。如此继续下去，一直到剩下的子图中不再含有回路为止，该子图就是直到剩下的子图中不再含有回路为止，该子图就是N的的最小部分树。最小部分树。例：用破圈法，求下图的最小部分树例：用破圈法，求下图的最小部分树v1v5v3v2v4v6237446551=3 最短路问题最短路问题 最短路的一般提法为：设最短路的一般提法为：设 为连通图，图中各边为连通图，图中各边 有权有权 （ 表示表示 之间没有边），之间没有边），为图中任意两点，求一条路为图中任意两点，求一条路 ，使它为从，使它为从 到到 的所有的所有 路中总权最短。

12、即：路中总权最短。即： ),(EVG jil),(jivvjiljivv ,tsvv ,svtv),()(jivvjilL最小。最小。3-1 迪杰斯特拉迪杰斯特拉(Dijkstra)算法算法算法的思想：算法的思想：如果如果P是从是从vs到到vt的最短路，的最短路，vi是是P上的一个上的一个 点，那么，从点，那么，从vs沿沿P到到vi的路是从的路是从vs到到vi的最短路。的最短路。 算法的步骤：算法的步骤：(1)从点从点s出发，因出发，因Lss=0，将此值标注在，将此值标注在s旁的小方框内，表旁的小方框内，表示示s点已标号；点已标号；(2) 从从s点出发，找出与点出发，找出与s相邻点中距离最小的

13、一个，设为相邻点中距离最小的一个，设为r.将将Lsr=Lss+dsr的值标注在的值标注在r旁小方框内，表明点旁小方框内，表明点r已标号；已标号；(3) 从已标号的点出发，找出与这些点相邻的所有未标号从已标号的点出发，找出与这些点相邻的所有未标号点点p。若有。若有 ，则对，则对p点标号，点标号，并将并将Lsp的值标注在的值标注在p点旁的小方框内；点旁的小方框内；rpsrspssspdLdLL,min 设设dij为图中两相邻点为图中两相邻点i与与j的距离，若不相邻，的距离，若不相邻，dij=0；Lsi为点为点 s到到i的最短距离的最短距离, 求求s点到点到t点最短距离。点最短距离。(4) 重复第重

14、复第3步，一直到步，一直到t点得到标号为止。点得到标号为止。例例3 求从求从v1到到v7的最短路的最短路解：解：(1)131312122, 5min,minLddLp3613341312111,mindLdLdLLp12542, 72, 50minL(2)(3)(5)(4)36133413241225121,mindLdLdLdLLp16642, 72, 25, 75minL6716651664163413241225121,mindLdLdLdLdLdLLp1514766 , 16 , 26, 72, 25, 75minLL例例 求从点求从点1 1到点到点8 8的最短路径的最短路径23718

15、4566134105275934682(6)1066 , 37min,min6716571517dLdLL48237184566131052759346201(1)解：解：(2)min d12,d14,d16=min 0+2,0+1,0+3=L14=1min L12,L16,L14+d42,L14+d47=min 0+2,0+3,1+10,1+2=L12=24823718456613105275934620(3)(4)min L16,L12d23,L12+d25,L14+d47=min 0+3,2+6,2+5,1+2=L16=L17=323718456613410527593468221023

16、718456613410527593468221033482371845661310527593462210633(5)min L12+d23,L12+d25,L17+d75,L17+d78=min 2+6,2+5,3+3,3+8=L15=6min L12+d23,L15+d53,L15+d58,L17+d78=min 2+6,6+9,6+4,3+8=L13=8(6)2371845661341052759346822103368102371845661341052759346822103368min L13+d38,L15+d58,L17+d78=min 8+6,6+4,3+7=L18=10(

17、7)3-2 求任意两点间最短路的矩阵算法求任意两点间最短路的矩阵算法(Ford 算法算法)计算步骤：计算步骤：(1) 根据图中任两点根据图中任两点i和和j的关系，给出直接距离矩阵的关系，给出直接距离矩阵 ；(2) 构造构造矩阵矩阵 ，令，令 ，则，则 表示表示点点i和和j直接到达和有一个中间点时的最短距离。直接到达和有一个中间点时的最短距离。 1D 001minrjirrijddd 00ijdD(3) 再构造矩阵再构造矩阵 ，令，令 ，则，则 表示点表示点i和和j直接到达，及经过一至三个中间点的最短距离。直接到达，及经过一至三个中间点的最短距离。 2D 112minrjirrijddd(4)

18、迭代更新迭代更新k次，生成一个新矩阵次，生成一个新矩阵 kD 1D 2DmmDD1 kD 表示网络中任意两点直接到达，及经过一个、两个到表示网络中任意两点直接到达，及经过一个、两个到(2k-1)个中间点时的最短距离。个中间点时的最短距离。设网络中有设网络中有p个点，个点， 中中k值的大小由下式确定：值的大小由下式确定： kD122121kkpkpk2lg1lg1 或或 当当 时，停止计算。时，停止计算。 11minkrjkirrkijddd即：即：例例2：求任意两点的最短距离：求任意两点的最短距离解：77767574737271676665646362615756555453525147464

19、544434241373635343332312726252423222117161514131211ddddddddddddddddddddddddddddddddddddddddddddddddd06360124310672607247027205250 043810104012446310357128230627104560721047270561272501D 0436881040124463103557623062784560728452705106772502D 23DD 中的元素中的元素 为图中从为图中从i点到点到j点的最短距离。点的最短距离。 2D 2ijd6 . 22lg6l

20、g2lg1lgp6.9 某人购买一辆摩托车，准备在今后某人购买一辆摩托车，准备在今后4年内使用，他可在年内使用，他可在第一年初购一辆新车，连续使用第一年初购一辆新车，连续使用4年，也可于任何一年年末年，也可于任何一年年末卖掉，于下一年初换一台新车。已知各年初的新车购置价如卖掉，于下一年初换一台新车。已知各年初的新车购置价如表表66，不同役龄车的年使用维护费及年末处理价见表，不同役龄车的年使用维护费及年末处理价见表67。要求确定该人使用摩托车的最优更新策略，使要求确定该人使用摩托车的最优更新策略，使4年内用于购年内用于购买、更换及使用维护的总费用最省。买、更换及使用维护的总费用最省。表表6-6表

21、表6-7解：构造有向图，以点表示各年初，弧解：构造有向图，以点表示各年初，弧(i,j)旁数字表示第旁数字表示第i年初年初买新车用到第买新车用到第j年初年初(即第即第j-1年末年末)卖掉时的总支出费用，记为卖掉时的总支出费用，记为dij。则则dij等于第等于第i年初的购车费，加上用到第年初的购车费，加上用到第j年初支付的使用维护年初支付的使用维护费，再减去按役龄年末处理费。费，再减去按役龄年末处理费。8 . 00 . 23 . 05 . 212d7 . 16 . 15 . 03 . 05 . 213d8 . 23 . 18 . 05 . 03 . 05 . 214d2 . 41 . 12 . 1

22、8 . 05 . 03 . 05 . 215d9 . 00 . 23 . 06 . 223d8 . 16 . 15 . 03 . 06 . 224d9 . 23 . 18 . 05 . 03 . 06 . 225d1 . 10 . 23 . 08 . 234d0 . 26 . 15 . 03 . 08 . 235d4 . 10 . 23 . 01 . 345d最优方案：最优方案：(1) 第一年初买新车，年末卖掉再买新车，一直用到第四年末卖掉第一年初买新车，年末卖掉再买新车，一直用到第四年末卖掉(2) 第一年初买新车，用两年后于第二年末卖掉再买新车，用两年第一年初买新车，用两年后于第二年末卖掉再

23、买新车，用两年后于第四年末卖掉；后于第四年末卖掉；(3) 第一年初买新车，年末卖掉后再买新车，用一年后即第二年末第一年初买新车，年末卖掉后再买新车，用一年后即第二年末又卖掉再买新车，再用两年后于第四年末卖掉；又卖掉再买新车，再用两年后于第四年末卖掉； 最优方案支出总费用为最优方案支出总费用为3.7万元。万元。4 4 网络的最大流网络的最大流4-1 网络最大流的有关概念网络最大流的有关概念网络流一般在有向图上讨论网络流一般在有向图上讨论图中规定一个发点图中规定一个发点s，一个收点，一个收点t，余为中间点余为中间点 网络上每条弧的最大通行能力，称为该弧的容量，记为网络上每条弧的最大通行能力，称为该

24、弧的容量，记为 c(vi,vj)或或cij ，弧上实际流量记为，弧上实际流量记为 fij 节点没有容量限制，流在节点不会存储节点没有容量限制，流在节点不会存储满足下列两个条件的流，称为满足下列两个条件的流，称为可行流可行流 容量限制条件：容量限制条件：0 fij cij 平衡条件：平衡条件：tifvtsisifvffjjiivBvjivAvij)(,0)()()(viA(vi)B(vi) 最大流最大流:满足容量约束条件和平衡条件满足容量约束条件和平衡条件,使使v(f)值为最大的流值为最大的流4-2 割和流量割和流量 将容量网络中的发点和收点分割开，并使将容量网络中的发点和收点分割开，并使 的流

25、的流中断的一组弧的集合，称为割中断的一组弧的集合，称为割(截集截集)； 一般包含一般包含 s 点的节点集合用点的节点集合用V表示，包含表示，包含 t 点的节点集点的节点集合用合用 表示；弧的集合表示；弧的集合 表示割；表示割； 割割(截集截集)的容量：指组成它的集合中各弧的容量之和的容量：指组成它的集合中各弧的容量之和ts VVVjijivvcVVc,即：即：VV,4-3 最大流最小割定理最大流最小割定理 如果在网络的发点和收点之间能找出一条链，在这条链上如果在网络的发点和收点之间能找出一条链，在这条链上所有指向所有指向 的弧的弧(称为称为前向弧前向弧，记，记 )，存在，存在 ；所有；所有指向

26、指向 的弧的弧(称称后向弧后向弧，记，记 )，存在，存在 ，这样的链称，这样的链称为为增广链增广链。定理：网络中定理：网络中 的最大流量等于它的最小割集的容量，即的最大流量等于它的最小割集的容量，即ts VVcfv,证明：略。证明：略。ts cf st 0f 当网络中存在增广链时，找出当网络中存在增广链时，找出对对iiiffcmin对非增广链上的弧对所有对所有iiiffff 仍是一个可行流，流量比仍是一个可行流，流量比 增大了增大了 值值f f04-4 求网络最大流的标号算法求网络最大流的标号算法(Ford-Fulkerson标号算法标号算法)算法实质：判断网络中是否有增广链，若有，找出调整算

27、法实质：判断网络中是否有增广链，若有，找出调整算法的步骤：算法的步骤：第一步：标号过程，找一条增广链第一步：标号过程，找一条增广链1、给源点、给源点 s 标号标号(0, )， 表示表示 s 点不限流量点不限流量2、找出与已标号节点找出与已标号节点 i 相邻的所有未标号节点相邻的所有未标号节点 j，若，若 (i, j)是前向弧且饱和，则节点是前向弧且饱和，则节点 j 不标号；不标号； (i, j)是前向弧且未饱和是前向弧且未饱和( ) ，则节点，则节点 j 标号为标号为 (i, )， ； s jijijcf s ijijfcij,min (i, j)是后向弧，若是后向弧，若 fji=0，则节点，则节点 j 不标号；不标号； (i, j)是后向弧，若是后向弧，若 fji0，则节点，则节点 j 标号为标号为(i, )，3、重复步骤、重复步骤 2，可能出现两种情况：，可能出现两种情况： 标号过程中断，节点标号过程中断，节点 t 尚未标号，说明网