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

《运筹学 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)＝４,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、一个连通图的顶点有两个以