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

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

1、第六章图与网络分析7/30/20211图论是运筹学中有着广泛应用的一个分支。管理科学、计算机科学、信息论、控制论、物理、化学、生物学、心理学等不同领域内的许多问题都可以描述为图论模型来解决。随着科学技术的发展以及电子计算机的出现和应用，20世纪50年代，图论的理论得到了进一步的发展。将宠大复杂的工程和管理问题用图描述，可以解决很多工程设计和管理决策的最优化问题。欧拉(E.Euler)在1736年发表图论方面的第一篇论文解决了著名的哥尼斯堡七桥问题，被公认为是图论的创始人。7/30/2021218世纪的哥尼斯堡城中流过一条河(普雷格尔河)，河上有七座桥连结着河的两

2、岸和河中的两个小岛，如下图所示。7/30/202137/30/20214当时，那里的人们热衷于这样的间题：一个散步者能否走过七座桥，且每座桥只走过一次，最后回到出发点。这就是著名的“七桥”难题。人们做了许多试验，但没有一个人成功。7/30/20215欧拉把这个试验化为下图所示的一个图论问题。它用结点A，B，C，D分别表示对应的陆地，用边来表示连接陆地的桥。这样哥尼斯堡七桥问题就转化为下图中寻求一条包含每边一次的回路问题。7/30/20216欧拉证明七桥问题无解，因为图中的每个点都只与奇数条线相关联，不可能将这个图不重复地一笔画成。从而解决了这一难题，它的抽象与论

3、证方法开创了图论科学的研究。随着科学技术的发展以及电子计算机的出现与广泛应用，二十世纪五十年代，图论的理论得到进一步发展。将庞大复杂的工程系统和管理问题用图描述，可以解决很多工程设计和管理决策的最优化问题。例如，完成工程任务的时间最少，距离最短，费用最省等等。图论受到数学、工程技术及经营管理等各个方面越来越广泛的重视。7/30/20217一、图的基本概念在生产和日常生活中经常碰到各种各样的图：公路或铁路交通图、管网图、电网图、通讯联络图等..运筹学中所研究的图（graph）是上述各类图的抽象概括，它表明一些研究对象和这些对象之间的相互联系。如交通图是表明一些城镇

4、及城镇之间的道路沟通情况；管网图是表明供应源、用户、中间加压站之间管网的联系情况等。7/30/20218例1、下图是我国北京、上海等十个城市间的铁路交通图，反映了这十个城市间的铁路分布情况。这里用点代表城市，用点和点之间的联线代表这两个城市之间的铁路线。7/30/20219北京郑州武汉天津济南青岛徐州连云港南京上海7/30/202110例2有六支球队进行足球比赛，我们分别用点v1，…，v6表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知v1队战胜v2队，v2队战胜v3队，v3队战胜v5队，如此等等。这个胜负情况，可以用下图所示的有

5、向图反映出来7/30/202111v3v5v2v4v6v17/30/202112综上所述，一个图是由一些点及一些点之间的联线(不带箭头或带箭头)所组成的。为了区别起见，把两点之间的不带箭头的联线称为边，带箭头的联线称为弧。如果用点表示研究的对象，用边表示这些对象之间的联系，则图G可以定义为点与边的集合，记作式V是点的集合，E是边的集合。7/30/202113注意，上面定义的图G区别于几何学中的图。几何学中，图中点的位置、线的长度和斜率等都十分重要，而这里只关心图中有多少个点以及哪些点之间有线相连。如果给图中的点和边以具体的含义和权数（如距离、费用、容量等）。把这

6、样的图称为网络图，记作N。图和网络分析的方法已广泛应用于物理、化学、控制论、信息论、计算机科学和经济管理等各领域。7/30/202114一个图可以用几何图形表示，用圆圈表示点（又称顶点或节点）并用小写字母v表示，用线表示边并用e表示。对每条边可用它所连接的点表示。7/30/202115e1v1e3v3e8v5e7v4e6e2e4e5v27/30/202116如记作若，称是边的端点，反之，称边为点或的关联边。若点与同一条边关联，称点相邻；若边和具有公共的端点，称和相邻7/30/202117如果边的两个端点相重，则称该边为环。如上图中边为环。如果两个点之间多于一条边

7、，称具有多重边，如。对无环、无多重边的图称为简单图。与某一个点相关联的边的数目称为点的次（也叫度），记作上图中次为奇数的点称作奇点，次为偶数的点称作偶点，次为0的点称作孤立点，如。7/30/202118图中有些点和边的交替顺序，若其中各边互不相同，且对任意和均相邻，称为链。上图中是一条链，也是一条链。对起点与终点重合的链称作圈。7/30/202119若在一个图中，如果每一对顶点之间至少存在一条链，称这样的图为连通图，否则称为不连通图。对要研究的问题确定具体对象及这些对象间的性质联系，并用图的形式表示出来，这就是对研究的问题建立图的模型。用建立图的模型的方法往往能

8、帮助我们解决一些用其他方