第6章：图与网络分析ppt课件.ppt

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

1、第7章   图与网络分析图的基本概念与模型树图和图的最小部分树最短路问题网络最大流问题图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论，信息论，工程技术，交通运输，经济管理，电子计算机等各项领域。对于科学研究，市场和社会生活中的许多问题，可以同图论的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。引言1736年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文，解决了著名的哥尼斯堡七座桥问题。即一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。如图1

2、所示。引例1欧拉将这个问题抽象成一笔画问题。即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。引例2左图是我国北京、上海、重庆等十四个城市之间的铁路交通图，这里用点表示城市，用点与点之间的线表示城市之间的铁路线。诸如此类还有城市中的市政管道图，民用航空线图等等。连云港武汉南京徐州上海北京塘沽青岛济南天津郑州有六支球队进行足球比赛，我们分别用点v1…v6

3、表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知v1队战胜v2队，v2队战胜v3队，v3队战胜v5队，如此等等。这个胜负情况，可以用下图所示的有向图反映出来。引例3v3v1v2v4v6v5图的基本概念与模型点：研究对象（车站、国家、球队）；点间连线：对象之间的特定关系（陆地间有桥、铁路线、两球队比赛及结果)。对称关系：桥、道路、边界；用不带箭头的连线表示，称为边。非对称关系：甲队胜乙队，用带箭头的连线表示，称为弧。图：点及边（或弧）组成。注意：一般情况下，图中的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显的并不重要，因此，图论中的图与几何图，工程

4、图等本质上不同。对称关系非对称关系无向图：图由点和边所构成的，记作G={V,E}(V是点的集合，E是边的集合)连接点vi,vjV的边记作eij={vi,vj}，或者[vj,vi]。有向图：图是由点和弧所构成的，记作D={V,A}(V是点的集合，A是弧的集合)，一条方向从vi指向vj的弧，记作(vi,vj)。图的相关概念网络图：给图中的点和边赋予具体的含义和权数，如距离，费用，容量等，记作N.图的相关概念若边eij=[vi,vj]∈E，称vi，vj是eij的端点，也称vi，vj是相邻的。称eij是点vi（及点vj）的关联边。若两条边有一个公共的端点，则称这两条边相邻。vivjevi

5、，vj相邻e与vi，vj关联vie1vjvke2点与边关联点与点相邻边与边相邻若某条边两个端点相同，称这条边为环。若两点之间有多于一条的边，称这些边为多重边。无环、无多重边的图称为简单图。无环、但允许有多重边的图称为多重图。v1e1e2e3v2v3e5e4v4v5注：无特别声明我们今后讨论的图都是简单图图的相关概念图G中以点v为端点的边的数目，称为v在G中的次(度），记为d（v）。d(v1)=2d(v2)=3d(v3)=4d(v4)=1次为1的点为悬挂点，悬挂点的关联边称为悬挂边，次为零的点称为孤立点。v1e1e2e3v2v3e5e4v4v5次为奇数的点称为奇点，否则称为偶点。图的

6、相关概念给定图G=（V，E），若图G’=（V’，E’），其中V’V，E’E，则称G’是G的子图。给定图G=（V，E），若图G’=（V，E’），其中E’E，则称G’是G的一个支撑子图（部分图）。点全部保留（a）（b）子图（c）部分图子图与部分图（支撑子图）图的连通性链：设图G=（V，E）中有一个点、边交替序列{v1,e1,v2,…vn-1,en-1,vn}，若ei=(vi,vi+1)，即这(n-1)条边把n个顶点串连起来，我们称这个交替序列为图G中的一条链，而称点v1,vn为该链的两个端点。对于简单图链也可以仅用点的序列来表示。如果一条链的两个端点是同一个点，则称它为闭链或圈；

7、如果一条链的各边均不相同，则称此链为简单链；更若一条链的各点、各边均不相同，则称该链为初等链。v1v3v5e1e2v7v8e7v2v4v6e3e4e5e6e8e9简单链：1=（v2，v1，v3，v6，v4，v3，v5）初等链：2=（v2，v1，v3，v5）图的连通性最短链:网络中链上权值的和称为链的长度，以点v1,vn为端点的诸链中长度最短的链称为这两点的最短链。连通图：如果图G=（V，E）中的任意两点都是其某一条链的两个端点，则称图G是连通图，否则，称图G是不连