为了确保生成无向图割集的递归收缩算法的正确性和稳定性，对算法中种子顶点是支点的情形进行了分析，并采取了新的处理策略。分析了支点具有一个非可吸簇的情形，引进附加吸入的概念，修正了种子顶点的BFSO值取值规则，解决了现有算法可能遗漏割集的问题。针对支点没有非可吸簇的情形，给出了一个新的处理策略，解决了现有算法在某些特殊输入条件下效率不高的问题，在理论上分析了新处理策略的有效性，并做了相应的实验比较，理论分析和实验比较均表明：新的处理策略采用提高了递归收缩算法的稳定性。
56 2011,47(19) Computer Engineering and Applications计算机工程与应用 留了可吸点,防止了割集的遗漏。为了进一步明确本文做法, 1(1) 1(1) 本文区分两种吸入,并明确种子顶点的BFSO值在不同情况下 0,414 0,5(5) 的取值问题: 正常入:指种子顶点在满足BFSO值限制的情况下,吸 2(2)3(3) 5(5)2(2 3(3) 入一个邻接顶点,此时种子顶点的BFSO值改为该邻接顶点的 0,1,4(4):5 3(3)4(4) BFSO值。 2(2)0,1,s(5) 1(1) 附带吸入:指种子顶点在符合某种特定条件下(如支点情 0(0 形Ⅱ),次性吸入其可吸簇(部分或全部,出现支点情形Ⅱ时 22)3)3(3+4(4) n 2(2) 5(5) 是全部)。这种吸入通常是伴随一次正常吸入发生的,故称附 带吸入,本文规定附带吸入不改变种子顶点的BFSO值。 0,1,4(4) 3(3)4(4) 本文将附带吸入独立成一个单独的过程,算法如图2所 5(5)212)0,1(1) a 示,算法中不包含改变种子顶点的BFSO值的处理。有了图2 5(5) 的附带吸入算法,图4所示的算法删除12-23行后就是修正后 2(2)3(3) 0,2(2)(1)0,3(3) 3(3)4(4) 1(1) 的递归收缩算法,算法的整体流程简明、清晰。为了叙述方 5(5) 便,称图4所示的算法删除12~23行后得到的算法为算法I。 0,1,2(2) 2(2)4(4) 3(3)4(4) 5(5)0,1,3(3) (p 输入:图G,种子顶点ν,顶点列表F,可吸簇的顶点列表H 5(5) 0,3(3):4 输出:经过边收缩处理的图G,新的顶点列表F; 3(3)4(4) 子算法侧程: contract cdcs(G,seed,F,H){ (2)中4(4) 1(1)1(1 将Ⅰ中的顶点按BFSO值升序排序 (k) 0,2(2):3,4,5 2 foreach(v'in H)( 0,1,2,5(5)0,1,2,3(3)01,2,4(4) 2(2) 1.3(3):4.5 在G中收缩边(v,v);/吸入v 5(5) 将v加入顶点列表F; 3(3) 2(2) 3(3)4(4) 4(4) (h) (1) (j) (d) 图2种子顶点吸入一组可吸簇的算法 0,1,2,4(4):5 0,1,2,3,4(4 423算法的执行实例 5(5) 对于图3(a)所示的无向图,图3是算法I求解其所有割集 33)b 4(4) (i 的执行过程,执行过程以类似递归树的形式描述。最初的种 0,1,2,3,4,5(5) g 子顶点是顶点0,算法共处理了22个 EC RCA图,其中非平凡 (f) 的有21个,但只生成9个割集(图中用下划线标出),树的树高 图3算法I的执行实例 为6。种子顶点中冒号后面的顶点是附带吸入的结果,对种子3针对支点情形Ⅲ采用“劈图”处理策略 顶点的BFSO值没有影响。 图4给出加入“劈图”处理策略的递归收缩算法(算法I)。 输入:图G,种子顶点v 19 调用 contract edges(G,v,H,D)生成新的G和新的H 输出:图G的割集列表S(v) find all cutsets(G, v, H) 初始化:S(v)=,顶点列表F={v; 求解各个顶点的BFS顺序值(以v为根的树表示); return; 递归例程: find al cutsets(G,ν,F){ 1i(顶点v是外部顶点){ 2if(S(v)个包含F将顶点列表F加入S(v); 25} 3}else{/v为割点(支点 26求解顶点ν的邻接点集合(v 4求出ν的非可吸簇数量 count 1a和可吸簇集合C(v) 从f(ν)中移除属于F的顶点 5i( count 1a>1){∥支点v的非可吸收簇多于1个 28从r(v)中移除BFS顺序值小于v的RFS顺序值的顶点; 6 retirn 29if(r(v)为空) 7} else if( count 1a=1){/支点v只有1个非可吸收簇 求出C(v)中所有簇的顶点的集合H 31) else i 9调用 contract edges(G,v,F,H)生成新的G和新的F; for all vertices u of iv)do{∥循环 find all cutsets( G, v, F) 拷贝顶点列表F到临时顶点列表H; 11 cturn 34 收缩边(v,u)生成G/uv; 12}lse{/支点v没有非可吸牧簇 将顶点u加入l 13求出C(v)中所有簇的顶点的集合K及可吸簇数k; 设置Gmv的收缩顶点g为新的种子顶点v; 求种子顶点邻接顶点数l; if(Gluv的顶点数大于1) find all cutsets(Guv,v,H); 5if(-2>k){ for all clusters C of C( v) do i 39} 将K中不属于C的顶点加入顶点列表 18 拷贝顶点列表F到临时顶点列表H; 图4加入“劈图”处理处理策略的递归收缩算法(算法Ⅱ 梁勇强:递归收缩算法中支点的欠理策略研究 2011,47(19) 5 3.Ⅰ现有算法存在效率不高的情形 I(1) 在理想的情况下, ERCA MC算法每生成一个 EC RCA 0(0) 图就得到一个割集,但通常情况下只有一部分的 EC RCA图 2(2) 5(5) 可以形成割集,无效的 EC RCA图越多,生成割集的平均代价 就越大,算法效率越差。 3(3)4(4) 如果算法过程较多地出现支点情形I,那么就会存在大 量的合法的 EC RCA图但不能形成割集(见图3的例子),导致 0(0):4,50(0):1,2,3 算法效率较低。 l(1) 2(2) 5(5 32改进措施的提出 对于上面提到的问题,为了确保递归收缩算法的效率,本 2(2) ,3(3):4,53(3) 4(4) 文采用下面的处理策略,以加速支点变成非割点 (i) (b) 1(1) 4(4):1,2,3 设在 ERCA MC算法中,待处理的 EC RCA图是G/V,G/V 0,5(5):1,2,3 0,1(1):4,5 5(5) 的种子顶点是支点,且没有非可吸簇,种子顶点的所有可吸簇 0,2(2):4,52(2) (k) 的集合是{G,-1,2,…,k},那么对于每个G,=1,2,…,k,在 喜 G/V中运用附带吸入策略让种子顶点一次性吸入顶点集合 3(3) 4(4) 3(3) (m)0,4,5(5):1,2,3 551G)中顶点得到 EC RCA图GV0,显然GF0 (g) (1) 的种子顶点不是割点一一利用G/可生成割集,对GV0进 0,1,3(3):4,5 1(1) 0,1,2(2):4,5 行递归处理。为方便后面的叙述,称以上处理策略为“劈图” 处理策略。 0,2,3(3):4,5 2(2) 设在GV中种子顶点的邻接顶点数为l,本文规定只有 (h) 3(3) f) l-2≥k才采用“劈图”策略,具体理由见4.1.1.2节的分析部分。 33改进措施的正确性 0,1,2,3(3):4,5 按照文献[5],当种子顶点不是割点时,利用 EC RCA图可 生成一个割集,递归收缩算法的目的就是列举出种子顶点不 图5算法Ⅱ的执行实例 是割点的全部 EC RCA图,当要对算法进行修改时,只要种子 顶点不是割点的 EC RCA图不丟失,那么算法的修改就是正4“劈图”处理策略的有效性 确的。 41理论分析 4L.1“劈图”处理策略对算法时间复杂度的影响 继续前面的讨论,考虑 ERCA MC算法处理G/V得到的 影响递归收缩算法执行时间的因素主要有两个:(1)算法 任意 EC RCA图G/V1,VcV,如果G/的种子顶点不是割点 中出现的非平凡 EC RCA图数量(因为处理平凡的 EC RCA 则G的导出子图<P",P-F(G)-H必定连通,这样必定存在图只需一个判断操作即可,且数量不多);(2)附带吸入的次数 1≤≤k),使得Vc(G),即<P>是的某个可吸簇的导出子(附带吸入比正常吸入需要更多的时间)。 图,既然VcK(G),那么【1skmy(G∈H,即除G之 为方便分析比较,在出现附带吸入时,将此次附带吸入和 外,其余各个可吸簇已绎被吸入GH的种子顶点中。考虑采相应的正常吸入作为整体看待 用“劈图”处理策略的结果,附带吸入使得G。的种子顶点的...1减少了非平凡 EC RCA图的生成数量 (1)算法Ⅱ生成的非平凡 EC RCA图的唯一性 BFSO值比图中其他所有顶点都小,显然G也可以由G/V0 设待处理的 EC RCA图是G/,GV的种子顶点g是支 进行边收缩处理生成。G的任意性证明了采用改进措施没点,且支点没有非可吸簇,g的所有可吸簇的集合是G,=1, 有丢失种子顶点不是割点的EC_RCA图,改进措施是正确的。2,…,k},应用“劈图”处理策略得到的 EC RCA图的集合是 3.4改进后的算法描述 G/ 图4给出了加入“劈图”处理策略的算法的完整流程,其中 定理1设G/V算法Ⅱ处理G/V。生成的EC_RCA图,如 第12-23行是“劈图”处理策略的伪码。图中第9行和第19行果G不是平凡图,则G/在算法Ⅱ处理G/生成的过程中 调用了图2的子算法,生成新的 EC RCA图和相应的顶点列只出现一次。 表。为了叙述方便,称加入“劈图”处理策略的算法为算法Il 证明(1)处理任意G/V0,≠时不会生成GF 35算法I的执行实例 由于j≠1,根据“劈图”处理策略,GV生成的所有 对于图3(a)的无向图,图5是采用算法I求解其割集的执 EC RCA图的种子顶点对应的顶点集合一定包含G的所有顶 行过程,仍然以类似递归树的形式。比较图3可以发现算法I点,又由于G/V0不是平凡图,即G/V的种子顶点对应的顶点 处理了13个 EC RCA图,其中非平凡的 EC RCA图11个,少集合不可能包含G的所有顶点,说明处理GV0时不可能生 了5个,树的层数为4,比图3所示的树少2层 成G/V。 2011,47(19) Computer Engineering and Applications计算机工程与应用 2)处理G/v时不会重复生成G/" 状态5),将附带吸入和相应的正常吸入看作整体(状态2和3 设G/"是处理G时生成的任意非平儿 EC RCA图,看作过渡状态,可以不计),故算法Ⅱ只有状态1和状态4的 I是与处理G;O的过程对应的递树,下面证明在T中,只要 CRCA图,算法I中显然有状态的 EC RCA图(都可以生成 G/"’与G/V处J不同的位置,则G/V"≠G/V,分两种情况讨论: 割集),由于“劈图”减少了簇与簇之间的关联,因此算法Ⅱ中 状态4的 EC RCA图应当比算法I少。而从图6(b)可以看出 祖先 ①在T中,要么G是G的祖先,要么G是G的算法I中状态2不是过渡状态,不能忽略。 根据收缩过程,如果G/是G/V的祖先,则bcV,如 综合上面的讨论,再根据定理1可以得出结论:算法Ⅱ生 果GV是GT的祖先,则TcI",总之G/T0≠G/W 成的非平凡 EC RCA图的数量小于算法I。 ②在T中,GP不是G的祖先G/也不是G"的祖先4.1.12减少了附带吸入的次数 在T中,显然必定存在G0,使得G/v是G/V和Gr 设种子顶点的邻接顶点数为l,可吸簇数为k,则算法I在 该支点处引起l-2次附带吸入,算法Ⅱ在该支点处引起k次附 的共同祖先,且GV"的任何后代都不是G/和GT的共同带吸入,由于只有1-22k时才采用“劈图”处理策略,故算法Il 祖先。因为G0至少有GW和G两个后代,所以G在支点处附加吸入次数不会多丁算法1。而在后续的吸入中, 的种子顶点要么不是割点,要么是支点(割点)且支点没有非由于“劈图”减少了簇与簇之间的关联,因此出现支点的情形 可吸簇: 自然会减少,附带吸入相应也会减少。 如果G的种子顶点不是割点,则在T中必定存在以4.2“壁图”处理策略对算法空间复杂度的影响 G/的两个直接后代以G/V和G/V,使得G或者是 影响递归算法的空间复杂度的主要因素是递归树的高 GP本身,或者是GV的祖先,而G0)或者是G本身,度。算法1的递山树的层数为n,算法用了“劈图”处理策 或者是GP的祖先。设GV和G是由G0的种子顶略,由于一次收缩了更多的顶点,递归树的层数可能小于n, 所以算法执行过程中需要存储的 EC RCA图的数目减少了, 点分别吸入邻接顶点v和v生成的,设和分别是G/W和 算法∏的空间复杂度要比算法I小一些。 G0中的非可吸顶点构成的集合,根据BFSO值限制,≠413理论分析小结 V2,且V=和V2=最多只有一个成立,不妨设v的BSO值 以上的分析表明:采用“劈图”处理策略有利于降低算法 小于的BFSO值,那么综合上面的条件显然有:v∈V0,即的时间复杂度,同时有利于降低递归收缩算法的空间复杂 中ve,neA,即eP,而ve,即v是G的非可吸度。时间复杂度和空间复杂度具体能够降低多少,与支点情 点,如果G/。是G"本身,那么v≠T,此时结论G 形Ⅲ出现的次数及图的拓扑结构有关 GP已经得证,如果G/o"是GP"的祖先,不管是否应用“劈4.2“实验比较 图”处理策略,祖先的非可吸点在其后代中也必然是非可吸 为了检验¨劈图”处理策略的正确性秈有效性,用(#语言 点,因此也必定有v,此时结论G/W"b≠G同样成立。 实现了算法I和算法Ⅱ,输入随机产生的一组无向图,和设计 如果G的种子顶点是支点,且支点没有非可吸簇 组特殊结构,即出现支点情形Ⅲ出现比例较高的无向图进行 实验比较。实验结果如表1和表2所示。 此情形与(1)完全相同,根据(1)的分析,G/V"'≠G/V 表1和表2的数据表明:(1)对于普通结构的无向图,算法 根据(1)和(2)的分析,G八Vc0在算法Ⅱ处理G/V生成的过 程中只出现次的结论成立,证毕 I和算法I的执行速度基本相当(2)对于特殊结构的无向图, (2)算法Ⅱ生成的非平凡 EC RCA图数量少于算法I 算法∏·执行时间明显小于算法I,从本文例子来看,最快的只 首先考察两种算法中种子顶点的状态变化,种子顶点有5 需算法I的1/5时间。(3)算法Ⅱ的非平凡 EC RAC图数量小于 种不冋的状态:①种子顶点不是割点生成割集;②种子顶点算法I,所以算法Ⅱ的空间代价不高于算法I。综合(1)~(3)可 是支点,且非可吸簇数量为0:③种子顶点是支点,且非可吸簇知:在不增加空间代价的情况下,算法Ⅱ具有更加稳定的性能。 数量为1:④种子顶点是支点,且非可吸簇数量大于1:⑤整个 本文的实验环境为:主频2.0 GHZ CPU(双核),1GB 图只有一个顶点,就是种子顶点,此时 EC RCA图为平凡图 RAM、 Windows Xp操作系统、 Microsoft net o#2005集成 算法I和算法Ⅱ种子顶点状态之间的转换关系分别如图6(a)开发环境。 和图6(b)所示,其中初始状态是状态1或状态2。 5结束语 对现有的生成无向图割集的递归收缩算法进行了改进 解决了算法中的两个存在问题:(1)针对支点只有一个非可吸 t 簇的情形,引进附带吸入的概念,修正了现有算法中关于种子 顶点的BFSO值的取值规则,解决了现有算法可能漏掉割集的 问题,并且使得算法逻辑上更清晰ε(2)继续运用附带吸入的 (a)算法I (b)算法Ⅱ 概念,针对支点没有非可吸簇的情形制定了“劈图”策略,在不 图6算法I和算法Ⅱ执行过程中种子顶点 的状态变化 增加空间代价的情况下,使得算法对于不同输入均能保持较 高的执行速度。理论上,本文完善了生成无向图割集的递归 从图6(b)可以看岀:如果忽略不平凡的 EC RCA图(不计收缩算法,给出了一个更加正确、清晰、稳定、高效的算法。应 梁勇强:递归收缩算法中支点的欠理策略研究 2011,47(19) 59 表1算法Ⅰ和算法Ⅱ对普通结构的图的割集求解效率比较 EC RCA图数量 执行时间/ms 序号顶点数割集数出现勞图次数 算法I算法Ⅱ算法I算法I两者比较 199 0.0656250.0656251.00000 12345678 0.1093750.1093751.00000 0.2187500.2218750.98592 8 41 0.2468750.2468751.0000 0.6437500.6437501.00000 113 0.6468750.5250001.23214 l19 09625000.7781251.23695 105 105.8343750.8406250.9925 180 022 2842722.6875002.5937501.03614 637 9519149.9375009.5937501.0358 11 619 842 842 840625084843750.99079 330 4694284.9375004.5468751.08591 1493 2602255931.50000031.2812501.00699 93889711.39062510.9375001.0414 5 1943 3434 2722268934.68750034.9843750.99151 16 1055 1392132817.84375017.2968751.03162 表2算法Ⅰ和算法Ⅱ对特殊结构的图的割集求解效率比较 EC RCA图数量 执行时间s 序号顶点数割集数出现劈图次数算法1算法Ⅱ箅法I算法Ⅱ两者之比 6 0.06093750.02968752.05263 0.11406250.0515625 3 8 90.14843750.04687503.16667 l0.22656250.05625004.02778 10 0.27187500.07187503.7826 150.3296875008906253.70175 7 14 190.43437500.11250003.86111 16 21 0.32500000.12968752.506 320.51250000.21562502.37681 10 330.76875000.21250003.61765 2 271.07500000.20000005.3750 1.09062500.24375004.47436 111371.29687500.28125004.6111 39 551.74687500.47812503.65359 15 31 127431.65625000.40937504.04580 16 41 135 541.6562500044687503.70629 用上,本文给出的算法无疑有助于提高基于割集的相关应用3] Tsukiyama S, Shirakawa i, Ozaki h, et al. An algorithm to enu 系统的执行效率。 merate all cutsets of a graph in linear time per cutset[]. Jour nal of the aCm,1980,27(4):619-632 参考文献: [4]王先培,唐旭章,凸冯尚友,等.一个寻找稀琉图的割集的算法[] [I Provan JS, Ball M OThe complexity of counting cuts and of 电压技术,1998,24(1):3-5. computing the probability that a graph is connected JJ. SIAM [5] Sharafat A R, Marouzi O R Recursive contraction algorithm: A Journal of Computing, 1983, 12: 777-788 novel and efficient graph traversal method for scanning all min [2] Hongfen Za simple enumeration of all minimal cutsets of an imal cut sets[J]. Iranian Journal of Science Technology, 2006 all-terminal graph[ J] Journal of China Universities of Posts and Telecommunications, 1995, 2(2) l6王朝墙图论M」北京:北京理L大学出版社,1997