管理运筹学图与网络分析.ppt

运筹学( Operations Research )经济学核心课程经济学核心课程Chapter6 Chapter6 图与网络分析图与网络分析( Graph Theory work Analysis )( Graph Theory work Analysis )图的基本概念与模型树与图的最小树最短路问题网络的最大流本章主要内容:本章主要内容:Page 3近代图论的历史可追溯到18世纪的七桥问题—穿过K?nigsberg城的七座桥,要求每座桥通过一次且仅通过一次。这就是著名的“哥尼斯堡7 桥”难题。Euler1736年证明了不可能存在这样的路线。图的基本概念与模型图的基本概念与模型KK??nigsbergnigsberg桥对应的图桥对应的图Page 4图的基本概念与模型图的基本概念与模型图论中图是由点和边构成,可以反映一些对象之间的关系。一般情况下图中点的相对位置如何、点与点之间联线的长短曲直,对于反映对象之间的关系并不是重要的。图的定义:图的定义:若用点表示研究的对象,用边表示这些对象之间的联系,则图G可以定义为点和边的集合,记作:},{EVG?其中: V——点集E——边集※图G区别于几何学中的图。这里只关心图中有多少个点以及哪些点之间有连线。Page 5图的基本概念与模型图的基本概念与模型(v1)赵(v2)钱孙(v3)李(v4)周(v5)吴(v6)陈(v7)e2e1e3e4e5(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈e2e1e3e4e5可见图论中的图与几何图、工程图是不一样的。例如:在一个人群中,对相互认识这个关系我们可以用图来表示。Page 6图的基本概念与模型图的基本概念与模型定义: 图中的点用v表示,边用e表示。对每条边可用它所连接的点表示,记作:e1=[v1,v1]; e2=[v1,v2]; v3e7e4e8e5e6e1e2e3v1v2v4v5端点,关联边,相邻若有边e可表示为e=[vi,vj],称vi和vj是边e的端点,反之称边e为点vi或vj的关联边。若点vi、vj与同一条边关联,称点vi和vj相邻;若边ei和ej具有公共的端点,称边ei和ej相邻。Page 7图的基本概念与模型图的基本概念与模型环, 多重边, 简单图如果边e的两个端点相重,称该边为环。如右图中边e1为环。如果两个点之间多于一条,称为多重边,如右图中的e4和e5,对无环、无多重边的图称作简单图。v3e7e4e8e5e6e1e2e3v1v2v4v5Page 8图的基本概念与模型图的基本概念与模型次,奇点,偶点,孤立点与某一个点vi相关联的边的数目称为点vi的次(也叫做度),记作d(vi)。右图中d(v1)=4,d(v3)=5,d(v5)=1。次为奇数的点称作奇点,次为偶数的点称作偶点,次为1的点称为悬挂点,次为0的点称作孤立点。v3e7e4e8e5e6e1e2e3v1v2v4v5图的次:一个图的次等于各点的次之和。Page 9图的基本概念与模型图的基本概念与模型链,圈,连通图图中某些点和边的交替序列,若其中各边互不相同,且对任意vi,t-1和vit均相邻称为链。用μ表示:v3e7e4e8e5e6e1e2e3v1v2v4v5},,,,,{110kkvevev???起点与终点重合的链称作圈。如果每一对顶点之间至少存在一条链,称这样的图为连通图,否则称图不连通。Page 10图的基本概念与模型图的基本概念与模型二部图(偶图)图G=(V,E)的点集V可以分为两个非空子集X,Y,集X∪Y=V,X∩Y=?,使得同一集合中任意两个顶点均不相邻,称这样的图为偶图。v1v3v5v2v4v6v1v2v3v4v1v4v2v3(a)(b)(c)(a)明显为二部图,(b)也是二部图,但不明显,改画为(c)时可以清楚看出。