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

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

1、运筹学图与网络GraphandNetwork图的基本概念与基本定理树和最小支撑树最短路问题本章内容重点引言图论是专门研究图的理论的一门数学分支，属于离散数学范畴，与运筹学有交叉。它有200多年历史，大体可划分为三个阶段：第一阶段是从十八世纪中叶到十九世纪中叶，处于萌芽阶段，多数问题围游戏而产生，最有代表性的工作是所谓的Euler七桥问题，即一笔画问题。例1：哥尼斯堡七桥问题哥尼斯堡（现名加里宁格勒）是欧洲一个城市，Pregei河把该城分成两部分，河中有两个小岛，十八世纪时，河两边及小岛之间共有七座桥，当时人们提出这样的问题：有没有办法从某

2、处（如A）出发，经过各桥一次且仅一次最后回到原地呢？ABCDACBD数学家Euler在1736年巧妙地给出了这个问题的答案，并因此奠定了图论的基础。他把问题转化为从任意一点出发，能不能经过各边一次且仅一次，最后返回该点。这就是著名的Euler问题。第二阶段是从十九世纪中叶到二十世纪中叶，这时，图论问题大量出现，如地图染色的四色问题、Hamilton问题等。直到1936年D.柯尼希发表了图论的第一本专著《有限与无限图理论》，这时图论才成为一门学科例2：哈密顿（Hamilton）回路是十九世纪英国数学家哈密顿提出，给出一个正12面体图形，共有

3、20个顶点表示20个城市，要求从某个城市出发沿着棱线寻找一条经过每个城市一次而且仅一次，最后回到原处的周游世界线路（并不要求经过每条边）。第三阶段是二十世纪中叶以后，由生产管理、军事、交通、运输、计算机网络等方面提出实际问题，以及大型计算机使大规模问题的求解成为可能，特别是以Ford和Fulkerson建立的网络流理论，与线性规划、动态规划等优化理论和方法相互渗透，促进了图论对实际问题的应用。现代图论应用在很多方面：如物流网络、社会网络、计算机网络、交通网络等等人际关系网络：六度分离，smallworld1967年哈佛大学美国社会心理学家

4、米尔格伦（StanleyMilgram）提出SNS网站:socialnetworkservice蛋白质网络刊登在Nature杂志首页互联网网络复杂网络一、图与网络的基本知识（一）、图与网络的基本概念EADCB1、一个图是由点和连线组成。（连线可带箭头，也可不带，前者叫弧，后者叫边）一个图是由点集和中元素的无序对的一个集合构成的二元组，记为G=(V，E)，其中V中的元素叫做顶点，V表示图G的点集合；E中的元素叫做边，E表示图G的边集合。v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10图12、如果一个图是由点和边所构成的，则

5、称其为无向图，记作G=(V，E)3、如果一个图是由点和弧所构成的，那么称它为有向图，记作D=(V,E)，其中V表示有向图D的点集合，E表示有向图D的弧集合。一条方向从vi指向vj的弧，记作(vi,vj)。v4v6v1v2v3v5V={v1,v2,v3,v4,v5,v6}，E={(v1,v3),(v2,v1),(v2,v3),(v2,v5),(v3,v5),(v4,v5),(v2,v4),(v5,v4),(v5,v6)}图24、一条边的两个端点是相同的,那么称为这条边是环。5、如果两个端点之间有两条以上的边，那么称为它们为多重边。6、一个无

6、环，无多重边的图称为简单图，一个无环，有多重边的图称为多重图。7、每一对顶点间都有边相连的无向简单图称为完全图。v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10度为零的点称为孤立点，度为1的点称为悬挂点。悬挂点的关联边称为悬挂边。度为奇数的点称为奇点，度为偶数的点称为偶点。8、以点v为端点的边的个数称为点v的度（次），记作。图中d(v1)=4，d(v6)=4（环计两度）定理1所有顶点度数之和等于所有边数的2倍。定理2在任一图中，奇点的个数必为偶数。所有顶点的入次之和等于所有顶点的出次之和。有向图中，以vi为始点的边数称为

7、点vi的出次，用表示；以vi为终点的边数称为点vi的入次，用表示；vi点的出次和入次之和就是该点的次。9、设G1=（V1,E1），G2=（V2,E2）如果V2V1,E2E1称G2是G1的子图；如果V2=V1,E2E1称G2是G1的部分图或支撑子图。v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8(b)子图v1v2v3v4v5v6v7e1e6e7e9e10e11(c)支撑子图在实际应用中，给定一个图G=（V，E）或有向图D=（V，A），在V中指定两个点，一个称为

8、始点（或发点），记作v1，一个称为终点（或收点），记作vn，其余的点称为中间点。10、由两两相邻的点及其相关联的边构成的点边序列称为链。如:v0，e1，v1，e2，v2，e3，v3,…,vn-