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

《运筹学 第6章 图论与网络分析讲解》由会员分享，可在线阅读，更多相关《运筹学 第6章 图论与网络分析讲解（40页珍藏版）》请在金锄头文库上搜索。

1、第6章 图与网络分析 1 图的基本概念与模型 2 树图和图的最小部分树 3 最短路问题 4 网络的最大流 5 最小费用流 1 图的基本概念与模型 哥尼斯堡七桥问题 (Knigsberg Bridge Problem) Leonhard Euler (1707-1783) 在1736年发表第 一篇图论方面的论文，奠基了图论中的一些基 本定理 B A C D 20世纪中期，随着计算机和离散数学的发展，图论取得了 很大的进展。 目前图论被广泛地应用于管理科学、计算机科学、信息论 、控制论等各领域，并取得了丰硕的成果。 图的特点： 用点代表研究的对象，用点与点之间的联线表示两个对 象间的关系。 图中点

2、的相对位置如何，点与点之间联线的长短曲直， 对反映对象间的关系不重要。故图论中的图与几何图、 工程图等是不同的。 图用G= V, E 表示。V是点集合; E是边集合。 端点、关联边、相邻 若节点vi , vj 之间有一条边 eij=vi ,vj，则称 vi 和 vj 是 eij 的端点，而 eij 是节点 vi 和 vj 的关联边。 同一条边的两个端点称为相邻节点，具有共同端点的边 称为相邻边。 环、多重边，简单图 若边e 的两个端点相重，称该边为环； 若两个点之间的边多于一条，称为具有多重边； 对无环、无多重边的图称为简单图。 次、奇点、偶点、孤立点、悬挂点 与某一个点vi 相关联的边的数目

3、称为次(也称度)，记d(vi) ； 图的基本概念 多重边 环 v1 v5 v4v3 v2 e12 e34 e13e24 e45 图6.2 简单图 无环、无多重边的图称为 简单图 V6 孤立 点 悬挂 点 v1 v5 v4v3 v2 e12 e34 e13e24 e22 e13 e45 图 6.1 l次为奇数的点称为奇点；次为偶数的点称为偶点； l次为0的点称为孤立点；次为1的点称为悬挂点。 链、路、圈、回路、连通图 点和边交错序列 ，若其中各边 互不相同，且任意 和 均相邻，称 为链； 若链中所有顶点 也不相同，这样的链称为路； 起点与终点重合的链为圈; 起点与终点重合的路为回路； 若图中每一

4、对顶点之间至少存在一条链，这样的图称为 连通图；否则，称为非连通图； 无向图、有向图、弧 边都没有方向的图，称为无向图，用G(V, E)表示；在无 向图中 eij=eji，或 (vi, vj)=(vj, vi) 当边都有方向时，称为有向图，用G(V, A)表示； 在有向图中，有向边又称为弧，用 aij表示，i, j 的顺序是 不能颠倒的，弧的方向用箭头标识。 完全图、偶图 一个简单图若任意两点之间均有边相连，称这样的图为 完全图； 若图的顶点能分成两个互不相交的非空集合V1和V2，使 在同一个集合中任意两个顶点均不相邻，称为偶图(也 称二分图)。 子图、部分图 图G1= V1 , E1 和图G

5、2= V2 , E2 ，如果有 ， 和 称G1是G2的一个子图； 若有 ，则称G1是G2的一个部分图(又称支 撑子图)。 2 树图和图的最小部分树 无圈的连通图，称为树，记为T(V, E) 2-1 树的性质 任何树中必存在次为1的点； 具有n个顶点的树的边数恰好为n-1条; 任何具有n个点、(n-1)条边的连通图是树图。 2-2 图的最小部分树 树图的各条边称为树枝。对含有权重的图来讲，树枝总 长最小的部分树，称为该图的最小部分树。 定理1：图中任一个点i，若j是与i相邻点中距离最近的，则 边i, j一定必含在该图的最小部分树内。 证明：略。 推论：把图的所有点分成 和 两个集合，则两个集合之

6、 间连线的最短边一定包含在最小部分树内。 2-3 避圈法和破圈法 避圈法的步骤： (1) 从图中任选一点vi，让 ，图中其余点均包含在 中 (2) 从 与 的连线中找出最小边，这条边一定包含在最小 部分树内，假设为 ，将 加粗，以标记是最小 部分树内的边； (3) 令 ； (4) 重复2、3两步，一直到图中所有点均包含在 中为止。 例：用避圈法，求下图的最小部分树 v1 v5v3 v2 v4 v6 2 3 7 4 46 5 5 1 破圈法的步骤： 从网络图N中任取一回路，去掉这个回路中权数最 大的边，得一子网络图N1。在N1中再任取一回路，再去 掉回路中权数最大的一条边，得N2。如此继续下去，

7、一 直到剩下的子图中不再含有回路为止，该子图就是N的 最小部分树。 例：用破圈法，求下图的最小部分树 v1 v5v3 v2 v4 v6 2 3 7 4 46 5 5 1 = = = = 3 最短路问题 最短路的一般提法为：设 为连通图，图中各边 有权 （ 表示 之间没有边）， 为图中任意两点，求一条路 ，使它为从 到 的所有 路中总权最短。即： 最小。 3-1 迪杰斯特拉(Dijkstra)算法 算法的思想：如果P是从vs到vt的最短路，vi是P上的一个 点，那么，从vs沿P到vi的路是从vs到vi的最短路。 算法的步骤： (1)从点s出发，因Lss=0，将此值标注在s旁的小方框内，表 示s点

8、已标号； (2) 从s点出发，找出与s相邻点中距离最小的一个，设为r. 将Lsr=Lss+dsr的值标注在r旁小方框内，表明点r已标号； (3) 从已标号的点出发，找出与这些点相邻的所有未标号 点p。若有 ，则对p点标号， 并将Lsp的值标注在p点旁的小方框内； 设dij为图中两相邻点i与j的距离，若不相邻，dij=0；Lsi为点 s到i的最短距离, 求s点到t点最短距离。 (4) 重复第3步，一直到t点得到标号为止。 例3 求从v1到v7的最短路 解： (1) (2) (3) (5) (4) 例 求从点1到点8的最短路径 23 7 1 8 45 6 6 1 3 4 1 0 52 7 59 3

9、4 6 8 2 (6) 48 23 7 1 8 45 6 6 1 3 10 52 7 59 34 6 2 0 1 (1)解： (2) min d12,d14,d16=min 0+2,0+1,0+3=L14=1 min L12,L16,L14+d42,L14+d47=min 0+2,0+3,1+10,1+2=L12=2 48 23 7 1 8 45 6 6 1 3 10 52 7 59 34 6 2 0 (3) (4) min L16,L12d23,L12+d25,L14+d47=min 0+3,2+6,2+5,1+2=L16=L17=3 23 7 1 8 45 6 6 1 3 4 10 52

10、7 59 34 6 8 2 2 1 0 23 7 1 8 45 6 6 1 3 4 10 52 7 59 34 6 8 2 2 1 0 33 48 23 7 1 8 45 6 6 1 3 10 52 7 59 34 6 2 2 1 0 6 3 3 (5) min L12+d23,L12+d25,L17+d75,L17+d78 =min 2+6,2+5,3+3,3+8=L15=6 min L12+d23,L15+d53,L15+d58,L17+d78 =min 2+6,6+9,6+4,3+8=L13=8 (6) 23 7 1 8 45 6 6 1 3 4 10 52 7 59 34 6 8 2

11、2 1 0 33 6 8 10 23 7 1 8 45 6 6 1 3 4 10 52 7 59 34 6 8 2 2 1 0 33 6 8 min L13+d38,L15+d58,L17+d78=min 8+6,6+4,3+7=L18=10(7) 3-2 求任意两点间最短路的矩阵算法(Ford 算法) 计算步骤： (1) 根据图中任两点i和j的关系，给出直接距离矩阵 ； (2) 构造矩阵 ，令 ，则 表示点i和j 直接到达和有一个中间点时的最短距离。 (3) 再构造矩阵 ，令 ，则 表示点i 和j直接到达，及经过一至三个中间点的最短距离。 (4) 迭代更新k次，生成一个新矩阵 表示网络中任意

12、两点直接到达，及经过一个、两个到 (2k-1)个中间点时的最短距离。 设网络中有p个点， 中k值的大小由下式确定： 或 当 时，停止计算。 即： 例2：求任意两点的最短距离 解： 中的元素 为图中从 i点到j点的最短距离。 6.9 某人购买一辆摩托车，准备在今后4年内使用，他可在第 一年初购一辆新车，连续使用4年，也可于任何一年年末卖 掉，于下一年初换一台新车。已知各年初的新车购置价如表 66，不同役龄车的年使用维护费及年末处理价见表67。 要求确定该人使用摩托车的最优更新策略，使4年内用于购 买、更换及使用维护的总费用最省。 表6-6 表6-7 解：构造有向图，以点表示各年初，弧(i,j)旁

13、数字表示第i年初 买新车用到第j年初(即第j-1年末)卖掉时的总支出费用，记为dij 。则dij等于第i年初的购车费，加上用到第j年初支付的使用维 护费，再减去按役龄年末处理费。 最优方案： (1) 第一年初买新车，年末卖掉再买新车，一直用到第四年末卖掉 (2) 第一年初买新车，用两年后于第二年末卖掉再买新车，用两年 后于第四年末卖掉； (3) 第一年初买新车，年末卖掉后再买新车，用一年后即第二年末 又卖掉再买新车，再用两年后于第四年末卖掉； 最优方案支出总费用为3.7万元。 4 网络的最大流 4-1 网络最大流的有关概念 网络流一般在有向图上讨论 图中规定一个发点s，一个收点t，余为中间点

14、网络上每条弧的最大通行能力，称为该弧的容量，记为 c(vi,vj)或cij ，弧上实际流量记为 fij 节点没有容量限制，流在节点不会存储 满足下列两个条件的流，称为可行流 容量限制条件：0 fij cij 平衡条件： vi A(vi) B(vi) 最大流:满足容量约束条件和平衡条件,使v(f)值为最大的流 4-2 割和流量 将容量网络中的发点和收点分割开，并使 的流 中断的一组弧的集合，称为割(截集)； 一般包含 s 点的节点集合用V表示，包含 t 点的节点集 合用 表示；弧的集合 表示割； 割(截集)的容量：指组成它的集合中各弧的容量之和 即： 4-3 最大流最小割定理 如果在网络的发点和

15、收点之间能找出一条链，在这条链上 所有指向 的弧(称为前向弧，记 )，存在 ；所有 指向 的弧(称后向弧，记 )，存在 ，这样的链称 为增广链。 定理：网络中 的最大流量等于它的最小割集的容量，即 证明：略。 当网络中存在增广链时，找出 仍是一个可行流，流量比 增大了 值 4-4 求网络最大流的标号算法(Ford-Fulkerson标号算法) 算法实质：判断网络中是否有增广链，若有，找出调整 算法的步骤： 第一步：标号过程，找一条增广链 1、给源点 s 标号(0, )， 表示 s 点不限流量 2、找出与已标号节点 i 相邻的所有未标号节点 j，若 (i, j)是前向弧且饱和，则节点 j 不标号； (i, j)是前向弧且未饱和( ) ，则节点 j