运筹学第五章-图与网络分析课件.ppt

《运筹学第五章-图与网络分析课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5章图与网络分析第５章　图与网络分析５.１基本概念５.２最小支撑树问题５.３最短路问题５.４最大流问题5.１基本概念1.图、子图与简单图图：由节点和线组成的图形．记为：G=(V,E)V={v1,v2,…,vm}—节点集,表示研究对象.E={e1,e2,…,en}—边集，表示研究对象之间的关系.e1e2e3e5e6e4e7v3v2v1v4e1e2e3e5e6e4e7v3v2v1v4e2e3e5e6e4v3v2v1v4图Ｇ图Ｇ１子图：图的一部分，记为Ｇ１．多重边：两节点之间有多于一条边。环：首尾相接的边简单图：无环、无多重边的图。2.有向图与无向图有向图：有方向的图。无向图

2、：无方向的图。e1V2V1e2V3v1ev23.关联与相邻关联(边与节点的关系):若e是v1、v2两节点间的边，记e=[v1，v2]，称v1、v2与e关联。相邻（边与边、节点与节点的关系）：点v1与v2有公共边，称节点v1与v2相邻；边e1与e2有公共节点，称边e1与e2相邻。圈封闭的链称为圈如：μ={(1,2),(2,4),(3,4),(1,3}链:由图G中的某些相连的边构成的图形（首尾不能相接），称为图G中的一条链。如：μ={(1,2),(3,2),(3,4)}4.链、圈与连通图42314231连通图任意两个节点之间至少有一条链的图称为连通图42315.网络图给图中的节

3、点和边赋以具体的含义和权数（如距离、时间、费用、容量等），则称这样的连通图为网络图。423150702045典例:会议日程安排某单位要在今后的三天内召开6个会议,每天上下午各安排一个会议，参加会议的领导如下∶会议A:朱、马、牛、姬、江、姚会议B:朱、杨、张、江会议C:马、姬、侯、王、姚会议D:朱、姬、张会议E:杨、侯、王会议F:刘、杨、王、江、姚每位领导每天最多只参加一个会议。会议A要安排在第一天上午,会议F安排在第三天下午，会议B要安排在任何一天的下午。试根据上述要求排出一个会议日程表，使各位领导都能参加相应的会议ABCDEF会议日程安排如下:上午下午第一天会议AE第二天

4、会议CB第三天会议DF解:用节点表示会议，若两个会议能安排在一天，则用连线连接。5.2最小支撑树问题树：无圈的连通图，记为T。树的性质243512435124351如果树T有m个节点，则边的个数为m-1。树中任意两个节点间有且只有一条链。在树中任意去掉一条边，则不连通。图的支撑树图G1和G2的节点相同，但图G1边的集合包含于G2边的集合，且G1是树图，则图G1是G2的支撑树。一个图的支撑树不是唯一的。图G1图G2最小支撑树树枝总长最短的支撑树。特点：各节点都连通且线路总长最短．最小支撑树的求法1破圈法2避圈法5.2.1求解最小支撑树问题的破圈法方法：去边破圈的过程。步骤：1

5、）在给定的赋权的连通图上任找一个圈。2）在所找的圈中去掉一条权数最大的边。3）若所余下的图已不含圈，则计算结束，余下的图即为最小支撑树，否则返回1）。例１：用破圈法求右图的最小支撑树。V4V2V3V174581V4V2V3V1V1V4V2V3V4V2V3V1V4V2V3V1总权数=3+4+1=85.2.2求解最小支撑树的避圈法方法：选边的过程。步骤：1）从网络中任意选一点vi，找出与vi相关联的权最小的边[vi,vj]，得第二个顶点vj。2）把顶点集V分为互补的两部分A,Ā，其中：A：与已选边相关联的点集Ā：不与已选边相关联的点集3)考虑所有这样的边[vi,vj]，其中vi

6、∈A,vj∈Ā,挑选其中权最小的。4）重复3），直至全部顶点均属于A即可。例２：用避圈法求图的最小支撑树。V4V2V3V174581①任选点v1，挑与之相关联的权最小的边（v1,v4）.②A={v1,v4},Ā={v2,v3}从边（v1,v2）,（v1,v3）,（v4,v2）,（v4,v3）中选权最小的边（v1,v2）。V4V2V3V174581③A={v1,v2,v4},Ā={v3}从边（v1,v3）,（v2,v3）,（v4,v3）中选权最小的边（v2,v3）。④A={v1,v2,v3，v4}网络的生成树和线性规划的关系网络的一个生成树对应于线性规划的一个基生成树上的边对

7、应于线性规划的基变量生成树的弦对应于线性规划的非基变量生成树的变换对应于线性规划单纯形法的进基和离基变换71425673734243562412破圈法举例避圈法举例1425673734243562412例３校园局域网问题某大学准备把所属７个学院办公室的计算机联网．这个网络的可能联通的途径如图所示．边上权数为这条边的长度，单位为百米．试设计一个网络联通７个学院办公室，并使总长度为最短．v1v4v5v3v7v6v2513724843103v1v4v5v3v7v6v2137233权和＝１９例４电话线网架设问题某６个城市之