求解强分图的算法综述

求解强分图的算法综述

图的连通性是图论中一个非常重要的问题，其应用也非常广泛。比如在操作系统中检测和纠正“死锁”状态,就需要识别图中是否包含多于一个结点的强分图。由文献可知,有向图有三个分图:强分图、单向分图和弱分图,有向图的分图问题都是从有向图的顶点集合V中,选取V的子集并满足某种连通性质的最大子图。很多图论的专著(如等)中都只是给出了有向图的三个分图定义,而没有提到各个分图的求法。文献都给出了求解强分图的方法。文献还论述了求解单向分图的算法,不过算法效率较低。弱分图的求解可以转为无向图的连通性来研究,所以求解相对简单。本文总结了强分图的现有的求解算法,主要是总结了算法实现的基本技术和特点;通过论述求解单侧分图和相应无向图的团问题的等价性,提出了求解单侧分图问题是NP问题的观点;最后又阐述了求解弱分图的方法,并给出了一个具体的实现算法。本文第1节给出了相关概念的定义;.第2节总结了求解强分图的算法;第3论述了求解单侧分图的问题是NP问题;第4节阐述了求解弱分图的算法。1有向图和最大团下面的关于图的定义和定理在很多图论的专著(如等)中都提及:定义1在有向图G中,若略去弧的方向,G成为连通的无向图,则G是弱连通的;如果任何一对结点间,至少一个结点到另一个结点是可达的,则G是单向连通的;如果任何一对结点两者间是相互可达的,则G强连通的。定义2在有向图G中,设Gˊ是G的子图,若(1)设Gˊ是强连通的(单向连通的,弱连通的);(2)G中没有包含Gˊ的更大的子图是强连通的(单向连通的,弱连通的),则称Gˊ是G的强分图(单向分图和弱分图)。定理1在有向图中,它的每一个结点位于且只位于一个强分图中。定义3设G=<V,E>是一个简单图,它有n个结点V={v1,v2,…,vn},则n阶方阵A(G)=(aij)称为G的邻接矩阵。其中,如果vi和vj邻接(i≠j),则aij=1,否则aij=0。定义4令G=<V,E>是一个简单有向图,|V|=n,假定G的结点已编序,即V={v1,v2,…,vn},定义一个n×n可达矩阵P=(pij)。其中,如果vi和vj至少存在一条路,则pij=1;如果vi和vj不存在路,则pij=0。可达性矩阵表明了图中任意两个结点间是否至少存在以及在任何结点上是否存在回路。一般地讲,可由图G的邻接矩阵A得到可达性矩阵P,即令Bn=A+A2+…+An,再从Bn中将不为0的元素改换为1,而为零的元素不变,这个改换的矩阵即为可达性矩阵P。定义5对于给定无向图G=(V,E),团是指图G的顶点集V的一个子集,使得其导出子图是完全图,即任何两个不同结点间有边相连。如果一个团不是任何一个其他团的子集,则该团为极大团。顶点数最多的团称为G的最大团。最大团一定是极大团,极大团一定是团,反之则不一定成立,求解最大团时需能遍历到各个极大团,最大团问题是NP完全问题。2强块分割算法的总结从所周知,求一个有向图的强分图的算法早已有之。本文从所使用的技术不同,将求解强分图的算法分为两类:(1)算法的时间复杂度在文献中给出的基于深度优先(DFS)遍历技术求强分图的算法,其时间复杂度是O(|E|),算法的详细描述也可以见文献,文献对基于深度优先(DFS)遍历技术进行了一定的改进,不过算法时间复杂度不变。(2)i、k之间的相互关系文献都提出了用可达矩阵来求解强分图,因为通过可达矩阵可以直接判断图中任意两点是否相互可达,由定理能够知道强分图的传递性,即结点j,k都和i相互可达,那么j,k也相互可达。所以基于可达矩阵方法来求强分图十分简单,无需使用DFS技术,时间复杂度是O(n2)。不过基于可达矩阵的方法的最大缺点是需要从图的邻接矩阵得到其可达矩阵,而基于深度优先(DFS)技术在求解强分图时一般基于邻接矩阵即可。尽管文献都有求可达矩阵的方法,不过当问题规模n较大时,求解可达矩阵的计算量是很大的。3两间的连通模式由定义可知,求解单向分图的问题比强分图问题要复杂,因为他们的性质不同。一个结点可能属于多个单向分图,而单向分图也无传递性,即结点j,k都和i单向连通,而j,k可能不连通。如果结点i有x个邻接点,那么包含i的单向分图也可能有x个。因为在有向图G=<V,E>中判断两点间是否单向连通是复杂的,因为需要判断两点间是否至少存在一条路。现将求解有向图G中的单向分图问题进行等价转化:设有一个简单无向图G=(V,E),其中V=V,且e=(i,j)∈Eˊ是Gˊ中两个不同结点间的任一条边,当且仅当i和j在G中是单向连通的。从Gˊ的定义中,可以看到两点间有一条无向边当且仅当两点是单向连通的,因为是求G的单向分图,这里只是关心两点间是否单向连通,而不考虑Gˊ中边的方向问题。Gˊ相当于G的可达矩阵,在Gˊ中判断两点间是否单向连通的是方便的,只需判断两点间是否有边,在图的邻接矩阵中判断两点间是否有边要比判断两点间是否有路简单得多。由Gˊ的定义可以证明:G=(V,E)中的一个极大团(由顶点集Vm导出的子图)当且仅当由Vm在G=<V,E>中所导出的子图是一个单向分图。证明:设由顶点集Vm在G中所导出的子图是一个单向分图,所以对于Vm中的任意两不同结点i,j是单向连通的,由单向分图的定义可知,在V中,不存在不属于Vm的任一个结点k,使得k和Vm中的任一结点都单向连通。由Gˊ的定义可知,VmG,且Vm中的任意两不同结点i,j都有一条无向边,所以由Vm在Gˊ所导出的子图是团(完全图),并且该团是Gˊ中的一个极大团。因为假设该团不是Gˊ的极大团,那么在Vˊ中一定可以找到一个不属于Vm的顶点k,使得k和Vm中任何一个顶点都有边,即k和Vm中任何一个顶点在G中都单向连通,所以k可以添加到Vm中而不影响Vm所导出子图的单向连通性,但是这和顶点集Vm在G中所导出的子图是一个单向分图是相矛盾的,所以假设不成立,所以由Vm在Gˊ所导出的子图是极大团。(2)时间复杂度分析由充分性的证明,同理可证必要性,在此不再赘述。由上面的证明可知,在G中求解所有的单向分图,就是等价于在Gˊ中找到所有的极大团,因为最大团的问题是NP问题,所以求解一个有向图G的所有的单向分图问题是个NP问题,因此尽管文献提出基于可达矩阵方法来求解单向分图的算法,其时间复杂度却是指数阶的。虽然求解有向图的单向分图问题是NP问题,但是仍然可以参考求最大团的算法(如文献等)来求有向图的单向分图。4viched[n]提供由定义可知,求解弱分图的问题可以转化到无向图的连通问题上来研究,即将原图的每一个有向边都可以看成无向边,从任意结点出发进行深度优先(DFS)遍历,便可得到原图的一个极大子图且是弱连通的,从各个结点出发进行遍历,便可得到原图的各个弱分图。因为在无向图中,一个结点只能属于一个连通分支,即一个结点只能属于一个弱分图,所以为了避免重复搜索,在算法实现时可以设置一个辅助Visited[n]数组,它的初始值为“假”,一旦顶点Vi属于当前的弱分图,便置Visited[i]为真。以下是算法的主要代码:求解弱分图的算法的时间复杂度显然是O(n2)5求解单向分图的理论图的连通性问题是图论中一个非常重要的问题。