图论总结(超强大)解读

1、ADN.cnlibrarysummary图论总结2022323 /33 /33图论GraphTheory定义与术语DefinitionandGlossary图与网络GraphandNetwork图的术语GlossaryofGraph路径与回路PathandCycle连通性Connectivity图论中特殊的集合Setsingraph匹配Matching树Tree组合优化Combinatorialoptimization图的表示Expressionsofgraph邻接矩阵Adjacencymatrix关联矩阵Incidencematrix邻接表Adjacencylist弧表Arclist星形表示

2、Star图的遍历Travelingingraph深度优先搜索Depthfirstsearch(DFS)概念求无向连通图中的桥Findingbridgesinundirectedgraph广度优先搜索Breadthfirstsearch(BFS)拓扑排序Topologicalsort路径与回路Pathsandcircuits1.5.1.欧拉路径或回路Eulerianpath.无向图.有向图.混合图.无权图Unweighted.有权图Weighed中国邮路问题TheChinesepostproblemHamiltonianCycle哈氏路径与回路无权图Unweighted有权图Weighed旅行商

3、问题Thetravellingsalesmanproblem网络优化Networkoptimization最小生成树Minimumspanningtrees基本算法BasicalgorithmsPrimKruskalSollin(Boruvka)扩展模型Extendedmodels度限制生成树Minimumdegree-boundedspanningtreesk小生成树Thekminimumspanningtreeproblem(k-MST)最短路Shortestpaths单源最短路Single-sourceshortestpaths基本算法BasicalgorithmsDijkstraBel

4、lman-FordShortestpathfasteralgorithm(SPFA)应用Applications差分约束系统Systemofdifferenceconstraints有向无环图上的最短路ShortestpathsinDAG所有顶点对间最短路All-pairsshortestpaths基本算法BasicalgorithmsFloyd-WarshallJohnson网络流Flownetwork最大流MaximumflowFord-FulkersonmethodEdmonds-KarpalgorithmMinimumlengthpathMaximumcapabilitypath预流推

5、进算法PreflowpushmethodPush-relabelRelabel-to-front基本算法BasicalgorithmsDinicmethod扩展模型Extendedmodels.2.1.有上下界的流问题最小费用流Minimumcostflow找最小费用路Findingminimumcostpath找负权圈Findingnegativecircle网络单纯形Networksimplexalgorithm匹配Matching二分图BipartiteGraph无权图-匈牙利算法Unweighted-HopcroftandKarpalgorithm带权图-KM算法WeightedKuh

6、n-Munkres(KM)algorithm一般图GeneralGraph无权图-带花树算法Unweighted-Blossom(Edmonds)1.图论GraphTheory定义与术语DefinitionandGlossary图与网络GraphandNetwork二元组(V,E)称为图(graph)。V为结点(node)或顶点(vertex)集。E为V中结点之间的边的集合。点对(u,v)称为边(edge)或称弧(arc),其中u,veV，称u,v是相邻的(adjacent)，称u,v与边(u,v)相关联(incident)或相邻。若边的点对(u,v)有序则称为有向(directed)边，其中

7、u称为头(head),v称为尾(tail)。所形成的图称有向图(directedgraph)。为对于u来说(u,v)是出边(outgoingarc)；对于v来说(u,v)是入边(incomingarc)。反之，若边的点对无序则称为无向(undirected)边，所形成的图称无向图(undirectedgraph)。若图的边有一个权值(weight)，贝V称为赋权边，所形成的图称赋权图(weightedgraph)或网络(network)。用三元组G(V,E,W)表示网络。其中W表示权集，它的元素与边集E对应。满足|E1Y(G)。VV定理：连通图中，V是点覆盖，则V是支配集。极小点覆盖不一定是极

8、小支配集。支配集不一定是点覆盖。定理：无向图G无孤立点，V是(极，最小)点覆盖，充要于V-V是(极，最大)独立集。a(G)+0(G)=|V|。VV定理:无向图G,V是G的(极,最大)团,充要于V是G的(极,最大)独立集。co(G)=0v(G)。由上述定理知，a(G),P(G),讥G)三者互相确定，但都是NPC的。但是二分图中，VV点覆盖数是匹配数。M是匹配，W是边覆盖，N是点覆盖，Y是点独立集。定理：无向图G无孤立点，|M|=|N|,|Y|W(v,w)，则d(w)=W(v,w)，转2。这里的d可以用优先队列实现，需用到删除最小(DeleteMin)与减值(DecreaseKey)的操作。假设用

9、FibonacciHeap实现(删除最小O(logn)，减值O)，算法复杂度：O(nlogn+m)。Kruskal基本思想：就是维护一个生成森林。每次将一条权最小的边加入子图T中，并保证不形成圈。如果当前弧加入后不形成圈，则加入这条弧，如果当前弧加入后会形成圈，则不加入这条弧，并考虑下一条弧。算法：T=0,i=0，将E中的边按权从小到大排序，W(e)W(e)m，结束，此时G没有生成树；否则判断Tue是否含圈，是则转2,否则转3。iT=Tue。若ITI=N，结束，此时T为G的最小生成树。i分离集合(disjointset)，可用并查集实现。由于排序是O(mlogm)的。所以复杂度为O(mlogm

10、+ma(n)。Sollin(Boruvka)基本思想：前面介绍的两种算法的综合。每次迭代同时扩展多棵子树，直到得到最小生成树T。算法：对于所有veV,G=v。T=0。v若|T|=N，结束，此时T为G的最小生成树；否则，对于T中所有的子树集合G，计算它v的边割G,G中的最小弧e*(有的书称连接两个连通分量的最小弧“安全边”)。vvv对T中所有子树集合G及其边割最小弧e*=(p,q)，将G与q所在的子树集合合并。vvvT=Tue*。转2。v由于每次循环迭代时，每棵树都会合并成一棵较大的子树，因此每次循环迭代都会使子树的数量至少减少一半，或者说第i次迭代每个分量大小至少为2i。所以，循环迭代的总次数

11、为O(logn)。每次循环迭代所需要的计算时间：对于第2步，每次检查所有边O(m)，去更新每个连通分量的最小弧；对于第3步，合并O(n/2i)个子树。所以总的复杂度为O(mlogn)。RindSafhEdghs(VE):Bdruvka(YE):T=(V,0whileFhasmorethanonecamponentdiooseleadersusingDFSFindSabEdgbsCYE)foreadileadervaddsafe(v)tcFforeach,leadervsafe(v)coforcacLedge(u,)Euleader(u)vleader(u)if辽爭方ifwfsafefiL)sa

12、fe(u)if)safe(5)1(叫诃1612扩展模型Extendedmodels16121度限制生成树Minimumdegree-boundedspanningtrees由于这个问题是NP-Hard的，一般用搜索算法解决。本文就只讨论一种特殊多项式情况:单点度限制(onenodedegreebounded)。把度限制的点记为v，满足度限制deg(v)k。一种贪心的思路：在最小生成树T的基础00上，通过添删边来改造树，使之逐渐满足度限制条件。算法：求图的最小生成树T。若v已满足度限制，结束；否则转3。0对于删去v后的每一个连通分支T(为一棵树)，求添加边割T,T-v中的最小弧，0iii0删除边

13、割T,v0里的最大弧后的生成树中的边权和最小的一个。更新最小生成树T。i转2。第3步，v的度少1。0习题：NOI2005小H的聚会16122k小生成树Thekminimumspanningtreeproblem(k-MST)生成树T删除一条边f并加入一条新边e的操作称为交换。若交换后的图仍是一颗树，则此交换称为可行交换。若生成树T可通过一次交换成为生成树T,则称它们互为邻树。对于生成树集合S,生成树T,若T不在S中，且在S中存在某生成树是T的邻树，称为T为S的邻树。定理：设T,T,T为图的前k小生成树，则生成图集合T,T的邻树中的边权和12k12k最小者可作为第k+1小生成树(可能有边权和相同

14、的情况)。按这个定理设计算法，很难得到有满意的时间复杂度的算法。下面讨论一个特例：次小生成树(ThesecondMST,2-MST)基本思想：枚举最小生成树T的每一个邻树，即枚举被添加与被删除的边。由于在树中添加一条边(u,v)(u,v)电T)，一定形成了一个环，环是由(u,v)与从u到v的生成树上的唯一路径(记为P(u,v)组成的。所以被删除的边一定在P(u,v)上。由于要求最小边权和，所以被删除的边一定是P(u,v)上最小者，其权值记为f(u,v):f(u,v)=minw(e)|eeP(u,v)。算法：求图的最小生成树T。次小生成树T的权值的最小值w(T)=x。以每个结点为根r，DFS遍历

15、树。在遍历过程中求出f(r,v)|veV，用w(T)+w(r,v)-f(r,v)更新次小生成树的权值的最小值w(T)。输出w(T)。算法复杂度的瓶颈在第2步O(n2)，故总算法复杂度为O(n2)。习题：Ural1416Confidential最短路Shortestpaths单源最短路Single-sourceshortestpaths令s为起点，t为终点。单源最短路问题定义为：对于网络G=(V,E,W)，寻找s到t的一条简单路径，使得路径上的所有边权和最少。令d(v)为s到v的最短路长度上界。单源最短路问题的规划模型如下：mind(t)s.t.d(v)d(u)+w(u,v)(u,v)eEd(s

16、)=0对于只含正有向圈的连通有向网络，从起点s到任一顶点j都存在最短路，它们构成以起点s为根的树形图(称为最短路树(TreeofShortestPaths)。当某弧(u,v)位于最短路上时,一定有d(v)-d(u)=w(u,v)。所以最短路的长度可以由Bellman方程(最短路方程)唯一确定:d(s)二0d(v)二mind(u)+w(u,v)u丰v在规划模型与最短路方程中都出现了d(v)d(u)+w(u,v)，则改进d(v)=d(u)+w(u,v)。直观的讲，就是路径最后通过(u,v)，使得s到v的距离比原来s到v的方案的距离短。松弛操作是最短路算法求解的基本方式。最短路算法求解过程中的标号规

17、定：对于V中每一个顶点v,设置一个标号：距离标号d(v),记录的是从起点到该顶点的最短路长度的上界；再设置一个是前趋pred(v)，记录的是当起点s到该顶点v的一条路长取到该上界时，该条路中顶点v前面的那个直接前趋。算法通过不断修改这些标号，进行迭代计算。当算法结束时，距离标号表示的是从起点到该顶点的最短路长度。标号设定算法(Label-Setting):在通过迭代过程对标号进行逐步修正的过程中，每次迭代将一个顶点从临时标号集合中移入永久标号集合中。标号修正算法(Label-Correcting)：每次迭代时并不一定将任何顶点标号从临时标号转变为永久标号，只是对临时标号进行一次修正，所有顶点标

18、号仍然都是临时标号；只有在所有迭代终止时，所有顶点标号同时转变为永久标号。最长路问题可以转化为最短路问题，把弧上的费用反号即可。基本算法BasicalgorithmsDijkstra采用了标号设定算法(Label-Setting)。在迭代进行计算的过程中，所有顶点实际上被分成了两类：一类是离起点较近的顶点，它们的距离标号表示的是从点s到该顶点的最短路长度,因此其标号不会在以后的迭代中再被改变(称为永久标号)；一类是离起点较远的顶点，它们的距离标号表示的只是从点到该顶点的最短路长度的上界，因此其标号还可能会在以后的迭代中再被改变(称为临时标号)。下文称永久标号为已检查。算法：d(s)=0，d(v

19、)=8,(v丰s)，已检查U=0取未检查的u，即uU，使得d(u)最小。若u取不到，即d(u)=g则结束；否则标记为已检查，即U=Uuu。枚举所有的u的临边(u,v)，满足v未检查，即v笑U。松弛(u,v)，即若d(v)d(u)+w(u,v)，则改进d(v)=d(u)+w(u,v),pred(v)=u。转2。这里的d可以用优先队列实现，需用到删除最小(DeleteMin)与减值(DecreaseKey)的操作。假设用FibonacciHeap实现(删除最小O(logn)，减值O(l),则算法复杂度：O(nlogn+m)。若用BinaryHeap则O(n+m)logn)。适用范围：非负权图。Be

20、llman-Ford采用了标号修正算法(Label-Correcting)。本质就是用迭代法(动态规划)解Bellman-Ford方程：d(l)(s)=0,d(1)(v)=w(s,v),v丰sd(k+1)(v)=mind(k)(v),mind(k)(u)+w(u,v),u,vgV,k=1,2,，n一2u工vd(k)(v)表示s到V的且边数不超过k条时的最短路路长。下面用归纳法证明：k=1显然成立。假设对k成立，下面考虑k+1的情况.从起点s到顶点V且所经过的弧数不超过k+1条时的最短路有两种可能：含有不超过k条弧，即d(k)(v)；含有k+1条弧，即mind(k)(u)+w(u,v)。u工v由

21、于第k+1次迭代过程中，不会影响k次的迭代结果，d用O(n)的空间即可。算法：d(s)=0，d(v)=8,(v主s)松弛所有边(u,v)，即若d(v)d(u)+w(u,v)，则改进d(v)=d(u)+w(u,v)，pred(v)=u。若没有边被松弛，则算法结束。若2的迭代次数超过n-1，则有负权圈，结束；否则转2继续迭代。可以证明算法一定在n-1步迭代后收敛；否则一定有负权圈。所以算法复杂度为O(nm)。适用范围：一般图。.1.2.1.Shortestpathfasteralgorithm(SPFA)SPFA其实就是Bellman-Ford的一种队列实现，减少了冗余，即松驰的边至少不会以一个d

22、为a的点为起点。算法：队列Q=s，d(s)=0，d(v)=8,(v丰s)取出队头u，枚举所有的u的临边(u,v)。若d(v)d(u)+w(u,v)，则改进d(v)=d(u)+w(u,v),pred(v)=u,由于d(v)减少了，v可能在以后改进其他的点，所以若v不在Q中，则将v入队。一直迭代2，直到队列Q为空(正常结束)，或有的点的入队次数=n(含有负圈)。由于点可能多次入队，但队列中同时不会超过n个点。所以用一个长度为n的循环队列来实现这个队。SPFA在形式上和宽度优先搜索非常类似，不同的是宽度优先搜索中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，

23、也就是一个点改进过其它的点之后，过了一段时间可能本身被改进，于是再次用来改进其它的点，这样反复迭代下去。设一个点用来作为迭代点对其它点进行改进的平均次数为k有办法证明对于通常的(不含负圈，较稀疏)情况,k在2左右。算法复杂度理论上同Bellman-Ford，O(nm)，但实际上却是O(km)。一般用于找负圈(效率高于Bellman-Ford)，稀疏图的最短路。习题：Ural1254DieHard(可斜走的网格最短路)。应用Applications差分约束系统Systemofdifferenceconstraints差分约束系统：求解n个未知数x，满足m个不等式：ix一xb,1i,jn,1kmj

24、ik若描述为线形规划模型：AxB。mxn矩阵A每行含一个1一个-1，其他都是0。如线形规划模型(10一10、(-2010-1(x)14100-11x5201一10 x-3-10013lxj421一100丿i3丿等价于x一x一2TOC o 1-5 h z13x一x424x一x514x一x一323x一x241x一x312注意到单源最短路模型中的。d(v)d(u)+w(u,v),即d(v)-d(u)w(u,v)。很像差分约束系统模型。于是可以构造一个有向网络G=(V,E,W),称为约束图(constraintsgraph)。V=v,v,v，,v。E=(v,v)|x一xb+(v,v)11inTOC o

25、 1-5 h z012nijjik0iW：w(i,j)=b|x-xd(u)+w(u,v),则改进d(v)=d(u)+w(u,v)，pred(v)=u。转2。复杂度：O(m)所有顶点对间最短路All-pairsshortestpaths基本算法BasicalgorithmsFloyd-Warshall本质就是用迭代法(动态规划)：d(1)(u,u)=0,ugVd(1)(u,v)=w(u,v),u,vgVd(k+1)(u,v)=mind(k)(u,v),d(k)(u,k)+d(k)(k,v),u,vgV,k=1,2，n-1d(k)(u,v)表示u到v的不经过k,k+1,n结点(除u,v外)时，从u

26、,v的最短路长。下面用归纳法证明：k=1显然成立。假设对k成立，下面考虑k+1的情况；从u到v且不通过k+1,n节点的最短路有两种可能：(1)不经过k节点,即为d(k)(u,v)；(2)经过k节点,即为d(k)(u,k)+d(k)(k,v)。由于第k+1次迭代过程中，不会影响k次的迭代结果，d用O(n2)的空间即可。二维数组p(u,v),记录u到V,最后经过哪个k的迭代。算法：k=1，对于所有u,v，d(u,v)=w(u,v),p(u,v)=vk=k+1，对于所有u,v,若d(u,v)d(u,k)+d(k,v)，则d(u,v)=d(u,k)+d(k,v)，p(u,v)=k。若发现某个节点u使得

27、d(k)(u,u)h(v)，所以w(u,v)=w(u,v)+h(u)-h(v)0。令路径p=(v,v，,v)，贝912ni-1iw(p)=工w(v,v)=w(v,v)+h(v)-h(v)i-1ii-1ii=2i=2=w(p)+h(v)一h(v)1kw(p)只与w(p)以及首尾的标号h有关，不影响w(p)的决策。所以w(p)是最短路长当且仅当W(p)是最短路长，且不影响最短路p。参考文献：125.3Johnsonsalgorithmforsparsegraphs，IntroductiontoAlgorithms，MITPress网络流Flownetwork最大流Maximumflow在有向无权图

28、G(V,E,C)中，其中C为每条边的容量(capability)c(u,v),再给每条边赋予个流值(flow)f(u,v)，并规定源s和汇t。最大流问题的数学模型描述如下:(1)max工f(s,v)veVs.t.f(u,v)c(u,v)u,veVf(u,v)=-f(v,u)u,veV工f(u,v)=0ueV-s,tveV其中(2)f(u,v)V,那么我们就有一些流量需要在u继续往上进行处理，使用刚才在V点同样的办法，直到一直处理到了S，一路上肯定是不会出现什么障碍的。然后我们将c从V运送到t,我们在构造这个层次图的时候很容易就可以保证所有从S出发的路径都会在t终结，这样就好办了，使用上面同样的

29、办法，只是处理的方向是从V到t了。这样，我们刚才处理的过程就容易得到下面的下面所谓的性质了。*)上面的算法给了我们一个可以在0(mn)的时间内充满这个层次图的算法，下面进一步分析。为了得到我们需要的界，我们需要这样一个性质：当我们在上面的对每个新的顶点V执行算法的步骤中，保证对每条边我们只检查一次，对其做完所有需要的操作之后才会去做下一条边。这点意味着，我们可以把运行时间分成两个部分来考虑：a)花在被充满的边上的时间b)花在没有被充满的边上的时间。对于a),因为我们每次充满一条边就会把它从图中删除，所以a)的总时间是0(m)。因此我们的时间主要由b)来决定，而b)对应的边在对每个新的顶点v的执行过程中至多出现0(n)次，因此总的时间是0(22)。而我们可以在0(m)的时间内重新计算新的层次图，所以我们就可以在O(nm+nnA2)时间完成整个算法，也就是0(3)。扩展模型Extendedmodels有上下界的流问题问题模型：给定一个加权的有向图G(V,E,B,C)，满足:容量限制条件：b(u,v)f(u,v)a的弧(t,maxmaxs),则从在这个改造后的图中一定没有无源汇的可行流：否则将这个可行流中的弧(t,s)除去，就