6-图及网络(运筹学)

《6-图及网络(运筹学)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1第六章网络优化模型图的基本概念最小树问题最短路问题最大流问题218世纪，哥尼斯堡城中有一条普雷格尔河，河上有七座桥将河中的两个小岛与河岸连接起来。人们提出了这样的问题：一个散步者能否从某地出发，走遍七桥且每座桥恰好经过一次，最后回到原地？陆地A陆地B岛D岛CA·D··B·C1736年瑞士数学家欧拉将两岸和小岛抽象为四个点，将桥抽象为七条边，此问题归结为一笔画问题。3例1（6个球队之间的赛事关系，P131）4例2在五个城市之间架设电话线，要求任两个城市之间都可以相互通话（允许通过其他城市），并且电话线的根数最少。v1v5v2v3v4用v1,v2,v3,v4,v5

2、代表五个城市,如果在某两个城市之间架设电话线,则在相应的两点之间联一条边,这样一个电话线网就可以用一个图来表示。显然,这个图必须是连通的,而且是不含圈的连通图。如左图所示。5例3某工厂的组织机构如下图所示厂长行政办公室生产办公室生产计划科技术科设计组工艺组供销科财务科行政科车间铸造工段锻压工段二车间三车间四车间该厂的组织机构图就是一个树。6例4树图倒置的树，根(root)在上，叶(leaf)在下7例5（石油流向管网示意图，P131）此为一个有向图81图的基本概念无向图：G={V，E}顶点或节点：v图5.3子图与部分图边：e=eij=[vi,vj]=[vj,vi]

3、有向图：G={V，A}弧：a=aij=[vi,vj]≠[vj,vi]树图:T(V，E)，没有任何圈的连通图最小支撑树（最小树）：能够把所有节点连接起来，且树枝总长最小的树图。连通图G：如果图G中任何两点间至少有一条链链：连接两个顶点的一个序列；例1中{a,b,c}，{a,b,e,d}等圈：两个端点重合的链，例1中{a,b,c,a}，{a,b,d,a}等路：从节点vi到vj的弧和节点组成的一个序列回路（圈）：始点和终点重合的路9图的引入例6：在一个人群中，相互认识这个关系我们可以用图来表示。右图就是一个表示这种关系的图。我们用G=(V，E)来表示图，其中V为图中点

4、的集合，E为边的集合。本例中，V={v1,v2,…v7}；E={e1,e2,…,e5}10如果我们把上面的例子中“相互认识”的关系改成“认识”的关系，那么只用两点的联线就很难刻间他们之间的关系了。例如，周认识赵．而赵却不认识周。这时我们引入一个带箭头的联线，称之为弧。这就是有向图。右图就是一个反映这七人“认识“关系的有向图。有向图记为D＝(V，A)，其中V为图D的点集合，A为图D的弧集合。本例中，V={v1,v2,…,v7};D={a1,a2,…,a15}无向图是一种特殊的有向图，无向图的边实际就是等价于两条反向的弧。112.最小树的计算方法一避圈法开始选一条权

5、最小的边，以后每一步中，总从未被选取的边中选一条权最小的边，并使之与已选取的边不构成圈。v1v2v3v4v5v6651572344这就得到了该图的一个最小树。12方法二破圈法任取一个圈，从圈中去掉一条权最大的边。在余下的图中，重复这个步骤，一直到一个不含圈的图为止，这时的图便是最小树。v1v2v3v4v5v6651572344这就得到了该图的一个最小树。13例7：某公园要为主要景点铺设光缆。为减少成本，要让这个光缆线路在连接所有景点的条件下，费用尽可能的少。下图每个点A-E是一个主要景点，S和T分别是入口和出口。线段边上的数字表示在这两点之间铺设光缆所要花费的成

6、本，问应该如何铺设？公园问题的路径系统14分析显然，此问题是一个最小树的生成问题。用避圈法来做。软件实现在WinQSB中模块NetworkModeling的“MinimalSpanningTree”实现结果与此完全相同.最小树：如图中红线所示。公园各景观间的最小电话安装15例8：求最小树16方法1（避圈法）将图中的边按权的大小从小到大排列先取边(v1，v2)，再依次加入不形成圈的各边，就可以得最小树。总权数为11。17方法2（破圈法）将图中的各圈中权重最大的边去掉，直到没有圈为止。18用WinQSB求最小树19例9某大学准备对其所属的7个学院办公室计算机联网，这

7、个网络的可能联通的途径如下图所示，图中v1,v2,...,v7表示7个学院办公室，图中的边为可能联网的途径，边上所赋的权数为这条路线的长度，单位为百米。请设计一个网络能联通7个学院办公室，并使总的线路长度为最短。线路总长度1+2+3+3+3+7=19。203.最短路问题实际例子：公园的入口到各个景点，各个景点之间，以及各景点到出口处的道路都有很多条线路，需要事先确定从公园入口、各个景点到出口处的最短线路，作为游客的最佳游玩线路。最短路问题是对一个赋权的有向图D(其赋权根据具体问题的要求可以是路程的长度，成本的花费等等)中的指定的两个点s和t找到一条从s到t的路，

8、使得这条路上所有弧的权数