第七章 图与网络分析1

《第七章 图与网络分析1》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、管理运筹学--管理科学方法李军桂林电子科技大学商学院第7章图与网络分析内容提要Subtitle第一节图论的概念第二节最小树问题第三节最短路问题第四节网络最大流第五节最小费用流2OR:SMOR:SM哥尼斯堡，原属波兰，现属俄罗斯，名为加里宁格勒3OR:SMOR:SM18世纪，哥尼斯堡城（当时东普鲁士柯尼斯堡，今日俄罗斯加里宁格勒）中有一条普雷格尔河，河上有七座桥将河中的两个小岛与河岸连接起来。茶余饭后，人们提出了这样的问题：一个散步者能否从某地出发，走遍七座桥且每座桥恰好经过一次，最后回到原地？4第7章网络分析1736年瑞士数学家欧拉将两岸和小岛抽象为四个点，将桥抽象为七条边

2、，此问题归结为一笔画问题。陆地AA岛CDC岛DB陆地B欧拉回答的根据是：若图是连通的，且图中奇点(和奇数条边相关联的点)的数目为0或2时，则图能“一笔画”。奇点的数目为零时，则图中任一点即是“一笔画”的起点又是终点。奇点的数目为2时，则两点中任一点为“一笔画”的起点，而另一点为终点。前图中奇点数目为4，不满足“一笔画”规则，因此是无解的。哥尼斯堡七桥问题，用图论的方法得到了简捷的证明，所以欧拉被人们公认为图论的创始人，人们称他为“图论之父”。5OR:SMOR:SM第一节图论的概念一、图的内涵1、图的定义•图论的图与一般几何图形或代数函数图形是完全不同的图论中的图:由一些点

3、和连接点的线所组成的“图形”点和线的位置是任意的线的曲直、长短与实际无关，代表的只是点与点之间的相互关系•例：表示苏州v1、杭州v2、上海v3、南京v4仓储网点之间的物流运输线路关系e5ev··v·5·v24v24ee31ee3e·e44v6ee161e2·vv·e1e32·v33e2e5·e1·e4·e6·v1v2v3v46OR:SMOR:SM第一节图论的概念一、图的内涵2、图的分类不带箭头的连线称为“边”，如公路运输线路；带箭头的连线称为“弧”，如供排水的管道运输线路。1、无向图2、有向图由点和边的集合所构成由点和弧的集合所构成•链：无向网络中，前后相继点和边•

4、路径：有向网络图中，前后相继并且的交替序列称为一条链。方向一致的点弧序列称为一条路径。•圈：闭合的链称为一个圈。•回路：闭合的路径称为一个回路。7OR:SMOR:SM第一节图论的概念图与网络的基本概念图及其分类3、简单图4、多重图无环，且任意两点间有环，或有多重边不多于一条边8OR:SMOR:SM第一节图论的概念图与网络的基本概念母图、子图、支撑子图母图子图支撑子图（生成子图）9OR:SMOR:SM第一节图论的概念图与网络的基本概念网络（赋权图）在实际问题中，只用图来描述所研究的对象间的关系往往是不够的，而常常还需要考虑与点或边有关的某些数量指标（即“权”），其可以代表诸如

5、距离、费用、通过能力（容量）等等。网络——点或边带有某种数量指标的图24243322663737115510OR:SMOR:SM第一节图论的概念图与网络的基本概念连通图在众多各类图中有一类在实际应用中占有重要地位的图连通图——在图中，任意两点间至少存在着一条链。连通图不连通图11OR:SMOR:SM第二节最小树问题树及其性质无圈且连通的无向图称为树。例如，企业的组织结构，文件的目录管理等都可以用一个树状图来表示。性质：①树中任两点之间必有且只有一条链；②树中去掉任一条边，则成为不连通图；③树中不相邻两顶点之间添一条边，则得到一个圈；④顶点个数n与边的个数n的关系：n=n－1

6、。veev12OR:SMOR:SM第二节最小树问题支撑树：如果图G（V，E）的支撑子图T=（V，E/）是树，则称T为G的支撑树。权数总和为最小的那棵支撑树，称为最小树。w(T)wij求解方法：①破圈法；②避圈法[vi,vj]T例：一家企业分别要在6间办公室铺设网线接入口，网线的可行走线方式如下图所示，如何铺设网线才能使网线总长为最短？vv2458635v16v6268v3v4最短网线总长度为最小树权之和2+3+4+6+6=2113OR:SMOR:SM第二节最小树问题方法一：破圈法：任取一个圈，从圈中去掉一条权最大的边。在余下的图中，重复这个步骤，一直到一个不含圈

7、的图为止，这时的图便是最小树。vv355647v13v1654v2v24这就得到了该图的一个最小支撑树。142011-03-25OR:SM14OR:SM第二节最小树问题方法二：避圈法：开始选一条权最小的边（也可从一点开始），以后每一步中，总从未被选取的边中选一条权最小的边，并使之与已选取的边不构成圈。vv355647v13v1654v2v24这就得到了该图的一个最小支撑树。152011-03-25OR:SM15OR:SM第三节最短路问题－－ShortestRoute(Path)Problems一、最短路问题路权：