运筹学8图与网络分析

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

1、第八章图与网络分析主要内容：§8.1图的基本概念与基本定理§8.2树和最小支撑树§8.3最短路问题§8.4最小费用流问题§8.5最大流问题§8.6网络计划§8.7中国邮递员问题§8.7指派问题§8.1图的基本概念与基本定理图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论，信息论，工程技术，交通运输，经济管理，电子计算机等各项领域。对于科学研究，市场和社会生活中的许多问题，可以同图论的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。随着科学技术的进步，特别是电子计算机

2、技术的发展，图论的理论获得了更进一步的发展，应用更加广泛。如果将复杂的工程系统和管理问题用图的理论加以描述，可以解决许多工程项目和管理决策的最优问题。因此，图论越来越受到工程技术人员和经营管理人员的重视。关于图的第一篇论文是瑞士数学家欧拉（E.Euler）在1736年发表的解决“哥尼斯堡”七桥难题的论文；德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，（见图8.1a）当地的居民热衷于这样一个问题，一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验者很多，但是都没有成功。为了寻找答案，1736年欧拉将这个问题

3、抽象成图8.1b所示图形的一笔画问题。哥尼斯堡七桥问题图8.1aABCD哥尼斯堡七桥问题可简化为以下图形其中的四个顶点都是奇顶点ABCDCADB图8.1b即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。例8.1图8.2是我国北京、上海、重庆等十四个城市之间的铁路交通图，这里用点表示城市，用点与点之间的线表示城市之间的铁路线。诸如此类还有城市中的

4、市政管道图，民用航空线图等等。石家庄太原北京天津塘沽济南青岛徐州连云港南京上海郑州武汉重庆图8.2例8.2有六支球队进行足球比赛，我们分别用点v1，…，v6表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知v1队战胜v2队，v2队战胜v3队，v3队战胜v5队，如此等等。这个胜负情况，可以用图8.3所示的有向图反映出来图8.3v3v5v2v4v6v1从以上的几个例子可以看出，我们用点和点之间的线所构成的图，反映实际生产和生活中的某些特定对象之间的特定关系。一般来说，通常用点表示研究对象，用点与点之间的线表示研究对象之间的特定关系。由于在一般情况下，图中的相对位置如何，

5、点与点之间线的长短曲直，对于反映研究对象之间的关系，显的并不重要，因此，图论中的图与几何图，工程图等本质上是不同的。综上所述，图论中的图是由点和点与点之间的线所组成的。通常，我们把点与点之间不带箭头的线叫做边，带箭头的线叫做弧。如果一个图是由点和边所构成的，那么，称为无向图，记作G=(V，E)，其中V表示图G的点集合，E表示图G的边集合。连接点vi,vjV的边记作[vi,vj]，或者[vj,vi]。如果一个图是由点和弧所构成的，那么称为它为有向图，记作D=(V,A)，其中V表示有向图D的点集合，A表示有向图D的弧集合。一条方向从vi指向vj的弧，记作(vi,vj)。例如.图

6、8.4是一个无向图G=（V，E），其中V={v1,v2,v3,v4}E={[v1,v2],[v2,v1],[v2,v3],[v3,v4],[v1,v4],[v2,v4],[v3,v3]}v3v2v1v4图8.4图8.5是一个有向图D=（V，A）其中V={v1,v2,v3,v4,v5,v6,v7}A={(v1,v2),(v1,v3),(v3,v2)(v3,v4),(v2,v4),(v4,v5),(v4,v6),(v5,v3),(v5,v4),(v5,v6),(v6,v7)}图8.5v7v5v3v4v2v6v1下面介绍一些常用的名词：一个图G或有向图D中的点数,记作P(G)或P(

7、D),简记作P,边数或者弧数,记作q(G)或者q(D),简记作q。如果边[vi,vj]E,那么称vi,vj是边的端点，或者vi,vj是相邻的。如果一个图G中，一条边的两个端点是相同的,那么称为这条边是环，如图8.4中的边[v3,v3]是环。如果两个端点之间有两条以上的边，那么称为它们为多重边，如图8.4中的边[v1,v2],[v2,v1]。一个无环，无多重边的图称为简单图，一个无环，有多重边的图称为多重图。以点v为端点的边的个数称为点v的度，记作d(v),如图8—4中d(v1)=3，d(v2)=4,d