图论与网络分析课件

《图论与网络分析课件》由会员分享，可在线阅读，更多相关《图论与网络分析课件（50页珍藏版）》请在金锄头文库上搜索。

1、图论与网络分析 （Graph Theory and Network Analysis）,教学要求：,了解图论的基本概念，理论和方法以及应用,掌握最小树以及最短路问题等模型及其基本算法。,掌握欧拉道路、回路的判断和构造方法,18世纪，哥尼斯堡城中有一条普雷格尔河，河上有七座桥将河中的两个小岛与河岸连接起来。人们提出了这样的问题：一个散步者能否从某地出发，走遍七桥且每座桥恰好经过一次，最后回到原地？,陆地A,陆地B,岛D,岛C,A ,D , B, C,1736年瑞士数学家欧拉将两岸和小岛抽象为四个点，将桥抽象为七条边，此问题归结为一笔画问题。,图论起源,第一节 图论的概念,图论的图与一般几何图形或

2、函数图形是完全不同的 图论中的图:由一些点和连接点的线所组成的“图形” 点和线的位置是任意的 线的曲直、长短与实际无关，代表的只是点与点之间的相互关系,无向图的基本概念,G=(V,E),V=viG的顶点集合,E=ek G的边集合， 且ek=（vi,vj）为无序二元组, 表示ek连接vi,vj,n(G)=|V|=nG的顶点数 m(G)=|E|=mG的边数,顶点相邻,两顶点之间有一条边，顶点为该边的端点，边与其端点关联。,边相邻,e1,e2,e3,e4,e5,e6,e7,两边与同一顶点关联，即两边有共同的端点。,环,两端点重合为一点的边，如e1,多重边,两点之间多于一条边，如e6，e7,简单图,不

3、含环和多重边的图，去掉e1和e7.（不特指都是简单图）,完全图,每对顶点之间都有边相连 的无向简单图，n个顶点 的无向完全图记为Kn,次,与顶点v相关联的边数，即 以v为顶点的边数记为d(v), 环记2次。d(1)=4.,奇点，偶点,次为奇数的点为奇点，次为 偶数的点为偶点。,次为1的点为悬挂点。 若4，5之间有一条边，则5 为悬挂点。,孤立点,次为0的点为孤立点，5为孤 立点。,Kn有边 条,悬挂点,无向图的基本概念,二部图：图G=(V,E)，顶点集合V可分为两个非空子集X,Y，知XY=V，XY=，E中每条边的两个端点，一个在X中，一个在Y中，则称G为二部图，记为G=（X,Y,E）,有向图的

4、基本概念,G=(V,E),V=vi：G的顶点集合,E=ek：G的有向边(弧)集合， 且ek=（vi,vj）为有序二元组, 表示弧ek从vi（始点）指向vj（终点）,环,有向图中，始点、终点重合的弧为环，如e1,多重边,始点和终点都相同的弧为 多重边，如e6，e7非多 重边。,简单有向图,不含环和多重边的有向图，去掉e1,有向完全图,以任意点为始点，另一点为终点都有一条弧的简单有向图，n个顶点的有向完全图有弧n(n-1)条,出次，入次，次,以顶点v为始点的弧数为v的出次，记 为 ；以顶点v为终点的弧数为v的入次，记为 ；顶点v的出次与入次之和为点v的次。,网络（赋权图）,在无向图的边（或有向图的

5、弧）上标上实数，称为该边（或弧）的权，无向（有向）图连同它边上的权称为一个网络赋权图，简称网络。（无向网络，有向网络）,子图,道路，回路,连通图,点i和j点是连通的：i,j之间存在一条链 G是连通的：G中任意两点都是连通的 不连通图可以分为若干连通子图，每个称为原图的分图。,关联矩阵,图的矩阵表示,关联矩阵示例,右图的关联矩阵是 右图的关联矩阵是,e1,e2,e4,e7,e6,e5,e8,e3,e1,e2,e3,e4,e5,邻接矩阵,邻接矩阵示例,右图的邻接矩阵是 右图的邻接矩阵是,主要结论,图论基本概念应用,例1：证明在9座工厂之间，不可能每座工厂只与其他3座工厂有业务联系，也不可能只有4座

6、工厂与偶数个工厂有业务联系。,将9座工厂看做9个点，他们有联系用边相连，若每座工厂 只与其他3座工厂有业务联系，则每个点的次都为3，从而 总次为27，非偶数，与总次为边的2倍矛盾。从而得证。,若只有4座工厂与偶数个工厂有业务联系，则其余5座与奇 数个工厂有业务联系，从而总次为 4*偶+5*奇=奇数 非偶数，矛盾。从而得证。,例2：6个人围成圆圈就座，每个人恰好只与相邻者不认识，是否可以重新就座，使每个人都与邻座认识？,将6个人看做6个点，相互认识用边表示,要求重排之后每个人与邻座认识只需找到一个序列，该序列中前后两个点是相邻的就可以了。如 1-3-5-2-6-4-1,例3 甲、乙、丙、丁、戊5

7、个运动员报名参加A,B,C,D,E，F六个项目比赛，报名情况见下表（打*表示各运动员报名参加的比赛项目）。问如何安排项目，使每名运动员不连续参加两项比赛？,将6个项目看做6个点，同一个人参加的项目之间有边,要求安排项目，每名运动员不连续参加两项比赛，只需找到一个遍历点的序列，该序列中前后两个点是不相邻的就可以了。如 A-C-D-E-F-B,练习 10个研究生参加6门课考试，每个研究生考试课程见下表，要求上下午各排一门课，每人每天最多考一门，且A必须第一天上午，F必须最后考，B要安排在下午考，试给出一个考试安排表。,AECBDF,欧拉回路,连通图G中若存在一条道路，经每边一次且仅一次，则该道路为

8、欧拉道路 若存在一条回路，经每边一次且仅一次，该回路为欧拉回路。 有欧拉回路的图称为欧拉图。,结论：,Th1：无向连通图G为欧拉图充要条件是G中无奇点。 Th2：无向连通图G为欧拉图充要条件是G的边集可分为若干初等回路。 Th3：无相连通图G为欧拉道路充要条件是G中恰有2个奇点。 Th4：连通有向图G为欧拉图充要条件是他每个顶点的出次等于入次。 Th5：连通有向图G为欧拉道路充要条件是这个图中除了两个顶点之外，其余每个顶点出次等于入次，且这两顶点中，一个顶点入次比出次多1，另一个出次比入次多1.,一个散步者能否从某地出发，走遍七桥且每座桥恰好经过一次，最后回到原地？ 即是否存在欧拉回路？,陆地

9、A,陆地B,岛D,岛C,A ,D , B, C,每点都是奇点，所以不是欧拉图，即不存在欧拉回路。,如果存在欧拉回路，如何找到该回路？,欧拉回路的构造方法,从G中任意点v1出发找到一个初等回路c1，再从图中去掉c1，在剩余的图中再找初等回路c2，一直找到图中所有的边都被包含在这些初等回路中为止，最后把这些回路连续起来即得该图的欧拉回路。,下面两个图是否可以一笔画出？,V3,V1,V2,V6,V5,V4,1,2,3,4,5,6,7,8,9,10,(2，e23,3,e34,4,e41,1,e12,2,e27,7,e75,5,e56,6,e67,7,e79,9,e910, 10,e108,8,e89,

10、9,e93,3,e310,10,e104,4,e48,8,e86,6,e61,1,e15,5),第二节 最小树问题,一、树的定义与树的特征,定义 连通且不含圈的无向图称为树常用T表示.,树中的边称为树枝. 树中次为1的顶点称为树叶，次大于1的点为分枝点。,定理 设T是具有n个顶点的图，则下述命题等价：,1) T是树（ T无圈且连通）；,2) T无圈，且有n-1条边；,3) T连通，且有n-1条边；,4) T无圈，但添加任一条新边恰好产生一个圈;,5) T连通，且删去一条边就不连通了,6) T中任意两顶点间有唯一一条路.,二、图的生成树,定义 若T是包含图G的全部顶点的子图,它又是树,则称T是G

11、的生成树. 图G中不在生成树的边叫做弦.,定理 图G=(V,E)有生成树的充要条件是图G是连,通的.,找图中生成树的方法,可分为两种：避圈法和破圈法,A 避圈法 : 深探法和广探法,B 破圈法,A 避圈法,这种方法就是在已给的图G中，每步选出一条边使它与已选边不构成圈，直到选够n-1条边为止. 这种方法可称为“避圈法”或“加边法”,在避圈法中，按照边的选法不同，找图中生成树的方法可分为两种：深探法和广探法.,a) 深探法,若这样的边的另一端均已有标号，就退到标号为,步骤如下：,i) 在点集V中任取一点u,ii) 若某点v已得标号，检,端是否均已标号.,若有边(v,w)之w未标号,则给,w代v，

12、重复ii).,i-1的r点,以r代v,重复ii),直到全部点得到标号为止.,给以标号0.,查一端点为v的各边，另一,w以标号i+1，记下边(v,w).令,例用深探法求出下图的一棵生成树,0,1,2,3,4,5,6,7,8,9,10,11,12,13,13,a) 深探法,0,1,2,3,4,5,6,7,8,9,10,11,12,例用深探法求出下图的一棵生成树,3,b)广探法,步骤如下：,i) 在点集V中任取一点u,ii) 令所有标号i的点集为,是否均已标号. 对所有未标,号之点均标以i+1,记下这些,iii) 对标号i+1的点重复步,步骤ii)，直到全部点得到,给u以标号0.,Vi,检查Vi,V

13、Vi中的边端点,边.,例用广探法求出下图的一棵生成树,1,0,1,2,2,1,3,2,1,2,2,3,4,标号为止.,3,b)广探法,例用广探法求出下图的一棵生成树,1,0,1,2,2,1,3,2,1,2,2,3,4,显然图的生成树不唯一.,B 破圈法,相对于避圈法，还有一种求生成树的方法叫做“破圈法”. 这种方法就是在图G中任取一个圈，任意舍弃一条边，将这个圈破掉，重复这个步骤直到图G中没有圈为止.,例 用破圈法求出,下图的一棵生成树.,B 破圈法,例 用破圈法求出下图的另一棵生成树.,不难发现，图的生成树不是唯一的 .,三、 最小生成树与算法,介绍最小树的两种算法： Kruskal算法（或

14、避圈法）和破圈法.,A Kruskal算法（或避圈法）,步骤如下：,1) 选择边e1，使得w(e1)尽可能小；,2) 若已选定边 ，则从,中选取 ，使得:,i) 为无圈图，,ii) 是满足i)的尽可能小的权，,3) 重复步骤2），直至选够n-1条边.,定理 由Kruskal算法构作的任何生成树,都是最小树.,例用Kruskal算法求下图的最小树.,在左图中 权值,最小的边有 任取一条,在 中选取权值,最小的边,中权值最小边有 , 从中选,任取一条边,中选取在中选取,已经选够5-1条边，从而最小树构造结束。,B破圈法,算法2 步骤如下：,1) 从图G中任选一棵树T1.,2) 加上一条弦e1，T1

15、+e1中,立即生成一个圈. 去掉此,圈中最大权边，得到新,树T2,以T2代T1,重复2)再,检查剩余的弦，直到全,部弦检查完毕为止.,例用破圈法求下图的最小树.,先求出上图的一棵生成树.,加以弦 e2,得到的圈v1v3v2v1,去掉最大的权边e2,得到一棵新,树仍是原来的树；,再加上弦e7，得到圈 v4v5v2v4,去掉最大的权边e6，得到一棵,新树；如此重复进行，直到全,部的弦均已试过,得最小树.,例：一家企业分别要在6间办公室铺设网线接入口，网线的可行走线方式如下图所示，如何铺设网线才能使网线总长为最短？,最短网线总长度为最小树权之和2+3+4+6+6=21,8,2,3,5,4,6,6,6,8,v1,v4,v2,v3,v5,v6,第三节 最短路问题,狄克斯特拉(Dijkstra)算法 路权：弧(vi, vj)的权为lij；路权是路p中各条弧权之 和 最短路：在所有从vs到vt 的路p中，求一条路权最短的路 算法说明： 1959年提出，目前公认的最短路算法 适合于求解所有弧权wij 0的最短路问题,第三节 最短有向路问题,基本思路: 从始点vs 出发，逐步探寻，给每个点标号； 标号分永久标号P(vk)和临时标号T(vk) 两种： 永久标号P(vk) 是从点 vs