图论知识及其应用的课件

1、 图论知识及其应用 图的定义图(graph)可用G=(V,E)来表示，即顶点集合V和边集合E组成的二元组。E中的每条边是V中一队顶点(u,v)。如果(u,v)是无序对，那么称该图为无向图，否则为有向图。任意两个顶点最多只有一条边(多条边称为重边)，且每个点都没有连接到它自身的边(无自环)的图叫简单图。顶点和边如果(u,v)是E(G)中的一条边，则称u与v互为邻接顶点。在无向图中，一个顶点v的度是与他相关联的边的条数。在有向图中，顶点的度等于该顶点的入度与出度之和。顶点v的入度是以v为终点的有向边的条数；顶点v的出度是以v为始点的有向边的条数。某些图的边具有与它相关的数，称之为权。这种图称为网络

2、或带权图。路径在图G=(V,E)中，若从顶点vi出发，沿一些边经过一些顶点vp1,vp2,vpm，到达顶点vj。则称顶点序列(vi vp1 vp2 vpm vj)为从顶点vi到顶点vj的路径。它经过的边(vi,vp1)、(vp1,vp2)、(vpm,vj)应是属于E的边。非带权图的路径长度是指路径上边的条数。带权图的路径长度是指路径上各边的权之和。若路径上各顶点v1,v2,vm均不互相重复，则称这样的路径为简单路径。若路径上第1个顶点v1与最后一个顶点vm重合，则称这样的路径为回路或环。图的连通性在无向图中，若从顶点v1到顶点v2有路径，则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通

3、的，则称此图是连通图。非连通图的极大连通子图叫做连通分量。特别的，一个连通图的生成树是它的极小连通子图，在n个顶点的情况下，有n-1条边。在有向图中，若对于每一对顶点vi和vj，都存在一条从vi到vj和vj到vi的路径，则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。点连通性设无向图G是连通的，若有结点集 ，使得图G删除了v1所有的结点后所得的子图是不连通的，而删除了v1的任意真子集后，所得的子图仍然是连通图，则称集合v1为图G的点割集。若某一结点就构成了一个点割集，则称该结点为割点。包含点数最少的割集所包含的点数称为G的点连通度k(G)边连通性设无向图G为连通的，若有边集 ，使

4、得图G删除了E1所有边后所得的子图是不连通的，而删除了E1的任意真子集后，所得的子图仍然是连通图，则称集合E1为图G的边割集。若某一边构成边割集，则称该边为桥(或割边)。包含变数最少的边割集所包含的边数称为G的边连通度k(G)图的实现：邻接矩阵与邻接表邻接矩阵：设图A=(V,E)有n个顶点，g为一个二维数组，则当(i,j)为图中的边时有gij=1，否则gij=0。如果需要存储带权图，则把gij的值改为对应权w(i,j)的大小。带权的邻接矩阵无法保存重边。邻接矩阵的空间复杂度为O(N2)，查询边的复杂度O(1)，添加边的复杂度O(1)邻接表将同一个顶点出发的边链接在同一个边链表中，链表的每一个结

5、点代表一条边，叫做边结点。空间复杂度O(M+N)，查询边的复杂度O(Mi)，Mi为与i相连的边的数目，添加边的复杂为O(1)图的遍历一般分为两种，广度优先遍历和深度优先遍历。广度优先遍历：从一个点出发，按最短路径长度从小到大的顺序遍历，用一个队列实现。如果使用邻接矩阵，时间复杂度为O(N2)；使用邻接表则时间复杂度为O(N+M)深度优先遍历：从一个点出发，沿着边尽量走到没有访问过的顶点。如果没有未访问过的顶点，则沿边的相反方向退一步。一般用栈实现。用的空间较少，时间复杂度同上。可行性遍历问题常见的问题有下面两种Hamilton回路问题Euler回路与Euler路问题Hamilton问题已经被证

6、明是NP完全问题，尚未发现多项式算法下面介绍Euler回路与Euler路问题Euler回路无向图的Euler回路如果一个无向图所有的顶点的度为偶数，那么该图可以用起始点与终止点相同的一笔画出，这一笔经历的路线叫做无向图的Euler回路。有向图的Euler回路如果一个有向图的所有顶点的入度等于出度，那么该图可以用起始点与终止点相同的一笔画出，这一笔经历的路线叫做有向图的Euler回路。求Euler回路的套圈算法首先检查图G是否符合一笔画的条件。如果符合，那么标记顶点1为待查找状态。过程Euler(i)寻找开始于顶点i并且结束于顶点i的Euler回路，具体步骤如下：寻找从i出发的环 P1P2Px

7、(P1=Px=i)标记顶点P1x为待查找状态对所有处在待查找状态的结点Pj递归调用过程Euler(Pj)将Euler(Pj)找到的环Q1Q2.Qy插入到环P1P2Px中，得到回路P1P2PjQ2QyPj+1Px时间复杂度为O(M)Euler路问题如果一个无向图恰有两个顶点x,y的度为奇数，那么该图可以用起始点于x与终止点于y的一笔画出，这一笔经历的路线叫做无向图的Euler路。如果一个有向图中，顶点x出度比入度大1，顶点y入度比出度大1，其余所有顶点入度等于出度，那么该图可以用起始点于x与终止点于y的一笔画出，这一笔经历的路线叫做有向图的Euler路。求解Euler路问题可以沿用求解Euler

8、回路的套圈算法解决。另一种方法求解Euler回路与Euler路以求解有向图的Euler路问题为例，以下的算法框架首先判断是否存在Euler路如果存在则继续，否则跳出过程设x为Euler路的起点，y为终点，设当前点k为xfor t = 1 to n枚举与k相连的所有边(k,i)，找到一个不在以前求的路径中的i满足删除这条边(k,i)后剩余子图仍存在Euler路，且Euler路的起点必须是i，终点必须是y。pathtkki时间复杂度O(N+M)DFS在图论中的应用无向图我们定义在DFS过程中，结点的颜色有3种：白色表示尚未被遍历过；灰色表示已经被遍历但尚未检查完毕(即DFS树中当前结点与根的路径上

9、的点)；黑色表示已经被遍历而且检查完毕(即已经完全访问过的点)。无向连通图的割顶如果对于一个结点i，在DFS过程中，发现i的某个儿子j或j的子孙有连向i祖先的边(即j及j的子孙中存在灰色结点)，那么i就不是割顶。求法：用ancestori表示搜索树中i以及i的子孙中所能到达的最高的i的祖先。用deepi表示i结点在搜索树中的深度。无向连通图的割顶procedure Dfs(当前结点k,k的父亲fa)begincolork=灰色deepk=deepfa+1ancestork=deepkfor i = 1 n if 边(k,i)未访问过beign if i为白色Dfs(i) if i为灰色且i不是

10、faancestork=min(ancestork,ancestori)endif ancestork=deepk k是原图的一个割顶ancestork=min(ancestork,deepk)colork=黑色end;无向连通图的缩圈顾名思义，即将无向图的所有连通分量收缩成一个点缩圈的结果是将原图收缩成一棵树同样是用求无向图割顶的程序，不过需要附加记录Ai表示i的子孙里能到达的最高的i的祖先的编号。在做完DFS后，对于一个结点i，利用并查集将i与Ai所在的集合合并(因为i与Ai处于同一个圈上)。这样处理完所有的结点后，新图中的一个结点就代表原图中的一个集合，重新把边添上就可以了(注意处理重边

11、)在缩圈之后，求图的桥就十分简单了。所有新图中的边都是原图的桥。有向图的极大强连通分支下面给出算法对图进行DFS遍历，遍历时记下所有的时间戳Ti。遍历的结果是构建了一座森林W1，我们对W1中的每棵树G进行步骤(2)到步骤(3)；改变图G中每一条边的方向，构造出新的有向图Gr；按照Ti由大到小的顺序对Gr进行DFS遍历。遍历的结果是构建了新的森林W2，W2中每棵树上的顶点构成了有向图的极大强连通分支。求有向图的极大强连通分支的算法，我们可以轻松实现有向图的收缩：先求出所有极大强连通分支，将所有极大强连通分支都收缩成一个点。这样原图就变成一个拓扑图。生成树问题最小生成树(Prim,Kruskal)

12、最大边最小的生成树(Kruskal)最大边与最小边差最小的生成树枚举最小边,然后在比它权值大的边集中用Kruskal求解。K小生成树(次小生成树)首先可以证明，次小生成树为最小生成树替换一条边后得到。构造最小生成树，设生成树为T。然后枚举非生成树的边(x,y)，加入该边后就需要删除在T上x,y之间路径上的边权最大的边。因此定义f(i,j)为生成树上i结点到j结点间路径上的最大值边，其中i,jT。所以答案就为min(|T|+w(i,j)-f(i,j)算法瓶颈在与求f(i,j)。如果硬做是O(N2)，可以利用LCA做到O(M)的复杂度。度限制最小生成树单点度限制生成树设v0为有度限制的点，其限制为

13、k，设Hi表示v0的度数为i的最小生成树。问题就是求minHi,1=i=k。可以证明，Hi=minHi-1+(x,y)-(a,b),(x,y)Hi-1,(a,b)E-Hi-1我们可以按照类似求次小生成树的方法求出f(i,j)。暴力枚举求解是O(n2)的。但是这个问题与上个问题有一点区别：只需要询问f(V0,i)。因此只需要记录g(i)表示从在当前的生成树中V0到i的路径上的最大边。这样就可以在O(n)时间内完成查询(即求出添加的边(V0,x)然后花O(n)时间从x开始遍历整个树，以更新g的值即可。由因为g的初始值可以在O(n)的时间内求出，因此由Hi-1求出Hi的复杂度就变成了O(n)度限制最

14、小生成树单点度限制生成树将v0及其相邻的边从原图G中删去得到新图G。在新图求最小生成树，得到森林W。选取权最小的边，将森林W中的每个树Ti(i=t) 与v0连接，作为Ht。按照之前所说的方法依次求出Ht+1,Ht+2,Hk。时间复杂度O(n(k+logn)+m)或O(nk+mlogm)空间复杂度O(n+m)最短路问题DijkstraFloydBellman-ford ( SPFA )网络流问题最大流最短增广路O(N2M)加边指针优化预流推进算法O(N2M)最高标号预流推进算法O(N2M1/2)DinicO(N2M)07年王欣上浅谈基于分层思想的网络流算法实际效果很好，一般远低于理论复杂度最大流

15、最小割定理定义：最小割集C为一个边的集合，若从E中删去C则S与T不连通，并且C中边的权值和尽量小S所在的连通分量叫做S集，T所在的连通分量叫做T集。定理：网络G的最小割容量为该网络的最大流流量。网络流问题最小费用最大流最小费用路算法即在最大流问题中的最短增广路算法进行改进，每次使用ford(spfa)求出一条费用最小的连接S和T的路径。复杂度O(NMV)，V为最多迭代的次数(最大流量)消圈算法在最大流残量网络中不断寻找负权圈并沿着它增广，直到不存在这样的负权圈。复杂度O(NM2CW)，c最容量最大值，w是费用最大值。可以做到O(NM2logN)。二分图问题二分图最大匹配匈牙利算法O(NM)Ho

16、pcroft算法O(NM1/2)即将二分图转化为单位容量网络的最大流问题二分图最佳匹配KM算法O(N4)二分图最小覆盖数即求最少的点让每条边都至少与其中的一个点关联。可以转化为二分图最大匹配问题，即二分图最大匹配数等于二分图最小覆盖数。二分图及其相关问题二分图独立数即找出一个点集V，使得不存在(x,y)E满足x,yV同样可以转化为二分图最大匹配问题，即|V|=|V|-|M|最小路径覆盖问题。用尽量少的不相交的简单路径覆盖一个有向无环图G的所有顶点。构造二分图G，将G中的顶点i拆为i和i，分别作为G的左右边结点。若图G中存在边(i,j)，那么对应的在G中构造边(i,j)。图G的最小路径覆盖数即等

17、于n-图G的最大匹配数。综合例题分析例题1 spoj203有一个考察队伍，决定对一个洞穴进行考察。洞穴有干个洞和连接洞的走道构成。一个队员从洞顶 (只能向下)走到洞底。要求任意两个队员的考察路线不能相交(可以在某个洞汇合)。问最多有几个队员可以同时进行考察。(n=200）例题2给出若干个三元组(xi,yi,zi)。每次可以选择若干个三元组满足选出的三元组中xi,yi,zi严格递增。求最少要选几次能将所有的三元组选完。N=1000例题3 spoj282给出一个n*m的网格，有的位置是泥地，有的地方是草地，要求用一些1*L或L*1的木板覆盖所有的泥地，要求用的木板的数目尽量少。(n,m=50)例如

18、4 4*.*. 1. 2. .* . 333*. 444. . *. . . 2. 例题3 spoj282抽取行，对于每行的每个连通块，将其标号xi。抽取列，对于每列的每个连通块，将其标号yi。如果行连通块xi与列连通块yj有公共泥地，那么就添加边(xi,yj)问题就转化为求一个点集V，当每条边的两端都至少有一个点V时(即所有泥地都被覆盖了)，这时|V|就是答案。即求最小的V(最小覆盖)例题4 spoj373给出n张卡片，每张卡片上有1n的数字。给出m个变换(x,y)，表示可以将写有x的卡片换成y或将写有y的卡片换成x。问你最少经过多少次置换，可以将这n张卡片换成1到n的排列。(n,m=500

19、)4n 答案：312 2 2 2 m2 3 3 4 例题4 spoj373求出每个卡片变换到i，(1=i=n)的费用。用BFS即可。构造二分图G，左半边的每个点代表一张卡片x，右边的每个点代表一个数y。边权即为卡片x变换为y的费用。最佳匹配。例题5 mipt110给出一个图的邻接矩阵(下三角矩阵)，aij表示i和j之间的最短路，问这个矩阵是否可以对应一棵树。如果可以，输出树上的边。5 YES 0 0 11 0 1 22 1 0 2 33 2 1 0 -1 -1 -1 -1 0 N=500例题5 mipt110题目要求判断原图是否是一棵树因此如果原图是树，那么只存在一种生成树。先用Prim求出一

20、棵生成树，然后在这个树上求出任意两点间的最短距离。然后判断最短路图是否与原图一致即可。因为是树上求最短距离，使用BFS即可。O(N2)例题6 mipt106给出一个图，要求这个图中的一个极大导出子图，使得这个极大导出子图包含一个特定的点k，并且所有点中最小的度尽量大。优先保证度的最小值最大，如果有多解则要求子图包含的点尽量多。M=4000例题6 mipt106最小最大问题或最大最小问题一般采用二分。这题中，我们二分度的最小值d。假设原图中不存在度小于d的点i，那么该图就是个满足条件的图。如果存在，则将这个点删去，继续寻找。可以使用BFS，使得维护子图的复杂度变成O(M)例题7 sgu326给定

21、了一些队已经比赛的成绩，以及他们之间剩余的比赛场次，你需要安排剩下队伍之间问第一个队有没有取胜希望（胜利数达到所有队中最大）。 (n=20)3 队伍数n1 2 2 已经胜利的场数1 1 1还要比的场数0 0 0 n*n的矩阵，表示任意两个队之0 0 0 间还要比赛的场次。0 0 0 YES例题7 sgu326首先剩余的跟队伍1的比赛肯定都让队伍1赢。于是，题目就成了安排剩下的n-1队伍之间的胜场关系。构造网络G，设xi表示所有的比赛，yi表示所有的队伍。xi向对应的两只队伍yi和yj连边,边权为这两只队伍还需比赛的场数 s向xi连边,边权为该比赛的场数,yi向t连边,边权为对应队伍至多还能赢的

22、场数然后求最大流.最后只需要把所有连向t的的流量加起来.看所有本赛区队伍间的比赛总数(不包括1队)是否和这些流量和相等.相等就是yes,否则就是no例题7 CERC2005给n个字母串，选择若干个串排成一个圈，使得总长度/总个数最大。两个串能排到一起的条件是第1个串的最后两个字母等于第2个串的头两个字母。N=2003 intercommunicationalalkylbenzenesulfonatetetraiodophenolphthalein 答案21.66例题7 CERC2005构造图G，将每个串对应成图G中的一个结点，如果x串能接上y串，那么连一条边(x,y)，权为len(x)-2。问

23、题变成找一个环，使得(w+2)/l尽量大，其中w为环上的权值和，l为环上点的个数。设该环上各边的权值和为wi，那么有(w1+w2+wl+2)/=answ1+w2+wl+2=l*ans(w1-ans)+(w2-ans)+(wl-ans)+2=0因此，我们只需要二分答案ans，构造图G，将G中的所有边(x,y)的权减去ans添加到图G中，求图G中是否存在正环即可。(即用SPFA求最长路，若某个点迭代的次数大于n，那么肯定存在正环，否则不存在)。例题8特殊的哈密尔顿回路问题:给出一张无向简单图，保证这张图中每个点的度不小于N/2+1。(n=n。因为m是一条极长路，所以m1只能与m中的顶点邻接。同理m

24、l只能与m中的顶点邻接。只有m-r个符合条件的mi使得m1不与mi邻接只有m-1-s个符合条件的mi使得mi+1不与ml邻接(m-r)+(m-1-s)=2m-1-(r+s)m因此至少存在一个点使得m1与mi+1相邻，mi与ml相邻。例题9有n个王子和n个公主，他们之间已经一一配对了。每个王子都有若干个后选的配对的公主，但是他喜欢的公主只有一个(不一定是配对上的那个)。国王决定满足一个王子的愿望娶上喜欢的公主，但是又不能让别的王子没有公主娶。问有几个王子的愿望可能被满足。N=100000, m=200000例题9硬搞，每次枚举一个王子让他完成愿望然后做二分图匹配，O(N2M)每次并不需要重新做一次匹配