欢迎来到天天文库
浏览记录
ID:56414657
大小:2.81 MB
页数:137页
时间:2020-06-17
《运筹学(第6章 图与网络分析).ppt》由会员上传分享,免费在线阅读,更多相关内容在PPT专区-天天文库。
1、运筹学基础及应用(OperationsResearch)主讲:杨启明图的基本概念与模型1树图和图的最小部分树2最短路问题3第6章图与网络分析邮路问题4网络的最大流5近代图论的历史可追溯到18世纪的七桥问题—穿过Königsberg城的七座桥,要求每座桥通过一次且仅通过一次。这就是著名的“哥尼斯堡7桥”难题。Euler1736年证明了不可能存在这样的路线。Königsberg桥对应的图6.1图的基本概念与模型岛北区东区南区图论中图是由点和边构成,可以反映一些对象之间的关系。一般情况下图中点的相对位置如何、点与点之间联线的长短曲直,对于反映对象之间的关系并不是重要的。(v1)赵(v
2、2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈e2e1e3e4e5例如:在一个人群中,对相互认识这个关系我们可以用图来表示,图6-1就是一个表示这种关系的图。图的定义:若用点表示研究的对象,用边表示这些对象之间的联系,则图G可以定义为点和边的集合,记作:其中:V——点集E——边集当然图论不仅仅是要描述对象之间关系,还要研究特定关系之间的内在规律,一般情况下图中点的相对位置如何、点与点之间联线的长短曲直,对于反映对象之间的关系并不是重要的,如对赵陈等七人的相互认识关系我们也可以用图6-2来表示,可见图论中的图与几何图、工程图是不一样的。(v1)赵(v2)钱孙(v3)李(
3、v4)周(v5)吴(v6)陈(v7)e2e1e3e4e5图6-2图与网络的基本概念图与网络的基本概念a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈图6-3如果我们把上面例子中的“相互认识”关系改为“认识”的关系,那么只用两点之间的联线就很难刻画他们之间的关系了,这是我们引入一个带箭头的联线,称为弧。图6-3就是一个反映这七人“认识”关系的图。相互认识用两条反向的弧表示。图的基本概念与模型定义:图中的点用v表示,边用e表示。对每条边可用它所连接的点表示,记作:e1=[v1,v1];e2
4、=[v1,v2];v3e7e4e8e5e6e1e2e3v1v2v4v5端点,关联边,相邻若有边e可表示为e=[vi,vj],称vi和vj是边e的端点,反之称边e为点vi或vj的关联边。若点vi、vj与同一条边关联,称点vi和vj相邻;若边ei和ej具有公共的端点,称边ei和ej相邻。图的基本概念与模型环,多重边,简单图如果边e的两个端点相重,称该边为环。如右图中边e1为环。如果两个点之间多于一条,称为多重边,如右图中的e4和e5,对无环、无多重边的图称作简单图。v3e7e4e8e5e6e1e2e3v1v2v4v5图的基本概念与模型次,奇点,偶点,孤立点与某一个点vi相关联的边的
5、数目称为点vi的次(也叫做度),记作d(vi)。右图中d(v1)=4,d(v3)=5,d(v5)=1。次为奇数的点称作奇点,次为偶数的点称作偶点,次为1的点称为悬挂点,次为0的点称作孤立点。v3e7e4e8e5e6e1e2e3v1v2v4v5图的次:一个图的次等于各点的次之和。图的基本概念与模型链,圈,连通图图中某些点和边的交替序列,若其中各边互不相同,且对任意vi,t-1和vit均相邻称为链。用μ表示:v3e7e4e8e5e6e1e2e3v1v2v4v5起点与终点重合的链称作圈。如果每一对顶点之间至少存在一条链,称这样的图为连通图,否则称图不连通。图的基本概念与模型二部图(偶
6、图)图G=(V,E)的点集V可以分为两各非空子集X,Y,集X∪Y=V,X∩Y=Ø,使得同一集合中任意两个顶点均不相邻,称这样的图为偶图。v1v3v5v2v4v6v1v2v3v4v1v4v2v3(a)(b)(c)(a)明显为二部图,(b)也是二部图,但不明显,改画为(c)时可以清楚看出。图的基本概念与模型子图,部分图(支撑子图)图G1={V1、E1}和图G2={V2,E2}如果有称G1是G2的一个子图。v3e7e4e8e5e6e1e2e3v1v2v4v5v3e4e8e5e6v2v4v5v3e7e4e8e6e2e3v1v2v4v5(a)(b)(G图)若有,则称G1是G2的一个部分图
7、(支撑子图)。图的基本概念与模型网络(赋权图)设图G=(V,E),对G的每一条边(vi,vj)相应赋予数量指标wij,wij称为边(vi,vj)的权,赋予权的图G称为网络(或赋权图)。权可以代表距离、费用、通过能力(容量)等等。①②③④⑤⑥910201571419256端点无序的赋权图称为无向网络端点有序的赋权图称为有向网络。图的基本概念与模型出次与入次有向图中,以vi为始点的边数称为点vi的出次,用d+(vi)表示;以vi为终点的边数称为点vi的入次,用表示d-(vi);vi点的出次和入次
此文档下载收益归作者所有