第九章图与网络模型

9.图与网络模型•网络社会:计算机通信网络,运输服务网络,能源和物质分派网络,人际关系网络,…•数学上：网络即赋权图，图是描述网络的基本工具•问题：有效地设计规划、管理控制网络系统•本章内容：最小树、最短路、竞赛图等(不讨论较复杂的最大流和最小费用流等)9.图与网络模型•哥尼斯堡七桥问题•数学上：无(有)向图G=(V(G),E(G))，简记G=(V,E)上图例：顶点(节点)集V={A,B,C,D};弧(边)集E={…}“一笔画”(欧拉回路问题)基本概念：相邻，关联，度，路，圈，连通图，权函数9.1最小树9.2最短路与关键路线9.3球队排名与网页排序9.图与网络模型9.1最小树树：不含圈的连通图),,(EVG),,('''EVG.,''EEVV支撑子图:.,''VVGG子图():GG'树的性质：树G=(V,E)|E|=|V|-1若G’是树，则称支撑树网络G=(V,E,W)的所有支撑树中，权(即它所包含的弧上的权的和)最小的称为最小支撑树，简称最小树9.1最小树9.1.1最小树问题的几个例子9.1.2最小树问题的算法9.1.3实例问题的求解本节仅考虑无向网络G=(V,E,W)例1网线铺设问题7栋办公楼，弧上的权为相应的布线成本(万元)应当如何铺设网线？成本是多少？显然这是一个最小树问题问题G=(V,E,W)例2保密通讯问题n=7个国家(代理)，权wij为相应的通讯成本(万元)通讯被对手截获的概率(pij)：如何构建通讯网络？网络可靠性(可靠的概率)有多大？问题弧(a,b)(a,c)(a,d)(b,d)(b,e)(c,d)(c,f)(d,e)(d,f)(e,f)(e,g)(f,g)权0.050.060.020.050.050.020.050.030.040.040.020.01G=(V,E,W)例2保密通讯问题为实现信息共享，所有通讯路径应该构成一棵支撑树T假设每条线路是否被截获是独立的，则通讯可靠性为建模TjiijpR),()1()1(loglog),(ijTjipR以为权，求最小树即可)1log(ijp考虑成本wij：求支撑树T使均最小？TjiijwR),(,logTjiijTjiijpw),(),()1log(例2保密通讯问题双目标：加权法；约束法比值法：单位可靠性成本最小建模？求支撑树T使最小？如何求解？TjiijTjiijrw),(),(M为一个常数，保证对任意支撑树T均满足0),(Tjiijr0)1log(ijp)1log(ijijpMr例3成绩分类问题n=30名学生，两门主课(语文,数学)成绩若依据两门成绩之和分类无法揭示“偏科”构造完全图，以两两之间的距离(如欧氏距离)为权问题102030405060708090100110102030405060708090100110学生123…30语文864040…85数学717060…85计算最小树T分类(去掉T中权值最大的若干条弧)例4公园导游问题n=7个景点，权为相应的道路难度(如坡度等)如何设立提示牌，告知从任一景点p出发到任意另一景点q游览时，应选择哪条路径？路径最大难度为多少？问题可转化为最小树问题最小树问题的算法•避圈法：从空图T开始，每次将G的一条“最小弧”加入T，并保证无圈，直至得到支撑树(或不连通)•破圈法：从T=E开始，每次找出T的一个圈，去掉圈中的最大弧，直至得到支撑树(或不连通)费时G=(V,E,W)Kruskal算法：弧按照权顺序排列，依次加入Prim算法（又称“边割法”）：在割集中找最小弧SjSiEjiSSSSV,|),(],[,最小树问题的算法G=(V,E,W)Kruskal算法Prim算法(从a开始)图的邻接矩阵（代数表示）G=(V,E,W)定义图的邻接矩阵A=(aij)n*n为（n为顶点数）否则,0)(,1Ei,jaij0110000101110011010100110111010100100110010001110A无向图的邻接矩阵是对称矩阵若所有弧的权均不为零，可用弧的权代替A中的“1”用MATLAB求最小树G=(V,E,W)不介绍：符号数学工具箱（SymbolicMathToolbox）只介绍：生物信息学工具箱（BioinformaticsToolbox）输入：邻接矩阵(对大规模稀疏网络，稀疏矩阵输入)演示（例1）：bigraph命令：输入；view命令：显示minspantree命令：求解、算法选择缺省采用Prim法，通过Method参数可改为Kruskal法输出：最小树的邻接矩阵、前趋关系例1(网线铺设问题)：计算结果G=(V,E,W)最小成本14万元T原网络例2(保密通讯问题)：单目标计算结果可靠性最大可靠性0.8586(成本24万元)成本最小成本14万元(可靠性0.7988）例2(保密通讯问题)：双目标处理方法双目标单目标可靠性：0.8326成本：18万元TjiijTjiijrw),(),(*Tjiijijrw),(*0)(以作为弧（i，j）的权，是μ的减函数ijijrw迭代：从某个μ0开始，如果最小树的权大于0，则增大μ；如果权小于0，则减少μ；直到权(近似)为0演示)1log(ijijpMrM取值的影响加权法；约束法习题例2(保密通讯问题)：计算结果可靠性最大可靠性0.8586成本24万元成本最小0.798814万元综合考虑0.832618万元例3(成绩分类问题)的求解MATLAB软件实现(如：分4类)102030405060708090100110102030405060708090100110例4(公园导游问题)的求解于是，求出最小树即可记P是最小树T中连接p,q的唯一路径，P上最大难度弧为(i,j)wij为p-q间任意路径中最大难度“最小者”9.2最短路与关键路线给定有向网络G=(V，E，W)及其中的两个顶点s,t,以s为起点和t为终点、首尾相连的弧组成s-t有向路有向路上所有弧的权的和称为该有向路的权（根据其物理意义，通常也称为费用或者弧长、距离等）所有s-t有向路中权最小的称为s-t最短路，简称最短路无向网络中，可类似定义最短路9.2最短路与关键路线9.2.1最短路问题的几个例子9.2.2最短路问题的求解算法9.2.3实例问题的求解9.2.4项目管理与关键路线法例1设备更新问题问题请帮助张先生制定计划，使5年用车的总费用最少车龄t/年012345维护费ct/万元245912售价st/万元76210张先生欲制定购新车、维护、更新的5年计划节点：6个点(i=1，2，3，4，5，6)表示第i年的开始（i=6即5年计划的结束）弧与权：弧(i,j)（ij）,权wij表示的是第i年开始购买新车到第j-1年结束的用车总费用例1设备更新问题模型wij：购买新车费用+第i年开始到第j-1年结束的维护费-在第j年开始卖出二手车的收入求出最短路即可例2驾驶员雇佣问题问题7名申请人信息如下，公司应该雇佣哪些人上班？某公司必须保证从上午9点到下午5点之间至少有一名驾驶员上班节点：整点时刻弧与权：上班时间及报酬驾驶员1234567上班时间9-19-1112-312-52-51-44-5报酬3018213820229例2驾驶员雇佣问题模型求出最短路即可例3钢管定购和运输（选自2000年全国大学生数学建模竞赛B题）问题450里程(km)订购钢管，经铁路、公路运输，铺设管道1521AAAA1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7管道铁路公路S1~S7钢管厂火车站（沿管道有公路）例3钢管定购和运输简记：1单位钢管=1km管道钢管钢厂产量的下限：500单位钢管钢厂的产量和销价钢厂i1234567产量上限si80080010002000200020003000销价pi(万元)160155155160155150160例3钢管定购和运输准备工作：计算最小运费，相应的运输方式和路线里程(km)≤300301-350351-400401-450451–500运价(万元)2023262932里程(km)501–600601-700701-800801-900901-1000运价(万元)3744505560601=300+3014420+23?1单位钢管的铁路运价1单位钢管的公路运价0.1万元/km（不足整公里部分按整公里计）1000km以上每增加1至100km运价增加5万元最短路问题的求解算法基本假设有向网络G=（V，E，W），不含负有向圈无圈网络Step1拓扑排序：Step2计算uj：起点s到任一顶点j的最短路长（起点s编号为1，如有入弧可直接去掉）Ejiji),(,}.{min,01ijijijswuuuu最短路问题的求解算法正费用网络Dijkstra算法（略）一般网络Bellman-Ford算法：.1,21}},{min,min{,1,,0)()()1(1)1()1(1njnkwuuujwuuijkijikjkjjj临时标号表示从起点s=1到顶点j且所经过的弧数不超过k条时的最短路路长)(kju最后的即为从s到j的最短路路长(永久标号))1(njjuu最短路问题的求解算法一般网络Floyd-Warshall算法(所有点对最短路)临时标号表示不通过k，k+1，…,n节点(i,j除外)时从节点i到节点j的最短路路长)(kiju最后的即为从i到j的最短路路长(永久标号))1(nijijuu比n次调用Bellman-Ford算法省时间.,,1,,},,min{,,,0)()()()1()1()1(nkjiuuuujiwuukkjkikkijkijijijii最短路的MATLAB实现计算G中从节点s到t的最短路：[dist,path,pred]=shortestpath(G,s,t)缺省采用Dijkstra算法（正费用网络）；‘Method’参数选择算法，如Bellman-Ford算法、BFS算法（只计弧的条数）、Acyclic算法（无圈网络）如果省略t，则计算从s到所有其他节点的最短路输出：最短路程dist，路径path，路径上节点前趋pred所有点对最短路：[dist]=allshortestpaths(G)例1设备更新问题求解c=[7,12,21,31,44];n=length(c)+1;A=sparse(1:n-1,2:n,c(1),n,n);fori=3:n-1A=A+sparse(1:n-i+1,i:n,c(i-1),n,n);endG=biograph(A,[],'ShowWeights','on');view(G)[cost,path,pred]=shortestpath(G,1,6)结果(不惟一)：第1年初买车，第2年初卖掉/再买新车，第4年初卖掉，再买新车用到第5年末，总费用31万元例2驾驶员雇佣问题求解邻接矩阵111111111111111A计算结果：最小成本为61个单位路径用时间表示是9-1-4-5雇佣驾驶员1，6，7例3钢管定购和运输采用Floyd-Warshall算法比较方便铁路子网络类似，计算dij2最小运费cij2不考虑装卸费用,计算从每个钢管厂i=1~7到每个节点j=1~15每单位钢管的最小运费cij（运费矩阵）计算任意两个节点i，j之间的最短路长度（距离）dij1查铁路运价表得到最小运费cij1公路子网络假设连续