运筹学第五章图与网络分析.
《运筹学第五章图与网络分析.》由会员分享，可在线阅读，更多相关《运筹学第五章图与网络分析.（76页珍藏版）》请在文档大全上搜索。
1、第章图与网络分析第章图与网络分析u.基本概念基本概念u.最小支撑树问题最小支撑树问题u.最短路问题最短路问题u.最大流问题最大流问题5. 基本概念基本概念1.1.图图、子图、子图与简单图与简单图u图：图：由节点和线组成的图形由节点和线组成的图形 记为：记为： G = ( V, E ) G = ( V, E ) V=v V=v1 1,v,v2 2,v vm m节点集节点集, ,表示研究对象表示研究对象. . E=eE=e1 1,e,e2 2,e,en n边集，表示研究对象之边集，表示研究对象之间的关系间的关系. .e1e2e3e5e6e4e7v3v2v1v411111( ,),GV EVV EE
2、其中。e1e2e3e5e6e4e7v3v2v1v4e2e3e5e6e4v3v2v1v4图图u子图：子图：图的一部分，记为图的一部分，记为u多重边多重边：两节点之间有多于一条边。：两节点之间有多于一条边。u环：环：首尾相接的边首尾相接的边u简单图：简单图：无环、无多重边的图。无环、无多重边的图。2.有向图与无向图有向图与无向图v有向图有向图：有方向的图。：有方向的图。v无向图无向图：无方向的图。：无方向的图。 e1 V2 V1 e2 V3 v1 e v23.关联与相邻关联与相邻v关联关联(边与节点的关系边与节点的关系):若若e是是v1、v2两节点间两节点间 的边，记的边，记e=v1，v2 ，称称
3、v1、v2 与与e关联关联。v相邻相邻（边与边、节点与节点的关系）：（边与边、节点与节点的关系）： 点点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连通图连通图 任意两个节点之
4、间至任意两个节点之间至少有一条链的图称为少有一条链的图称为连连通图通图42315.网络图网络图 给图中的节点和边赋以给图中的节点和边赋以具体的含义和权数（如距离具体的含义和权数（如距离、时间、费用、容量等），、时间、费用、容量等），则称这样的连通图为则称这样的连通图为网络图网络图。4231 50 70 20 45v典例: 会议日程安排某单位要在今后的三天内召开6个会议,每天上下午各安排一个会议，参加会议的领导如下会议A: 朱、马、牛、姬、江、姚会议B: 朱、杨、张、江会议C: 马、姬、侯、王、姚会议D: 朱、姬、张会议E: 杨、侯、王会议F: 刘、杨、王、江、姚每位领导每天最多只参加一个会议。
5、会议A要安排在第一天上午,会议F安排在第三天下午，会议B要安排在任何一天的下午。试根据上述要求排出一个会议日程表，使各位领导都能参加相应的会议ABCDEF会议日程安排如下: 上午 下午第一天 会议A E 第二天 会议C B第三天 会议D F 解: 用节点表示会议，若两个会议能安排在一天， 则用连线连接。5.2 最小支撑树问题最小支撑树问题C1C2C3C4根根叶叶v树：无圈的连通图，记为树：无圈的连通图，记为T。v树的性质树的性质243512435124351如果树如果树T有有m个节点，则个节点，则边的个数为边的个数为m-1。 树中任意两个节点间有树中任意两个节点间有且只有一条链且只有一条链。
6、在树中任意去掉一条边，在树中任意去掉一条边，则不连通则不连通。v图的支撑树图的支撑树图图G1和和G2 的节点相同，但图的节点相同，但图G1边的集合边的集合包包含于含于G2边的集合，且边的集合，且 G1是树图，则是树图，则 图图G1是是G2 的支撑树。的支撑树。一个图的支撑树不是唯一的。一个图的支撑树不是唯一的。图 G1图 G2v最小支撑树 树枝总长最短的支撑树。特点：各节点都连通且线路总长最短v最小支撑树的求法1 破圈法2 避圈法5.2.1 求解最小支撑树问题的破圈法求解最小支撑树问题的破圈法v方法：去边破圈的过程。方法：去边破圈的过程。v步骤步骤：1）在给定的赋权的连通图上任找）在给定的赋权
7、的连通图上任找 一一 个圈。个圈。 2）在所找的圈中去掉一条权数最）在所找的圈中去掉一条权数最 大的边。大的边。 3）若所余下的图已不含圈，则计）若所余下的图已不含圈，则计 算结束，余下的图即为最小支撑算结束，余下的图即为最小支撑 树，否则返回树，否则返回 1）。）。v例：用破圈法求右图例：用破圈法求右图 的最小支撑树。的最小支撑树。V4V2V3V13 7 4 5 8 1V4V2V3V1V1V4V2V3V4V2V3V1V4V2V3V1总权数总权数=3+4+1=85.2.2 求解最小支撑树的避圈法求解最小支撑树的避圈法v方法：选边的过程。方法：选边的过程。v步骤：步骤：1）从网络中任意选一点）从
8、网络中任意选一点vi，找出找出与与vi相关联的权最小的边相关联的权最小的边vi,vj，得第二个得第二个顶点顶点vj。 2）把顶点集）把顶点集V分为互补的两部分分为互补的两部分A,，其中：其中： A：与已选边相关联的点集与已选边相关联的点集 ：不与已选边相关联的点集不与已选边相关联的点集 3) 考虑所有这样的边考虑所有这样的边vi,vj，其中其中viA,vj,挑选其中权最小的。挑选其中权最小的。 4）重复）重复3），直至全部顶点均属于），直至全部顶点均属于A即即可。可。v例：用避圈法求图的最小例：用避圈法求图的最小 支撑树。支撑树。V4V2V3V13 7 4 5 8 1任选点任选点v1，挑与之相
9、关挑与之相关联的权最小的边（联的权最小的边（ v1,v4）.A= v1,v4,=v2,v3 从边（从边（ v1,v2）,（ v1,v3）, （ v4,v2）, （ v4,v3） 中选权最小的边（中选权最小的边（ v1,v2）。）。V4V2V3V13 7 4 5 8 1A= v1,v2 ,v4,=v3 从边（从边（ v1,v3）, （ v2,v3）, （ v4,v3） 中选中选权最小的边（权最小的边（ v2,v3）。）。 A= v1,v2 , v3， v4l网络的生成树和线性规划的关系网络的生成树和线性规划的关系网络的一个生成树对应于线性规划的网络的一个生成树对应于线性规划的一个基一个基生成树上
10、的边对应于线性规划的基变生成树上的边对应于线性规划的基变量量生成树的弦对应于线性规划的非基变生成树的弦对应于线性规划的非基变量量生成树的变换对应于线性规划单纯形生成树的变换对应于线性规划单纯形法的进基和离基变换法的进基和离基变换71425673734243562412破圈法举例避圈法举例1425673734243562412例例 校园局域网问题校园局域网问题某大学准备把所属个学院办公室的计某大学准备把所属个学院办公室的计算机联网这个网络的可能联通的途径算机联网这个网络的可能联通的途径如图所示边上权数为这条边的长度，如图所示边上权数为这条边的长度，单位为百米试设计一个网络联通个单位为百米试设计一
11、个网络联通个学院办公室，并使总长度为最短学院办公室，并使总长度为最短v1v4v5v3v7v6v2513724843103v1v4v5v3v7v6v2137233权和权和例例 电话线网架设问题电话线网架设问题某个城市之间的道路网如图所示要某个城市之间的道路网如图所示要求沿着已知长度的道路联结个城市的求沿着已知长度的道路联结个城市的电话线网，并使电话线的总长度最短电话线网，并使电话线的总长度最短v1v4v2v6v5v3617524453v1v4v2v6v5v312453权和权和5.3 最短路问题最短路问题问题：求网络中一定点到其它点的最短路。问题：求网络中一定点到其它点的最短路。5.3.1 最短路
