运筹学 CH6图与网络分析课件.ppt

运筹学 CH6图与网络分析课件.ppt

ID:57181125

大小:1.08 MB

页数:75页

时间:2020-08-02

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

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

1、Chapter6图与网络分析(GraphTheoryandNetworkAnalysis)图与树的基本概念最短路问题网络的最大流网络问题的Excel解法本章主要内容:教学目的与要求【教学目的与要求】了解图和树的基本概念;掌握最短路问题基本理论;了解网络最大流问题;了解MicrosoftExcel求解网络问题的方法。【教学重难点】最短路问题图论是应用非常广泛的运筹学分支,它已经广泛地应用于物理学、控制论、信息论、交通运输、经济管理、电子计算机等各项领域。例如,各种通信线路的架设,输油管道的铺设,铁路或公路交通网络的合理布局等问题。图—引言哥尼斯堡七桥问题哥尼斯

2、堡(现名加里宁格勒)是欧洲一个城市,Pregei河把该城分成两部分,河中有两个小岛,十八世纪时,河两边及小岛之间共有七座桥,当时人们提出这样的问题:有没有办法从某处(如A)出发,经过各桥一次且仅一次最后回到原地呢?欧拉将这个问题抽象成一笔画问题,即能否从某一点开始不重复地一笔画出这个图形,最终回到原点,这就是古典图论中的第一个著名问题。1736年欧拉在他的论文中证明了这是不可能的。图—引例1BDACABCD哈密尔顿(Hamilton)回路哈密尔顿(Hamilton)回路是十九世纪英国数学家哈密顿提出,图形如下,共有20个顶点表示20个城市,要求从某个城市出发

3、沿着棱线寻找一条经过每个城市一次而且仅一次,最后回到原处的周游世界线路(并不要求经过每条边)。图—引例2球队比赛结果有六支球队进行足球比赛,我们分别用点v1…v6表示这六支球队,它们之间的比赛情况,也可以用图反映出来,已知v1队战胜v2队,v2队战胜v3队,v3队战胜v5队,如此等等。这个胜负情况,可以用下图反映出来。v3v1v2v4v6v5图—引例3点:研究对象(城市、球队)。点间连线:对象之间的特定关系。对称关系:用不带箭头的连线表示,称为边。非对称关系:用带箭头的连线表示,称为弧。图是由点和连线组成。无向图(简称图):由点和边构成,记作G=(V,E)(

4、V是点的集合,E是边的集合)连接点vi,vjV的边记作eij=[vi,vj],或者[vj,vi]。有向图:由点和弧所构成的,记作D=(V,A)(V是点的集合,A是弧的集合),一条方向从vi指向vj的弧,记作(vi,vj)。图的基本概念图的基本概念v3e7e4e8e5e6e1e2e3v1v2v4v5端点,关联边,相邻若有边e可表示为e=[vi,vj],称vi和vj是边e的端点,称边e为点vi或vj的关联边。若点vi和vj有公共边,称点vi和vj相邻;若边ei和ej有公共的端点,称边ei和ej相邻。图的基本概念环,多重边,简单图,多重图如果边e的两个端点相重,

5、称该边为环。如右图中边e1为环。如果两个点之间有多于一条的边,称这些边为多重边,如右图中的e4和e5。无环、无多重边的图称为简单图。无环,但允许有多重边的图称为多重图。v3e7e4e8e5e6e1e2e3v1v2v4v5图的基本概念次,奇点,偶点,悬挂点,孤立点以点vi为端点的边的数目称为点vi的次(也叫做度),记作d(vi)。右图中d(v1)=4,d(v3)=5,d(v5)=1。(环算两次)次为奇数的点称作奇点,次为偶数的点称作偶点,次为1的点称为悬挂点,次为0的点称作孤立点。v3e7e4e8e5e6e1e2e3v1v2v4v5图的次:一个图的次等于各点的

6、次之和。图的基本概念定理1任何图中,所有点的次数之和等于所有边数的2倍。定理2任何图中,奇点的个数必为偶数。证明:由于每条边必与两个顶点关联,在计算点的次时,每条边均被计算了两次,所以顶点次数的总和等于边数的2倍。证明:设V1和V2分别为图G中奇点与偶点的集合。由定理1可得:2m为偶数,且偶点的次之和也为偶数,所以必为偶数,即奇点的个数必为偶数。图的基本概念链,圈,连通图图中某些点和边的交替序列,若满足ei=[vi-1,vi],则称此序列为链。v3e7e4e8e5e6e1e2e3v1v2v4v5起点与终点重合的链称为圈。若链中点点不同,则称为初等链。如果每一

7、对顶点之间至少存在一条链,称这样的图为连通图,否则称不连通图。图的基本概念子图,支撑子图图G1=(V1、E1)和图G2=(V2,E2)如果有称G1是G2的一个子图。若有,则称G1是G2的一个支撑子图(生成子图)。v3e7e4e8e5e6e1e2e3v1v2v4v5v3e4e8e5e6v2v4v5v3e7e4e8e6e2e3v1v2v4v5(a)(b)(G图)一笔画问题的简单结论1、一个连通图的顶点都是偶点,没有奇点,则该图可以一笔画出(从任一点出发均可)。(欧拉图)2、一个连通图的顶点恰有两个奇点,其余均为偶点,则从任一奇点出发,可以一笔画出该图,而终点则是

8、另一个奇点。(欧拉道路)3、一个连通图的顶点有两个以

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

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

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