《图论基础(信息学奥赛).ppt》由会员分享，可在线阅读，更多相关《图论基础(信息学奥赛).ppt（90页珍藏版）》请在三一办公上搜索。
1、图论及其算法,吴闻,第一章 基本概念,1.1 引言1.2 图的定义1.3 道路和回路1.4 树,1.1 引言,图论是一个应用十分广泛而又极其有趣的数学分支。物理、化学、生物、科学管理、计算机等各个领域都可找到图论的足迹。介绍几个图论有关的简单例子,1.1 引言,例1 下图是一个公路网，V1,V2,.,V10是一些城镇，每条线旁边的数字代表这一段公路的长度。现在问，要从V1把货物运到V10，走哪条路最近?,1.1 引言,例1实际上，就是图论中的求最短路径问题。在现实中有很多此类问题，所以图论中求最短路径算法是一个非常经典和重要的算法。,1.1 引言,例2 下图是一个公路网，V1,V2,.,V10
2、看成公路网的一个站点，若这个公路网目前被敌方占领。请分析一下，最少需要破坏其公路网的几个站点，就可摧毁敌方整个运输线,1.1 引言,例2属于图的连通性问题。找出图中的割顶集，就是问题的解。军事指挥中很多此类问题。,1.1 引言,例3 飞行大队有若干个来自各地的驾驶员，专门驾驶一种型号的飞机，这种飞机每架有两个驾驶员。由于种种原因，例如相互配合的间题，有些驾驶员不能在同一架飞机上飞行，问如何搭配驾驶员，才能使出航的飞机最多。,1.1 引言,例3 用V1,V2,.,V10代表这10个驾驶员。如果两个人可以同机飞行，就在代表他们两个之间连一条线;两个人不能同机飞行，就不连。例如V1和V2可以同机飞行
3、，而V1和V 3就不行。,1.1 引言,例3此类问题属于图的最大匹配问题将实际生活中的事物分析转化为图论问题的实例还很多.,1.2 图的定义,图：由若干个不同顶点与连接其中某些顶点的边所组成的图形。图的表示：通常用一个大写字母G来表示图，用V来表示所有顶点的集合，E表示所有边的集合，并且记成G=(V,E)。,1.2 图的定义,子图：如果对图G=(V,E)与G=(V,E),G的顶点集是G的顶点集的一个子集(VV),G的边集是G的边集的一个子集(EE)，我们说G是G的子图,1.2 图的定义,环：如果一条边，它的起点和终点相同，这样的边称为环。平行边：若连接两个顶点的边有多条，则这些边称之为平行边。
4、孤立点：不与任何边关联的顶点称为孤立点。,1.2 图的定义,简单图：如果一个图没有环，并且每两个顶点之间最多只有一条边，这样的图称之为简单图。在简单图中，连接Vi与Vj的边可以记成(Vi,Vj)完全图：如果G是一个简单图，并且每两个顶点之间都有一条边，我们就称G为完全图。通常将具有n个顶点的完全图记为Kn。二分图：如果G是一个简单图，它的顶点集合V是由两个没有公共元素的子集X=X1,X2,.,Xn与Y=Yl,Y2,.,Ym组成的，并且Xi与Xj(1i,jn),Ys与Yt(1s,tm)之间没有边连接，则G叫做二分图。,1.2 图的定义,简单图、完全图、二分图,1.2 图的定义,完全二分图：如果在
5、二分图G中，IXI=N,IYI=M，每一个XiX与每一个YjY有一条边相连，则G叫做完全二分图,1.2 图的定义,如果G是一个N个顶点的简单图，从完全图Kn中把属于G的边全部去掉后，得到的图称为G的补图，通常记为G。一个图的补图的补图就是自身。,1.2 图的定义,相邻：如果图G的两个顶点Vi与Vj之间有边相连，我们就说Vi与Vj是相邻的，否则就说Vi与Vj是不相邻的。如果顶点V是边e的一个端点，就说顶点V与边e是相邻的，e是从V引出的边。度数：从一个顶点V引出的边的条数，称为V的度数，记作d(V)。,1.2 图的定义,下图中，d(V1)=d(V2)=d(V3)=d(V4)=d(V5)=5-1=
6、4,d(Y3)=2等等。,1.2 图的定义,K度正则图：把每个顶点的度数为常数K的图叫做K度正则图。经常使用下面两个符号:,1.2 图的定义,从顶点度数问题的讨论中，引出一些有趣的结论:1.2.对于任意的图G，奇次顶点的个数一定是偶数。,1.2 图的定义,例1、空间是否有这样的多面体存在，它们有奇数个面，而每个面又有奇数条边?分析:根据题意，可以构造一个图，以面为顶点，当且仅当两个面有公共棱时，则在G的相应两顶点间连一条边，得到图G。依题意，图的顶点个数是奇数，而且每个顶点的度数d(V)是奇数，从而 也是奇数，与结论1相违，故这种多面体不存在。,1.2 图的定义,例2、晚会上大家握手联欢，问是
7、否会出现握过奇次手的人是奇数的情况?分析:一个图，以人为顶点，两人握手时，则相应的两个顶点之间连一条边，于是每人握手的次数即相应顶点的度数。由结论2，奇次顶点的个数总是偶数，所以握过奇次手的人数是奇数的情况不可能出现。,1.3 道路与回路,道路：在图G中，一个由不同的边组成的序列e1,e2.,eg，如果ei是连接Vi-1与Vi(i=1,2,.,g)的，我们就称这个序列为从V0到Vg的一条道路，数g称为路长，V0与Vg称为这条道路的两个端点，Vi(1=i=g-1)叫做道路的内点。如果G是简单图，这条道路也可以记作(V0,V1,.,Vg),1.3 道路与回路,下图中e1,e2,e3,e4,e5,e
8、6组成一条道路,1.3 道路与回路,轨道：在道路的定义中，并不要求V0至Vg，互不相同。如果V0至Vg互不相同，这样的道路称为轨道，记成P(V0,Vg)。回路：V0=Vg的路称为回路。圈：V0=Vg的轨道叫做圈。K阶圈：长为K的圈叫做K阶圈。显然，如果有一条从V到V的道路上去掉若干个回路，便可得到一条从V到V的轨道。,1.3 道路与回路,U,V两顶点的距离：U,V间最短轨道的长度，记作为D(U,V)。连通图：若U与Y之间存在道路，则称U与V相连通。图G中任意两个顶点皆连通时，称G为连通图。,1.3 道路与回路,如果图G是一条从V0到Vg的道路，那么该条道路上的每一个内点Vi(1=i=g-1)都
9、是度数为偶数的顶点。因为对Vi来说，有一条进入Vi的边，就有一条从Vi引出的边，而且进出的边不能重复已走过的边，所以与Vi相邻的边总是成双的。故图G至多有两个奇顶点，即V0与Vg。如果G是一条回路，那么根据上面推理，V0与Vg的度数也是偶数。由此，我们可以引出下面一个结论:,1.3 道路与回路,有限图G是一条道路(即可以一笔画成)的充分必要条件是G是连通的，且奇顶点的个数等于0或2，并且当且仅当奇顶点的个数为0时，连通图G是一条回路(孤立点可以看作是回路)。,1.3 道路与回路,七桥问题：一条河从城市穿过，河中有两个岛A与D，河有七座桥，连接这两个岛及河的两岸B,C。如下图所示：,1.3 道路
10、与回路,问:(1)一个旅行者能否经过每座桥恰好一次，既无重复也无遗漏?(2)能否经过每座桥恰好一次，并且最后能够回到原来出发点?七桥问题转换成图后，实际上就成了图的一笔画问题：能否一笔画出这个图，每条边既无遗漏，也无重复？能否一笔画出这个图，并且最后回到出发点。根据道路和回路的知识解答,1.3 道路与回路,显然，由于七桥问题对应的图中有4个奇顶点，因而不能一笔画成，即一个旅行者要既无重复也无遗漏地走过图中七座桥是不可能的。需要几笔呢？,1.4 树,树：没有圈的连通图称作树，通常用T表示。T中d(V)=1的顶点叫做叶;森林：每个连通分支皆为树的图叫做森林。平凡树：孤立的顶点叫做平凡树。树的图论特
11、征：如果树T的顶点数为N，那么它的边数M=N-1;倒过来，一个具有N个顶点、M=N-1条边的连通图G，一定是一棵树。,1.4 树,红楼梦中荣国府的世系图就是一棵树：,1.4 树,树T具有以下性质:1.在T中去掉一边后所得的图G是不连通的，2.T添加一条边后所得的图G一定有圈;3.T的每一对顶点V与V之间有且仅有一条轨道相连。,1.4 树,设G是一个连通图，如果G中有圈，我们在这个圈中去掉一条边，得到的G还是连通的，如果G仍然有圈，再在圈中去掉一条边得连通图G，.，这样继续下去，最后得到一个树T，T与G的顶点是相同的，并且从T陆续添加一些边就得到G。具有这样性质的树称为连通图G的生成树。,第二章
12、 求最短路径的算法及应用,2.1 求最短路2.2 服务点设置间题1求图的中心2.3 服务点设置间题2求图的P中心2.4 服务点设置间题3求图的中央点,2.1 求最短路,一、什么是最短路问题：1.求有向图(图中从一个顶点连到相邻顶点的边有方向性)的最短路问题：设G=(V,A)是一个有向图，它的每一条弧Ai都有一个非负的长度L(Ai)，在G中指定一个顶点Vs，要求把从Vs到G的每一个顶点Vj的最短有向路找出来(或者指出不存在从Vs到Vj的有向路，即Vs不可达Vj,2.1 求最短路,2.求无向图(图中连接两个顶点的边无方向性)的最短路问题：设G=(V,E)是一个无向图，它的每一条边ei都有一个非负长
13、度L(ei)。在G中指定一个顶点Vs，要求把从Vs到G的每一个顶点Vs的最短无向路找出来(或者指出不存在从Vs到Vj的无向路，即Vs不可达Vj。,2.1 求最短路,二、求最短有向路的标号法 所谓标号，是指与图的每一个顶点对应的一个数字。设:b(j)：顶点Vj的标号，代表的是Vs到Vj的最短的长度。Vj已标号则意味着Vs到Vj的最短路以及这条路径的长度已经求出。显然初始时b(s)=0。l(i,j)：弧(Vi,Vj)的非负长度。K(i,j)：当前有向路加入弧(Vi，Vj)后，Vs到Vj的有向路长度。,2.1 求最短路,标号法的算法流程如下：,2.1 求最短路,标号法通用于有向、无向图。,2.1 求
14、最短路,实例：渡河问题。一个人带了一只狼、一只羊和一裸白菜想要过河，河上有一只独木船，每次除了人以外，只能带一样东西。另外如果人不在旁时狼就要吃羊，羊就要吃白菜。问应该怎样安排渡河，才能做到既把所有东西都带过河，在河上来回的次数又最少?分析：设变量M代表人，W代表狼，S代表羊，V代表白菜，代表空，什么都没有。开始时设人和其它三样东西在河的左岸，这种情况用MWSV表示。,2.1 求最短路,用一个集合表示左岸的所有可能情况。很显然，可能出现的情况有16种:剔除下述6种可能发生狼吃羊、羊吃白菜的情况:,2.1 求最短路,构造一个图G，它的顶点就是剩下的10种情况。G中的边是按下述原则来连的:如果经过
15、一次渡河，情况甲可以变成情况乙，那么就在情况甲与情况乙之间连一条边。,2.1 求最短路,作了图G以后，渡河的问题就归结为下述问题了:在G中找一条连接顶点MWSV与，并且包含边数最少的路。如果设G中各边的长度都是1，那么也可以把渡河间题归结为:“找一条连接MWSV与的最短路”。最终问题归结为求最短路径问题。,第三章 求最小生成树,3.1 求无向图的最小生成树3.2 求有向图的最小树形图,3.1求无向图的最小生成树,一、最小生成树的由来设G=V,E是一个无向图，如果T=V,E1是由G的全部顶点及一部分边组成的子图并且T是树(连通、没有圈的图)，则称T是G的一个生成树。一个连通图G一般有许多种生成树
16、。现在考虑一个连通图G=V,E，它的每一条边Ej，有一个长度L(Ej)0。这时对于G的任意一个生成树T，我们把属于T的各条边的长度之和称为T的长度，记作L(T)。,3.1求无向图的最小生成树,一、最小生成树的由来下图中，T1和T2是G的生成树，L(T1)=22,L(T2)=17,3.1求无向图的最小生成树,一、最小生成树的由来最小生成树问题：如何从G的所有生成树中，找出长度最小的生成树。这个问题即所谓最小生成树间题。,3.1求无向图的最小生成树,二、最小生成树的计算一开始，先将G图中的边都去掉，只留下孤立的顶点，这个图即为G图最初的生成子图G1。然后逐步地将当前最小边e1加上去，每次加的时候，
17、要保持“没有圈”的性质，在加了N-1条边(N是顶点个数)后，G1便成为所要求的最小生成树了。,3.1求无向图的最小生成树,二、最小生成树的计算算法步骤如下：,第四章 图的连通性,4.1 连通性的基本概念和定义4.2 深度优先搜索(dfs)4.3 求割顶和块4.4 求极大强连通子图4.5 求最小点基4.6 可靠通讯网的构作,4.1 连通性的基本概念和定义,在无向图G中，如果从顶点V到顶点V有路径，则称V和V是连通的。如果对于图中任意两个顶点Vi,VjV,Vi和Vj都是连通的，则称该图为连通图。所谓连通分量指的是无向图中的极大连通子图,4.1 连通性的基本概念和定义,在有向图G中，如果对于每一对V
18、i,VjV,ViVj,从Vi到Vj，和从Vi到Vj都存在路径，则称G是强连通图。有向图中的极大强连通子图称作有向图的强连通分量。,4.1 连通性的基本概念和定义,一个连通图的生成树是一个极小连通子图，它含图的全部顶点，但只有足以构成一棵树的N-1条边超过N-1条边必有回路，就不再是树了。,4.1 连通性的基本概念和定义,为更精确的描述图的连通性，还需引入两个概念：顶连通度K(G)边连通度K(G),4.1 连通性的基本概念和定义,顶连通度：V是连通图G的一个顶点子集。在G中删去V及与V相关联的边后图不连通，则称V是G的割顶集。最小割顶集中顶点的个数，记成K(G)，称为G的连通度。规定K(完全图)
19、=顶点数-1;K(不连通图)=K(平凡图)=0。K(G)=1时，割顶集中的那个顶点叫做割顶。没有割顶的图叫做块，G中成块的极大子图叫做G的块。,4.1 连通性的基本概念和定义,下图中，K(G2)=1,K(G3)=3,K(G4)=5-1=4;G3与G4是块;G2中有两个三角形块。,4.1 连通性的基本概念和定义,边连通度K(G)E是连通图G的一个边子集。在G中删去E中的边后图不连通，则称E是G的桥集.若G中已无桥集E，使得|E|E|，则称|E|为G的边连通度，记成K(G)。|E|=1时，E中的边叫做桥。规定K(不连通图)=0,K(完全图)=顶点数-1。,4.1 连通性的基本概念和定义,下图中，K
20、(G2)=2,K(G3)=3,K(G4)=5-1=4。G2,G3,G4中无桥。,4.1 连通性的基本概念和定义,对于任意一个连通图G，在计算出上述两个量后，我们可以给该图下一个定义:K(G)M,G叫做M连通图;K(G)M时，G称为M边连通图。下面给出连通图G的两个特征:1.K(G)K(G)G的顶点度数的最小值2.顶点数大于2的2连通图的充分必要条件是任两个顶点在一个圈上。,4.2 深度优先搜索(dfs),深度优先搜索过程:先任取一个顶点为根，记为U，作为深搜的起始出发点，设置U顶点为已访问。再从U的邻接顶点中，任选W顶点，对应关联边(U,W)，将该边定方向为U到W。此时边(U,W)称为“已检查
21、”，且作为树枝边且加入树枝边集合中，U称为W的父亲点，记为U=father(W)。再以W顶点作为新的出发点，重复上面步骤,4.2 深度优先搜索(dfs),一般情况下当访问某顶点X时，有两种可能:1、如果X顶点的所有关联边被检查过了，则回溯至X的父亲顶点，从father(X)再继续搜索，此时X顶点已无未用过的关联边;2、如存在X顶点未用过的关联边，则任选其中一边(X,Y)，对其定向为从X到Y,此时说边(X,Y)正等待检查。,4.2 深度优先搜索(dfs),检查结果有两种情况:1.如Y顶点从未被访问过，则顺着(X,Y)边访问Y，下一步从Y开始继续搜索。此时(X,Y)是前向边，且顶点X=father
22、(Y)，图上用实线表出;2.如Y顶点已被访问过，则再选一X顶点未用过的关联边。此时(X,Y)是后向边，用虚线表出。,4.2 深度优先搜索(dfs),此时，(X,Y)的归属已明确，(X,Y)就检查完毕。在dfs搜索期间，将顶点X被首次访问的序号作为顶点的dfn值，记为dfn(X)，如dfn(X)=i，则X是深搜过程中第i个被访问的顶点，dfn(X)称为X的深度优先搜索序数，当搜索返回根时，连通图的所有顶点都访问完毕。现在图中的边都定了方向，且分成前向边以及后向边(虚线)，前向边(实线)组成的有向树，称为dfs树。,4.2 深度优先搜索(dfs),对左图进行dfs搜索得到右图的dfs树。每个顶点旁
23、数字为顶点dfn值。,4.2 深度优先搜索(dfs),无向图G的dfs算法分析。,4.2 深度优先搜索(dfs),dfs树由前向边组成，若非连通图，则对每一个连通分量进行一次dfs搜索，结果产生一个由若干dfs树组成的森林。如果从U到W有树边组成的有向路，则称U和W有直系关系，U称为W的祖先点，W称为U的后代点。如(U,W)是树中一条边，U又确切地称为W的父亲点，W也可称为U的儿子点。一个顶点可有多个儿子点，顶点U和它的所有后代点组成关于树中以U为根的子树。,4.2 深度优先搜索(dfs),有向图的dfs本质上近似无向图，区别在于搜索只能顺边的方向去进行(有向边，简称弧)。有向图中的弧根据被检
24、查情况可有4种，一条未检查的弧(U,W)可按如下4种情况，分类归划成(其中2,3,4所述的三种情况中，设W已访问过)：,4.2 深度优先搜索(dfs),1.W是未访问过的点，(U,W)归入树枝弧2.W是U的已形成的dfs森林中直系后代点，则(U,W)称为前向弧。无论(U,W)是树枝弧还是前向弧，dfn(W)dfn(U)。3.W是U的已形成的dfs森林中直系祖先点，则(U,W)称为后向弧。4.U和W在已形成的dfs森林中没有直系上下关系，并且有dfn(W)dfn(U)这种类型的横叉弧。,4.2 深度优先搜索(dfs),4.2 深度优先搜索(dfs),下图为有向图的dfs示例：,是树枝弧，组成df
25、s森林(用粗线表示);是后向弧;是前向弧;,是横叉弧。,4.2 深度优先搜索(dfs),有向图和无向图的dfs算法基本相似,4.3 求割顶和块,割顶：如果一个连通图，删除某一顶点，不在连通，这个顶点就称为割顶。块：一个连通图，如果删除任一顶点不会破坏连通性，即没有割顶，这个连通图称为块。,4.3 求割顶和块,分析一个由无向图表示的通讯网，顶点看作是通讯站，无向边代表两个通讯站之间可以互相通讯。问:1.若其中一个站点出现故障，是否会影响系统正常工作;(求割顶)2.这个通讯网可以分成哪几个含站点尽可能多的子网，这些子网内的任一站点出现故障，都不会影响子网工作。(求块，即没有割顶的连通子图),4.3
26、 求割顶和块,给定dfs树，割顶的判断：1.如U不是根，U成为割顶当且仅当存在U的某一个儿子顶点S，从S或S的后代点到U的祖先点之间不存在后向边。2.如被选为根，则成为割顶当且仅当它有不止一个儿子点,4.3 求割顶和块,给定dfs树，割顶的判断：,4.3 求割顶和块,割顶的判断法则是构思算法的精华，为此引入一种顶点U的标号函数LOW(U)=min(dfn(U),LOW(S),dfn(W)其中:S是U的儿子，(U,W)是后向边。显然LOW(U)值恰是U或U的后代所能追溯到的最早(序号小)的祖先点序号。一般约定，顶点自身也认为自己是祖先点。所以有可能LOW(U)=dfn(U)或LOW(U)=dfn
27、(W)。,4.3 求割顶和块,利用标号函数LOW，我们可以将割顶判定1重新描述成:顶点U作为G的割顶当且仅当U有一个儿子S，使得LOW(S)dfn(U)，即S和S的后代不会追溯到比U更早的祖先点。,4.3 求割顶和块,LOW(U)值的计算步骤如下:在算法执行中，对任何顶点U计算LOW(U)值是不断修改的，只有当以U为根的dfs子树和后代的LOW值、dfn值产生后才停止。,4.3 求割顶和块,求割顶算法,4.3 求割顶和块,示例如下：从左图V3出发，按上述算法进行搜索，得出dfs树和各顶点dfn值、LOW值见右图。由于是前向边，且dfn(V5)=21,LOW(V5)=2，又LOW(V4)=2，由
28、基本事实1得出V4是割顶，并导出V4,V3,V2和V4,V5,V6,V7两个块。,4.4 求极大强连通子图,极大强连通子图：有向图中任意两个顶点都有向路双向连通的最大子图为了在dfs森林的基础上找强分支子树的根，我们引人了顶点U的标值函数LOWLINK(U)：LOWLINK(U)=mindfn(U),dfn(W)其中W是从U或U的后代点出发用一条后向弧或横叉弧所能到达的同一强连通分支中的顶点。,4.4 求极大强连通子图,由此可以看出，LOWLINK(U)正是U所处的强分支中从U出发先用树枝弧、前向弧，最后用后向弧或横叉弧到达的dfn最小的顶点的序值。而对于强分支的根i显然有LOWLINK(i)=dfn(i)。因此当深度优先搜索从一个使dfn编码=LOWLINK值的顶点U返回时，从树中移去根为U的所有顶点。每一个这种顶点的集合是一个强分支，即极大强连通子图.,4.4 求极大强连通子图,算法的主要思路是用逐步迭代计算出LOWLINK(U)值。,4.4 求极大强连通子图,求极大强连通分支的算法,
