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

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

ID:58669250

大小:1.52 MB

页数:125页

时间:2020-10-05

管理运筹学6 图与网络分析ppt课件.ppt_第1页
管理运筹学6 图与网络分析ppt课件.ppt_第2页
管理运筹学6 图与网络分析ppt课件.ppt_第3页
管理运筹学6 图与网络分析ppt课件.ppt_第4页
管理运筹学6 图与网络分析ppt课件.ppt_第5页
资源描述:

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

1、运筹学(OperationsResearch)经济学核心课程Chapter6图与网络分析(GraphTheoryandNetworkAnalysis)图的基本概念与模型树与图的最小树最短路问题网络的最大流本章主要内容:近代图论的历史可追溯到18世纪的七桥问题—穿过Königsberg城的七座桥,要求每座桥通过一次且仅通过一次。这就是著名的“哥尼斯堡7桥”难题。Euler1736年证明了不可能存在这样的路线。图的基本概念与模型Königsberg桥对应的图图的基本概念与模型图论中图是由点和边构成,可以反映一些对象之间的关系。一般情况下图中点的

2、相对位置如何、点与点之间联线的长短曲直,对于反映对象之间的关系并不是重要的。图的定义:若用点表示研究的对象,用边表示这些对象之间的联系,则图G可以定义为点和边的集合,记作:其中:V——点集E——边集※图G区别于几何学中的图。这里只关心图中有多少个点以及哪些点之间有连线。图的基本概念与模型(v1)赵(v2)钱孙(v3)李(v4)周(v5)吴(v6)陈(v7)e2e1e3e4e5(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈e2e1e3e4e5可见图论中的图与几何图、工程图是不一样的。例如:在一个人群中,对相互认识这个关

3、系我们可以用图来表示。图的基本概念与模型定义:图中的点用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相邻。图的基本概念与模型环,多重边,简单图如果边e的两个端点相重,称该边为环。如右图中边e1为环。如果两个点之间多于一条,称为多重

4、边,如右图中的e4和e5,对无环、无多重边的图称作简单图。v3e7e4e8e5e6e1e2e3v1v2v4v5图的基本概念与模型次,奇点,偶点,孤立点与某一个点vi相关联的边的数目称为点vi的次(也叫做度),记作d(vi)。右图中d(v1)=4,d(v3)=5,d(v5)=1。次为奇数的点称作奇点,次为偶数的点称作偶点,次为1的点称为悬挂点,次为0的点称作孤立点。v3e7e4e8e5e6e1e2e3v1v2v4v5图的次:一个图的次等于各点的次之和。图的基本概念与模型链,圈,连通图图中某些点和边的交替序列,若其中各边互不相同,且对任意vi,

5、t-1和vit均相邻称为链。用μ表示:v3e7e4e8e5e6e1e2e3v1v2v4v5起点与终点重合的链称作圈。如果每一对顶点之间至少存在一条链,称这样的图为连通图,否则称图不连通。图的基本概念与模型二部图(偶图)图G=(V,E)的点集V可以分为两个非空子集X,Y,集X∪Y=V,X∩Y=Ø,使得同一集合中任意两个顶点均不相邻,称这样的图为偶图。v1v3v5v2v4v6v1v2v3v4v1v4v2v3(a)(b)(c)(a)明显为二部图,(b)也是二部图,但不明显,改画为(c)时可以清楚看出。图的基本概念与模型子图,部分图(支撑子图)图G

6、1={V1、E1}和图G2={V2,E2}如果有称G1是G2的一个子图。若有,则称G1是G2的一个部分图(支撑子图)。v3e7e4e8e5e6e1e2e3v1v2v4v5v3e4e8e5e6v2v4v5v3e7e4e8e6e2e3v1v2v4v5(a)(b)(G图)图的基本概念与模型网络(赋权图)设图G=(V,E),对G的每一条边(vi,vj)相应赋予数量指标wij,wij称为边(vi,vj)的权,赋予权的图G称为网络(或赋权图)。权可以代表距离、费用、通过能力(容量)等等。端点无序的赋权图称为无向网络,端点有序的赋权图称为有向网络。①②③

7、④⑤⑥910201571419256图的基本概念与模型出次与入次有向图中,以vi为始点的边数称为点vi的出次,用d+(vi)表示;以vi为终点的边数称为点vi的入次,用表示d-(vi);vi点的出次和入次之和就是该点的次。※有向图中,所有顶点的入次之和等于所有顶点的出次之和。图的基本概念与模型图的模型应用例6.1有甲,乙,丙,丁,戊,己6名运动员报名参加A,B,C,D,E,F6个项目的比赛。下表中打√的是各运动员报告参加的比赛项目。问6个项目的比赛顺序应如何安排,做到每名运动员都不连续地参加两项比赛。ABCDEF甲√√乙√√√丙√√丁√√戊

8、√√√己√√√图的基本概念与模型解:用图来建模。把比赛项目作为研究对象,用点表示。如果2个项目有同一名运动员参加,在代表这两个项目的点之间连一条线,可得下图。ABCDEF在图中找

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。