《运筹学课件 第八章 图与网络分析.ppt》由会员分享，可在线阅读，更多相关《运筹学课件 第八章 图与网络分析.ppt（67页珍藏版）》请在三一文库上搜索。
1、引言 图论是专门研究图的理论的一门数学分支，属于离散数学范畴，与运筹学有交叉，它有200多年历史，大体可划分为三个阶段：第一阶段是从十八世纪中叶到十九世纪中叶，处于萌芽阶段，多数问题围游戏而产生，最有代表性的工作是所谓的Euler七桥问题，即一笔画问题。,第八章 图与网络分析,第二阶段是从十九世纪中叶到二十世纪中叶，这时，图论问题大量出现，如Hamilton问题，地图染色的四色问题以及可平面性问题等，这时，也出现用图解决实际问题，如Cayley把树应用于化学领域，Kirchhoff用树去研究电网络等.,第三阶段是二十世纪中叶以后，由生产管理、军事、交通、运输、计算机网络等方面提出实际问题，以及
2、大型计算机使大规模问题的求解成为可能，特别是以Ford和Fulkerson建立的网络流理论，与线性规划、动态规划等优化理论和方法相互渗透，促进了图论对实际问题的应用。,例：哥尼斯堡七桥问题 哥尼斯堡（现名加里宁格勒）是欧洲一个城市，Pregei河把该城分成两部分，河中有两个小岛，十八世纪时，河两边及小岛之间共有七座桥，当时人们提出这样的问题：有没有办法从某处（如A）出发，经过各桥一次且仅一次最后回到原地呢？,A,B,C,D,最后，数学家Euler在1736年巧妙地给出了这个问题的答案，并因此奠定了图论的基础，Euler把A、B、C、D四块陆地分别收缩成四个顶点，把桥表示成连接对应顶点之间的边，
3、问题转化为从任意一点出发，能不能经过各边一次且仅一次，最后返回该点。这就是著名的Euler问题。,A,C,B,D,例：哈密顿（Hamilton）回路是十九世纪英国数学家哈密顿提出，给出一个正12面体图形，共有20个顶点表示20个城市，要求从某个城市出发沿着棱线寻找一条经过每个城市一次而且仅一次，最后回到原处的周游世界线路（并不要求经过每条边）。,图的基本概念 图论是专门研究图的理论的一门数学分支，主要研究点和线之间的 几何关系。,一、图与网络的基本概念 1、图及其分类 定义1：（图）一个图由点集V和V中的元素无序对的一个集合，记为 G=（V，E） 其中：V= （ v1， v2，. vm）是m个
4、顶点集合； E= （ e1， e2，. en） 是n条边集合。 当V和E为有限集合时，G为有限图。 2个点u,v属于V，如果边(u,v)属于E， u,v相邻； u,v为边(u,v)的端点。 具有公共端点u的两条边，称为点u的关联边。,第一节 图与网络的基本知识,如果任一边(u,v)属于E且端点无序，无向边；图G为无向图。 如果任一边(u,v)属于E且端点有序，有向边；图G为有向图 m(G)= E ，表示图G的边数； n(G)= V ，表示图G的点数；,环（自回路）：一条边的两个端点如果相同。 两个点之间多于一条边的，多重边。 定义2：不含环和多重边的图，简单图。 含有多重边的图，多重图。 有向
5、图中的两点之间有不同方向的两条边，不是多重边。,简单图,定义3：每一对顶点间都有边相连的无向简单图，完全图。 有向完全图：指每一对顶点间有且仅有一条有向边的简单图。 定义4:图G=(V,E)的点集V可以分为2个非空子集X,Y，使得E中每条边的两个端点必有一个端点属于X，另一个端点属于Y，G为二部图（偶图），有时记为： G=(X,Y,E),V1,V4,V3,V2,X,Y,2、顶点的次 定义5：以点v为端点的边的个数称为点v的次，记作d(v), 如次为零的点称为弧立点； 次为1的点称为悬挂点。悬挂点的边称为悬挂边。 次为奇数的点称为奇点，次为偶数的点称为偶点。 偶点：d(v)=偶数； 奇点：d(v
6、)=奇数；,v1,v3,v2,v4,v6,v5,e1,e3,e5,e6,e4,e8,e7,e2,V= （ v1， v2，. v6） E= （ e1， e2，. e8） （e1）= （v1， v2） （e2）= （v1， v2） （e7）= （v3， v5） （e8）= （v4， v4） (e8)= (v4， v4),称为自回路(环)； v6是孤立点，v5为悬挂点，e7为悬挂边，顶点v3的次为4，顶点v4的次为4。,定理1 在一个图中，所有顶点次的和等于边的两倍。 定理2 在任意一个图中，次为奇数的顶点必为偶数个。 定义6：有向图中，以vi为始点的边数称为点vi的出次，d+(vi); 以vi为终
7、点的边数称为点vi的入次，d-(vi); 所有顶点的入次之和=所有顶点的出次之和；,3、子图 定义：设G=（V，E）和G1=（V1，E1）。 如果V1 V， E1 E则称G1为G的子图； 如果G1 =（ V1，E1 ）是G=（V，E）子图，并且V1 = V，则称G1为G的生成子图；,v1,v5,v4,v2,v3,e1,e8,e7,e6,e5,e4,e3,e2,v1,v5,v4,v2,e1,e5,e3,（a）的子图,v1,v5,v4,v2,v3,e8,e6,e5,e2,（a）的生成子图,二、连通图 定义8:如果图中的某些点、边可以排列成点和边的交错序列(v0 ,e1 ,v1 ,e2 ,v2，e3
8、 ,v3 ,vn-1 , en ， vn ） ，ei=(vi-1,vi)，则称此为一条链。 由两两相邻的点及其相关联边构成的点边序列。 初等链：链中无重复的点和边； 定义9：无向图中，如一条链中起点和终点重合，则称此链为圈。 初等圈：圈中无重复的点和边； 有向图中，当链（圈）上的边方向相同时，为道路（回路）。,道路 道路 回路,链、初等链、初等圈,道路、回路,连通图：图中任意两点之间均至少有一条通路，否则称为不连通图。,v1,v5,v4,v2,v3,e1,e8,e7,e6,e5,e4,e3,e2,有向图,v1,v5,v4,v2,v3,e1,e8,e7,e6,e5,e4,e3,e2,有向图,v1
9、,v5,v4,v2,v3,e1,e8,e7,e6,e5,e4,e3,e2,有向图,v1,v5,v4,v2,v3,e1,e8,e7,e6,e5,e4,e3,e2,有向图,v1,v5,v4,v2,v3,e1,e8,e7,e6,e5,e4,e3,e2,有向图,v1,v5,v4,v2,v3,e1,e8,e7,e6,e5,e4,e3,e2,有向图,v1,v5,v4,v2,v3,e1,e8,e7,e6,e5,e4,e3,e2,链,v1,v5,v4,v2,e1,e7,e6,e3,v1,v5,v4,v2,e1,e7,e6,e3,v1,v5,v4,v2,e1,e7,e6,e3,v1,v5,v4,v2,e1,e7
10、,e6,e3,圈,三、图的矩阵表示 一个图非常直观，但是不容易计算，特别不容易在计算机上进行计算，一个有效的解决办法是将图表示成矩阵形式，通常采用的矩阵是邻接矩阵、边长邻接矩阵、弧长矩阵和关联矩阵。,1、邻接矩阵 邻接矩阵A表示图G的顶点之间的邻接关系，它是一个nxn的矩阵，如果两个顶点之间有边相联时，记为1，否则为0。,定义12：对于G=(V,E)，构造矩阵A=(aij)nxn aij= 1, （vi,vj） E 0 矩阵A为邻接矩阵。,V1,V3,V5,V6,V4,V2,v1 v2 v3 v4 v5 v6,2、权矩阵 在图的各边上一个数量指标，具体表示这条边的权（距离，单价，通过能力等），
11、以边长代替邻接矩阵中的元素得到边长邻接矩阵。 定义11：赋权图G=(V,E)，其边（vi,vj）有权wij,构造矩阵A=(aij)nxn aij= wij, （vi,vj） E 0 矩阵A为权矩阵。,v1,v2,v5,v4,v3,9,2,4,3,8,6,7,4,5,v1 v2 v3 v4 v5,四、欧拉回路与中国邮政问题 1、欧拉回路与道路 定义13：连通图G，如果存在一条道路，经过每边一次且仅一次，则称这条路为欧拉道路； 如果存在一条回路，经过每边一次且仅一次，则称这条路为欧拉回路； 具有欧拉回路的图为欧拉图。 定理3：无向连接图G是欧拉图，当且仅当G中无奇 点。 推论1：无向连接图G为欧拉
12、图，当且仅当G的边集可划为若干个初等回路。 推论2：无向连接图G为欧拉道路，当且仅当G恰好有2个奇点。,定理4：连通有向图G是欧拉图，当且仅当它每个奇点的出次等于入次。 2、中国邮路问题 一个邮递员，从邮局出发，走遍所有街道后回到邮局，如何安排，使其总的路程最短？ 图论：给定一个连通图，每边有非负权，要求一条回路过每边至少一次，且满足总权最小。 定理5：已知图G*=G+E1无奇点，则L(E1)= l(e)最小的充要条件 （1）每条边最多重复一次； （2）对图G中每个初等圈，重复边的长度和不超过圈长的1/2；,例：求解网络的中国邮路问题,第一步：确定初始可行方案 先检查图中是否有奇点，如果无奇点
13、，为欧拉图；如果有奇点，图中的奇点的个数比为偶数个，所以可以两两配对，构造二重边。图中有4个奇点，v2,v4,v6,v8,配对 v2-v4,v6-v8，构造二重边。重复边 的总长： 2l23+ 2l36+ l69+ l98+ l23+ 2l87+ 2l74+ l41+ l12=51,第二步：调整可行方案，使重复边最多为一次 重复边 的总长： l69+ l98+ l41+ l12=21,第三步：检查每个初等圈是否 定理条件2，如果不满足，进行 调整，直至满足为止。 圈v1v2v5v4v1总长度24，重复边14，14/21大于1/2，调整（v2,v5），（v5,v4）代替（v1,v2），(v1,v
14、4),圈v1v2v5v4v1总长度24， 重复边6+4=10,重复边 的总长： l69+ l98+ l45+ l52=17 再检查圈v2v3v6v9v8v5v2总长=24,重复边 的长度13，继续调整,再次调整的重复边 的总长：=15，满足条件要求。 图中任一欧拉回路为最优邮递回路。 方法：简单；但要检查每一个初等圈。,总结:图的基本概念,G=（V，E）,子图,矩阵表示,含元素的个数,点的次,边,特殊的图,点边关系,简单图,多重图,连通图,树,生成子图,G=(V,E),矩阵表示 A 邻接矩阵 B 权矩阵,边e=(u,v),关联边,自回路,多重边 平行边,简单图,多重图,0 1 奇数 偶数,点边关系,点边关系,生成树,有向图,道路、回路,1.思考题 子图与生成子图的区别是什么？ 2.讨论题 中国邮路问题的解题步骤？,小结: 1.图的基本知识。 2.图的矩阵表示。 3.欧拉道路与欧拉回路。,