图论与网络分析.ppt

图论与网络分析 （Graph Theory and Network Analysis）,教学要求：,了解图论的基本概念，理论和方法以及应用,掌握最小树以及最短路问题等模型及其基本算法掌握欧拉道路、回路的判断和构造方法,18世纪，哥尼斯堡城中有一条普雷格尔河，河上有七座桥将河中的两个小岛与河岸连接起来人们提出了这样的问题：一个散步者能否从某地出发，走遍七桥且每座桥恰好经过一次，最后回到原地？,,,,,,,,,,,,陆地A,陆地B,岛D,岛C,A·,D ·,·B,· C,,,,,,,,1736年瑞士数学家欧拉将两岸和小岛抽象为四个点，将桥抽象为七条边，此问题归结为一笔画问题图论起源,第一节 图论的概念,图论的图与一般几何图形或函数图形是完全不同的图论中的图:由一些点和连接点的线所组成的“图形”点和线的位置是任意的线的曲直、长短与实际无关，代表的只是点与点之间的相互关系,无向图的基本概念,G=(V,E),V={vi}——G的顶点集合,E={ek}—— G的边集合，且ek=（vi,vj）为无序二元组,表示ek连接vi,vj,n(G)=|V|=n——G的顶点数m(G)=|E|=m——G的边数,顶点相邻,两顶点之间有一条边，顶点为该边的端点，边与其端点关联。

边相邻,e1,e2,e3,e4,e5,e6,e7,两边与同一顶点关联，即两边有共同的端点环,两端点重合为一点的边，如e1,多重边,两点之间多于一条边，如e6，e7,简单图,不含环和多重边的图，去掉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，知X∪Y=V，X∩Y=Φ，E中每条边的两个端点，一个在X中，一个在Y中，则称G为二部图，记为G=（X,Y,E）,,,,,有向图的基本概念,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的次网络（赋权图）,在无向图的边（或有向图的弧）上标上实数，称为该边（或弧）的权，无向（有向）图连同它边上的权称为一个网络赋权图，简称网络无向网络，有向网络）,子图,道路，回路,连通图,点i和j点是连通的：i,j之间存在一条链G是连通的：G中任意两点都是连通的 不连通图可以分为若干连通子图，每个称为原图的分图关联矩阵,图的矩阵表示,关联矩阵示例,右图的关联矩阵是 右图的关联矩阵是,e1,e2,e4,e7,e6,e5,e8,e3,e1,e2,e3,e4,e5,邻接矩阵,邻接矩阵示例,右图的邻接矩阵是 右图的邻接矩阵是,主要结论,图论基本概念应用,例1：证明在9座工厂之间，不可能每座工厂只与其他3座工厂有业务联系，也不可能只有4座工厂与偶数个工厂有业务联系。

将9座工厂看做9个点，他们有联系用边相连，若每座工厂只与其他3座工厂有业务联系，则每个点的次都为3，从而总次为27，非偶数，与总次为边的2倍矛盾从而得证若只有4座工厂与偶数个工厂有业务联系，则其余5座与奇数个工厂有业务联系，从而总次为 4*偶+5*奇=奇数非偶数，矛盾从而得证例2：6个人围成圆圈就座，每个人恰好只与相邻者不认识，是否可以重新就座，使每个人都与邻座认识？,将6个人看做6个点，相互认识用边表示,要求重排之后每个人与邻座认识只需找到一个序列，该序列中前后两个点是相邻的就可以了如1->3->5->2->6->4->1,,,,,,,例3 甲、乙、丙、丁、戊5个运动员报名参加A,B,C,D,E，F六个项目比赛，报名情况见下表（打*表示各运动员报名参加的比赛项目）问如何安排项目，使每名运动员不连续参加两项比赛？,将6个项目看做6个点，同一个人参加的项目之间有边,要求安排项目，每名运动员不连续参加两项比赛，只需找到一个遍历点的序列，该序列中前后两个点是不相邻的就可以了如A->C->D->E->F->B,练习 10个研究生参加6门课考试，每个研究生考试课程见下表，要求上下午各排一门课，每人每天最多考一门，且A必须第一天上午，F必须最后考，B要安排在下午考，试给出一个考试安排表。

AECBDF,欧拉回路,连通图G中若存在一条道路，经每边一次且仅一次，则该道路为欧拉道路若存在一条回路，经每边一次且仅一次，该回路为欧拉回路有欧拉回路的图称为欧拉图结论：,Th1：无向连通图G为欧拉图充要条件是G中无奇点Th2：无向连通图G为欧拉图充要条件是G的边集可分为若干初等回路Th3：无相连通图G为欧拉道路充要条件是G中恰有2个奇点Th4：连通有向图G为欧拉图充要条件是他每个顶点的出次等于入次Th5：连通有向图G为欧拉道路充要条件是这个图中除了两个顶点之外，其余每个顶点出次等于入次，且这两顶点中，一个顶点入次比出次多1，另一个出次比入次多1.,一个散步者能否从某地出发，走遍七桥且每座桥恰好经过一次，最后回到原地？ 即是否存在欧拉回路？,,,,,,,,,,,,陆地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,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的生成树. 图G中不在生成树的边叫做弦.,定理 图G=(V,E)有生成树的充要条件是图G是连,通的.,找图中生成树的方法,可分为两种：避圈法和破圈法,A 避圈法 : 深探法和广探法,B 破圈法,A 避圈法,这种方法就是在已给的图G中，每步选出一条边使它与已选边不构成圈，直到选够n-1条边为止. 这种方法可称为“避圈法”或“加边法”,在避圈法中，按照边的选法不同，找图中生成树的方法可分为两种：深探法和广探法.,a) 深探法,若这样的边的另一端均已有标号，就退到标号为,步骤如下：,i) 在点集V中任取一点u,,ii) 若某点v已得标号，检,端是否均已标号.,若有边(v,w)之w未标号,则给,w代v，重复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\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算法（或避圈法）和破圈法.,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+e1中,立即生成一个圈. 去掉此,,圈中最大权边，得到新,树T2,以T2代T1,重复2)再,检查剩余的弦，直到全,部弦检查完毕为止.,例用破圈法求下图的最小树.,先求出上图的一棵生成树.,加以弦 e2,得到的圈v1v3v2v1,,去掉最大的权边e2,得到一棵新,树仍是原来的树；,,,,,,,再加上弦e7，得到圈 v4v5v2v4,,,,去掉最大的权边e6，得到一棵,新树；如此重复进行，直到全,部的弦均已试过,得最小树.,例：一家企业分别要在6间办公室铺设网线接入口，网线的可行走线方式如下图所示，如何铺设网线才能使网线总长为最短？,最短网线总长度为最小树权之和2+3+4+6+6=21,。