有向基本割集矩阵的超图综合法.pdf_大学文库

块数大于2的问题。本文应用超图理论提出了从有向Q,的树路子阵Q逐层判断其可实现性和综合出其对应有向图G的算法RFCMHGT。它的原理直观。 1有向图关于基本割集的超图和等效图设已知一个元素为0、1和-1的n×e阶基本割集矩阵Q,=〔IQ:),I为单位阵，Q,称为 Q,的树路子阵，因为它的每行对应于一条树支，每列对应于一条连支和与该连支构成基本回路的一条树路。行（树支）号集t={1,…,n},列（边）号集g={1,…e},Q:p的列（连支)号集利={n+1,…,e}。要求实现Q,即综合出一个连通有向图G,以G为其基本割集的矩阵。若Q,含有互不关联的d块（子阵）Q1,…,Q,则它们可以分别进行实现。若它们实现成有向图G1,…,G,则由它们共有一点（参考点）所得的图G就是Q,的一个实现。暂时假设Q,只含一块，并省去下标f,即设Q=〔IQ,。令M(R,)、M(,C)和M(R;C)分别表示矩阵M中行集R、列集C和行集R及列集C所构成的子阵，则Q=Q(t,g),Q。=Q(: t)。定义1矩阵Q-,Y∈t,是指从Q中移去行列Y、列Y和列集tr得到的矩阵，即 Q-y=Q(t-{y},g-{Y}-tr),tr={k|Q(ysk)≠0，k∈1} (1) 一般Q-x可按行划分成互不关联（即没有公共连支）的C个子阵（块）Q-(t:;),,为块i的行（树支）号集，=1，"，c。若Q可实现成图G,则块Q-r(t:)对应于子图G。令行y对应于G。,t。={y}。暂时不考虑边的方向和各G:内部的边及顶点，仅考虑每个G:的端点集E,以便搞清各G,之间的联接关系。根据超图理论5，E,是超树支，超树支集 E={E,E:,…,E。}构成超树T,有向图G(图1(a)变成无向超图HG(图1(b)。对应于基本割集y中每条连支k,HG中有一条由超树支组成的超通路Px与连支K构成超回路， Px称为超树路，在E,左、右的子超树添上E.后各称为左超树LT和右超树RT。RT(LT) 内E:(>0)的端点中离E,的右（左）端最近（即对应超树路最短）者称为E,和t,的父点r:。若把E。(t。)用等效树支“1代替，把E,(t,),>0,的从i,到其余各端点的二端子超边E.(树路p.)各用一等效树支4，a>1,代替，则E,(t,)变成以r:为中心的等效星树1.：（每个t. 的所有树支互称为伴随树支)，T(t)变成等效树t,HG(G)变成无向等效图G。(图1（©）。 1的在41左、右子树添上“1后各称为左树L和右树R。如果从4：和E。开始向右、左逐步生长t.和T,则生长：和E,的等效树支s,=u。(树支f∈p)称为t.和E,的等效父支（父支），记作rb()=b;从等效树支4。（树支j)生长出的等效树支u。(树支h)称为“.(）等效子支 (子支)、从u.生长出的所有右（左）等效子支的集合记作Rt.(Lt.),E。、41和y各称为 T、t,和的根支。定义2定义Q,关于行y的无向子阵J,如下： Qpg←Q,(tg多t,),ty=t。Ut1/U…Ute, (2) J,←Q?(所有元素取绝对值)。对于i=0,1,…c进行：从y(t;)中取出所有相异列的列号组成集Z:;对于S=1, 186

块数大于的向题。本文应用超图理论提出了从有向了的树路子阵了，逐层判断其可实现性和综合出其对应有向图的算法。它的原理直观。有向图关于基本割集的超图和等效图设已知一个元素为。、和一的阶基本割集矩阵，〔，，〕，为单位阵，，，称为了的鱼路圣阵，因为它的每行对应于一条树支，每列对应于一条连支和与该连支构成基本回路的一条树路。行树支号集，… ，，列边号集夕， … ，，的列连支号集习二谧，十， … ，。。要求实现，，即综合出一个连通有向图‘ ，以‘ 了为其基本割集的矩阵。若，含有互不关联的块子阵，，一，，‘ ，则它们可以分别进行实现。若它们实现成有向图了， … ，了‘ ，则由它们共有一点参考点所得的图就是了的一个实现。暂时假设了只含一块，并省去下标，即设〔，〕。令，、和分别表示矩阵中行集、列集和行集及列集所构成的子阵，则，，，二。定义矩阵一，，任，是指从中移去行列、列和列集得到的矩阵，即一，一，一一，夕笋，任一般一可按行划分成互不关联即没有公共连支的个子阵块一 ‘ ，，为块的行树支号集，二，，。若可实现成图，则块一。 ‘ 对应于子图久。令行对应于。，。二对。暂时不考虑边的方向和各 ‘内部的边及顶点，仅考虑每个 ‘ 的端点集 ‘ ，以便搞清各。之间的联接关系。根据超图理论 ‘ ” 〕，，是超树支，超树支集二丈。，， … ，。构成超树，有向图图变成无向超图图。对应于基本割集中每条连支，中有一条由超树支组成的超通路二与连支构成超回路，尸二称为超树路。在。左、右的子超树添上。后各称为左超树和右超树。内。的端点中离。的右左端最近即对应超树路最短者称为 ‘和，的父点 ‘ 。若把。。用等效树支。，代替，把， ‘ ， ‘ ，的从“ 到其余各端点的二端子超边。。树路。各用一等效树支。，。，代替，则 ‘ ‘ 变成以， ‘为中心的等效星树 ‘ 每个， ‘ 的所有树支互称为伴随树支，变成等效树，，变成无向等效图，图。。的在。左、右子树添上 “ 后各称为左树和右树。如果从。和。开始向右、左逐步生长和，则生长， ‘ 和 ‘ 的等效树支，二 “ 。树支 ‘ 任。称为，和 ‘ 的等效父支父支，记作 ’ 二叭从等效树支 “ 。树支生长出的等效树支 “ 。树支称为。。力等效子支子支、从。。生长出的所有右左等效子支的集合记作。。，。、。和各称为、和的根支。定义定义，关于行的无向子阵，如下，，，，，，，。 … ‘ ，，所有元素取绝对值。，对于。，， ” · 。进行从 ‘ 中取出所有相异列的列号组成集己，对于

拟称为p.到t:的下标变换集。了，的行数n,=n,列数1，=|t,。定义3把J,中每条树路p.用一等效树支“。代替，并以Z。作为“。关联的连支集，构成行J.(u),即Va∈{1，…，n},Vk∈t,若k∈Z:则J,(u；k)←1，否则J,(“. k)一0，那么行（树支）集t,变成行（等效树支）集t.(t.:内所有行互称为伴随行)，形成的矩阵J,称为Q关于y的等效树路阵或G.的树路阵。J.的行、列号集各为，=t.。Ut,U…Ut,e 和t.=|t,行、列数各为n,和.=【，。定义4元素为0和1的矩阵M称为(0,1)矩阵。M中每行（列）的非零元素数称为该行（列）的长度。元素全为1的行（列）称为么行（列）。元素全为零的行（列)称为零行 (列)。设M的行、列号集各为R和C,若 M(i;k)-M(j;k)≤0，Vk∈C (3) M(ism)-M(i,n)≤0，Vi∈R (4) 则称行i含于行j,列m含于列”，记作M(i;)CM(j;),M(;m)二M(;n);否则称为行不含于行i,列m不含于列n,记作M(,)CM(i;),M(;m)CM(;n)。若(3)和(4) 式中等号成立，则称为行等于行j,列m等于列n,记作M(i;)=M(j;),M(;m)= M(;n)。=是C的特殊情况。定义5对于矩阵J.的任一列k,定义列k的增广列k“如下：若J.(“。;k)=1,“.∈t, 则对于所有u6∈t,J,(“。k)←1。从Jy(J,)中选一最长列k,去掉所有含于列克1(k,)的列后，再选一最长列k,去掉所有含于列k2(k2·)的列，依此类推，直到全部列都去掉，所得列集{k1,,k}称作J,的覆盖列集，记作Z,(J,的增广覆盖列集，记作Z)。 2从等效树路阵Je综合等效树te和超树T 要从Q综合G,可先从Q,综合G的有向树t,再给t添上所有连支，就形成G。若有从J,综合.和T的算法，就可接着应用该算法于Q-,的各分块，依此类推，逐步产生出t。为此应将J,中每列k的树支集Pk都实现成一条树路，而且彼此相容，即能够形成一等效树t,。定义6对于任意k∈Z,px←{u。l4.∈t.,J.(“.;k)=1},J.x←J.(px)。h-1,对于 j=2,…,lPx进行：若px(j)=“,则i←W(a),若t.l>1,则把当行i加上（逻辑和）其在」，中的每个伴随行时所形成的新列排在J,x的右边（这是由于t:为星树，这些列也是应被实现的树路)，即对于r=1,…,1tl进行多若t.(r）=46,b卡a,则对于s=1,…, 1.进行，若j.(b,s)=1则h←h+1,J,x(;h)←J,x(s),J.x(a,h)1。比较各列，若有相等列，仅留一列，移去多余列。把行按长短从上到下排列。若几行等长，则其中对应于末稍树支（即I.(i)=1)的行j（若有的话）应排在下面，其余行按行号自然顺序排。形成的矩阵称为I,x的增广阵，记作Ix。若J.k的第j行变成Ix的第i行，则Sx〔px(j)门←i,Tx() px(),集Sx和Tx分别称为I.到Tx的行号正和反变换集。Jx的行、列号集记作Rx和Cx。根据定义6，注意到px关联的所有连支都跨越根支41，并且px的末稍树支“，（用 I,(“,)=1表示)上不容许再生长树支，可导出下面的定理1和推论1。定理1I,x的增广阵Tx具有下列性质： 188

甜称为户到 ‘的下标变换集。，的行数，。，列数，，。定义把，中每条树路。用一等效树支 “ 代替，并以。作为 “ 关联的连支集，构成行，即任谧， … ，。，任，，若〔 ‘ 。则。，否则 “ 。，那么行树支集变成行等效树支集 ‘ 二内所有行互称为伴随行，形成的矩阵，称为关于的等效树路阵或‘ 的树路阵。的行、列号集各为，，。，，日 … 。和二，，行、列数各为气和，二，。定义元素为。和的矩阵称为，矩阵。中每行列的非零元素数称为该行列的长度，元素全为的行列称为鑫丘三列。元素全为零的行列称为雯旦左业夕设的行、列号集各为和，若一，几〔一。，任则称行含于行，列含于列，记作，，二否则称为行不含于行，列。不含于列，记作己，己。。若和式中等号成立，则称为行等于行，列。等于列。，记作 ’ 了，舰万。是二的特殊情况。定义对于矩阵的任一列舟，定义列的增广列如下若。幻， “ 任。 ‘ ，则对于所有 “ 。任 ‘ ， “ 。 ’ ，。从，中选一最长列，去掉所有含于列儿的列后，再选一最长列秃，去掉所有含于列的列，依此类推，直到全部列都去掉，所得列集仕， … ，讨称作，的覆盖列集，记作，的增广覆盖列集，记作。从等效树路阵。综合等效树。和超树要从综合，可先从，综合的有向树，再给添上所有连支，就形成。若有从，综合和的算法，就可接着应用该算法于一的各分块，依此类推，逐步产生出为此应将中每列的树支集尸都实现成一条树路，而且彼此相容，即能够形成一等效树。定义对于任意任，，尤。。 “ 。任，无二，二，二。，，对于二， … ，户二进行若夕二。。，则平，若 ‘ ，则把当行加上逻辑和其在中的每个伴随行时所形成的新列排在，的右边这是由于，，为星树，这些列也是应被实现的树路，即对于，， ‘ 进行，若，， “ ，，午，则对于， ” · ，进行，若，，则 “ ，，二 “ ，，二，，。比较各列，若有相等列，仅留一列，移去多余列。把行按长短从上到下排列。若几行等长，则其中对应于末稍树支即的行若有的话应排在下面，其余行按行号白然顺序排。形成的矩阵称为 ‘ 的遭鱼鉴记作八。若 ‘ 的第行变成八的第行，则二〔 ‘ 〕 ‘ ，二。，夕以，集和’ 分别称为到几的行号正和反变换集。八的行、列号集记作和 ‘ 。根据定义，注意到 ‘ 关联的所有连支都跨越根支。，并且二的末稍树支 “ 用二表示上不容许再生长树支，可导出下面的定理和推论。定理入二的增广阵几具有下列性质名

(1)第一行为么行，k号连支对应列为么列。 (2)若Ix可实现成树路pK,则右（左）树路Rpx(LPx)中串联树支的对应行必相等，非串联树支的对应行必不等而且长度不同，离根支4：愈近的树支对应行愈长，在丁x中愈靠上。 (3)设从Jx已产生px的子树路px二Px,pk的右和左末稍树支各为ax和bs,则从Tx别去pk的对应行集S(pk)〔rxrx-S(p)门和零列集Z。={月jeCx,Ix(rx)=0}(Cx← Cx-Z,)后，若第一行Rx(1)为么行，则其对应树支ex=Tx(Rx(1)是唯一当前待生树支，它将生长在P:的右或左侧，否则，不含于行Rx(1)的最长行（称为Rx(1)的匹配行）的对应树支e:也是当前待生树支，ex与e:将分别生长在pk的两侧。 (4)当前待生树支dx(ex或e)可生长在父支Sx(ax或bx)上的必要条件是(a)Sx不是px 的末稍树支，即I,(Sx)=0;(b)行dx含于行Sx,即Jx(dx;)CJx(Sx;)。推论1矩阵Jx可实现的一个必要条件是Ix或其子阵不含有3个长度相同的不相等行。注意：(1)星树t,:中所有等效树支是互相伴随的，必须同时产生，即在生长ex∈t,:和 e∈t.:的同时必须生长t.和t:',t,和t。“称为当前待生星树，E:和E称为当前待生超树支。(2)当从丁x综合了px时，不仅实现了J,的列k,也实现了丁.中含于增广列k·的所有列。(3)所有满足px∩t三+中，k∈Z,的树路px的集合称为生长1，：的树路集，其对应列号集记作Z,Z:CZ,。根据这些定理1可导出定理2。定理2设I.的增广覆盖列集Z。={k,…,km},构造增广阵Jk1,“,Jx,从它们同时综合树路Px1,·,Pxw,若整个综合过程满足下面的相容生长条件，对于每棵当前待生星树t,与所有k∈之，所有fx=PxAt,都是当前待生树支，而且都能够生长于同一条等效父支Sk(ax或bx)=4s上，即 Vk∈Z,Sx(ax或bx)=4s,I.(s)=0,Ix(fx;)二Ix(Sx;), (5) 则Px1,“,卫x#是相容的，即它们能组成等效树t,。根据定理1和2可设计一个从J.综合t,和T的算法SHTMJE如下。算法中每步生长过程进行了两次，第一次检查相容生长条件是否满足，若满足才进行第二次的实际生长过程；若从右侧进行和从左侧进行生长都不满足相容生长条件，则，不能实现。每条等效树支“。在算法中用其下标a表示。算法SHTMJE(Je,Y;RT,LT,Rt,Lt,rb) (1)初始化：所有数组清零，a←1，RT(r)←0，B←1，LT(1)←0；按定义5求Ze, Vk∈Ze,gx←1，hxl,Rpx(1)←1，Lpx(1)←1。 (2)Vk∈Z.,按定义6从J,构造Jx、Sx、Tk、Rx和Cx,RxRx-Rx(1)。 (3)若Z.=中，转步骤T,否则Vk∈Z.进行（求等效父支ax、bx、当前待生树支集Bx 和当前待生超树支集Dx): ①Z。←{ili∈Cx,Tx(Rx:j)=0},Cx←Cx-Zo,Z。r{jj∈Cx,Ix(Rx(1)5 j)=0},ex←Tx(Rx(1),i-W(ex),ax←Rpx(gx),bx*-LPx(hx)。 ②若Zo1=p,则Bx←{ex},Dx←{》。 ③若Zg1卡中，则r-第一个己Rx(1)的最长行的行号，eR←Tx(r),"-W(e), Bx{ek,e》,Dx←{i,}。 189

第一行为么行，寿号连支对应列为么列。若、可实现成树路，则右左树路夕、 ‘ 中串联树支的对应行必相等，非串联树支的对应行必不等而且长度不同，离根支。，愈近的树支对应行愈长，在八中愈靠上。设从几已产生的子树路二、三，关的右和左末稍树支各为二和、，则从二删去差的对应行集二〔 ‘ ，二一印关〕和零列集。二二，》二一。后，若第一行为么行，则其对应树支 ‘ 二袱是唯一当前待生树支，它将生长在关的右或左侧多否则，不含于行二的最长行称为二的匹配行的对应树支嵘也是当前待生树支，二与要将分别生长在鑫的两侧。当前待生树支二二或份可生长在父支二、或二上的必要条件是二不是夕‘ 的末稍树支，即二行、含于行、，即 ‘ 、〔、、。推论矩阵几可实现的一个必要条件是几或其子阵不含有个长度相同的不相等行。注意星树口 ‘ 中所有等效树支是互相伴随的，必须同时产生，即在生长‘ 任，。和。分任。。 ‘ 的同时必须生长 ‘和 ‘ ，， ‘和， ‘ 称为当前待生星树，，和 ‘ · 称为当前待生超树支。当从几综合了时，不仅实现了，的列，也实现了中含于增广列的所有列。所有满足二门。今功，友任，的树路二的集合称为生长， ‘ 的树路集，其对应列号集记作 ‘ ， ‘ 仁。。根据这些定理可导出定理。定理设的增广覆盖列集。伪，， … ，讨，构造增广阵几， … ，几，，从它们同时综合树路，，一，二二，若整个综合过程满足下面的相容生长条件，对于每裸当前待生星树。 ‘ 与所有友任二 ‘ ，所有二二门 ‘ 都是当前待生树支，而且都能够生长于同一条等效父支二 ‘ 或二。。上，即益任 ‘ ，二 ‘ 或二，。，二 ‘ 二 ‘ ，则，二，、二是相容的，即它们能组成等效树。根据定理和可设计一个从综合和的算法如下。算法中每步生长过程进行了两次，第一次检查相容生长条件是否满足，若满足才进行第二次的实际生长过程若从右侧进行和从左侧进行生长都不满足相容生长条件，则不能实现。每条等效树支。。在算法中用其下标。表示。算法，，，亡，， ‘ 初始化所有数组清零，，，，。，声，，，。按定义求，任，夕、，， ‘ “ ，二，， ‘ ，。任，按定义从构造二、 ‘ 、 ‘ 、 ‘ 和二，二，二一二。若，价，转步骤，否则壳任进行求等效父支听、久、当前待生树支集二和当前待生超树支集户 ① 。，币任二，、二，， ‘ 一。，。任、， ‘ 、二，二， ‘ 二，牙 ‘ ，， ‘ 二，、， ‘ 二。 ② 若。，二价，则 “ 对，补。 ③ 若。，午价，则第一个己八的最长行的行号，心 “ ‘ ， ’ 甲为，刀‘ ，夏二，里，二，丈，，。习

， ‘ 中元素按自然顺序排， ‘任，，，价。才任和庵任进行修改和，求生长，的树路号集。 ① 户 ‘ 二，。自户‘ ，若 ‘ 二尤含价，二任 ‘ ，则 ‘ ， ‘ 习。 ② 若户 ‘ 、二斧价，二不属于二，则若 ‘ 二， ‘ 二匕 ‘ ，二，二日， ‘ 谧壳若，贯，转步骤。检查相容生长条件，生长当前待生树支和当前待生超树支 ‘ ① 。，。，，。 ② 刀 ‘ ， “ 必，劝，价，， ③ 若 ‘ 价，转步骤否则￡，刀 ’ ， ’ ，，转步骤⑤ 。 ④ 若，，， “ ，则沉，，，转步骤② 。一若，，，转步骤① 。若等，，则， ‘ 一，一，转步骤⑤ 。 ⑤ 吞任，进行取出待生树支二，匹配超树支‘ 进栈 ‘ 二自 ‘ ，若刀二一 ’ 圣今沪， ‘ ，则 ’ ， “ ， “ ‘ ，若， “ ，否则， ⑥ 若二、，二。，转步骤⑦ ，若。，，转步骤⑧ 。若，，转步骤 ⑩ 。若，，转步骤。 ⑦ 若任 ‘ ， ‘ ，，二 ‘ 已 ‘ 二，则， ’ 一谧，转步骤④ 否则转步骤⑨ 。 ⑧ 若任 ‘ ，二，，二 ‘ 二二，则 “ 一，转步骤④，否则转步骤⑨ ⑨ 若、。，则，，，， “ ，转步骤② 否则转步骤⑥ 。 ⑩ 任 ‘进行， ‘ ，夕，二夕‘ ‘ ，，二，二二，二， ‘ 一，若价，，，一。，，，，，。 ‘ ，，一，转步骤④ 。 ⑧ 掩〔 ‘进行二， ‘ ，夕二二， ‘ ，二，， ‘ ‘ ，，二一，若二价，，一伪。声声，声，‘ ， ‘ ，，一， ‘ ， ‘ ， “ 一，转步骤④ 。停止，显示 “ 不能实现 ” 。结束。从基本割集矩阵综合有向图定义了从矩阵构造二维数组和一维数组刀如下价，价， ‘ ‘ 、。 “ ，笋，壳二。， ‘ 簇，秃笋， ‘ ，，，亡数组对，刀称为矩阵的邻接表。应用深度优先搜索算祛例如文献〔〕中算法从，的行号集。二， … ，。刀可求得的块数和各块

从基本割集矩阵Q综合有向树t是逐层逐块进行的。令H存放第m层的正在实现的Q的一块子阵，H存放H"的树路子阵，X1(j)和X2()存放树支j的始点和终点号，t“和分别表示第m层的正在综合的有向树和无向等效树，S(j)=1,-1或0表示树支j的方向与根支y=y'的一致、不一致或未定，1（引jt")=1表示i是"的未稍树支，R={Rt}, Lt={Ltb}。第m层是从H综合"，综合过程如下： (1)从H,求出J:和J,从J:综合出t:和T"(RT和LT")。计算每条树路px及其子树路p:的末稍树支数9x和9，，若9x>2或g:>1,则Px不能实现。 (2)顺序处理RT中每条超树支E的对应子树t:(a)若J:(t”)=J:(t:,)(即= ,且Va∈t”,Ip引=1)则可以给t”中每条未处理(S(i)=0)的树支i标定方向和始、终点号，即对于树支与其父支f的对应基本割集的所有公共连支1检查乘积H”(i;)H(f;) :是否都相等，若否（表示行i与∫的元素符号有矛盾），则H“不能实现，若是，则S() H(i;I)H(f,)S(f),I(j)1,将E的父点号赋于j的左端，若i有一条子支h已处理过，则将h的左端点号赋于i的右端，否则vv+1,将v赋于i的右端。(b)若J(”,)≠ J:(::)(即引≠或3a∈，pl>1),则的结构未定，H1Q(tU{f};), 进入第m+1层，从H+1综合m+1=t”U{f}。 (3)顺序处理LT,中每条超树支E:的对应子树：；与(2)类似，但左、右二字互换。根据上述原理可设计一个从H“综合t"的算法SDTFCM和从Q,综合G的主算法 RFCMHGT如下。算法SDTFCM(Hm;ym,tm,S,x1、X2) (1)初始化：Q。←H,y←y",t。-{y},t,←1。 (2)按定义7建立H二y的邻接表(L,D),调算法DFS从(L,D)求出H二y的块数c和各块的行号集t,i=1,“,C。 (3)按定义2从Q,求得Jy、W和P。,a=1,…,n。若m>2,求Jy的覆盖列集Zy,对于每个i∈{1，…，c}和每个k∈Zy进行；9：x-∑I(引i∈t,Jy(i;k)=1),若9x>1,转步骠(7)；对于每个k∈Zy进行；9x←已9：，若9x>2转步骤(7)。 (4)按定义3从Jy求得J.和t.1,t=1,…,c。若m>1,对于a=1,…,n,进行；q.← 已I(引j∈p),若9.>0则I.()-1,否则I.(a)←-0。 (5)调算法SHTMJE从J.产生RT,LT,Rt,Lt和rb: ①若=1，转步骤②：否则找出含有父支f"的t?,若∈RT则L←-1，否则L←1。若L“R-1=-1则RT"-LT,LT"←RT,Rt"←Lt,Lt"←Rt,转步骤③：否则转步骤②。 ②RT←RT,LTm←LT,Rt"←Rt,Lt←Lt。 ③rb"-rb,I:←I.p8p。,a=1,…,n；t←t6,t,-ti,i=1,…,c。 (6)顺序处理RT"和LT"中每条超树支E?(处理RT时R1,处理LT"时R"← -1) 191

从基本割集矩阵缥合有向树是逐层逐块进行的。令 ‘ 存放第层的正在卖现的的一块子阵，君存放 ‘ 的树路子阵，和存放树支的始点和终点号， “ 和代分别表示第‘ 层的正在综合的有向树和无向等效树，，一或。表示树支的方向与根支的一致、不一致或未定， ’ ‘ 二表示挤是 ’ 的末稍树支，。，。第层是丛尘兰查竺，盆查过程如下从贯求出罗和，从综合出片和 ’ ’ 和 “ 。计算每条树路及其子树路。，的末稍树支数 ‘ 和，，，若 ‘ 或叮 ‘ 。，则二不能实现。顺序处理 ’ 中每条超树支丁的对应子树号若笋片二 ‘ 即州片 ‘ 且。任叮，，则可以给绍中每条未处理力的树支标定方向和始、终点号，即对于树支与其父支了的对应基本割集的所有公共连支检查乘积二是否都相等，若否表示行夕与了的元素符号有矛盾，则 ‘ 不能实现若是，则 ’ ，万丁’ 二， ’ 将罗的父点号赋于夕的左端若夕有一条子支已处理过，则将的左端点号赋于的右端，否则，将赋于夕的右端。若种丁户并才丁 ‘ 即了并 ‘ 】或日〔丁 ‘ ，丁，则尹的结构未定， ’ “ ‘ 一丁日谧，进人第。层，从 ’ ’ 综合 ’ ‘ 才丁七》。顺序处理。中每条超树支的对应子树甲与类似，但左、右二字互换。根据上述原理可设计一个从 ‘ 综合 ’ 的算法和从，综合的主算法如下。算法，，，、初始化，，万二，少，夕 ’ ，。夕，。。 “ 。按定义建立二，的邻接表，刀，调算法从，求出二，的块数。和各块的行号集 ‘ ，， … ，按定义从，求得，、牙和，，。二， … ， ” ，。若，求的覆盖列集，对于每个任， … ，和每个任进行 “ 笋任 “ ，，若 ‘ 二，转步骤，对于每个吞〔进行 ‘ 。，，若叮二转步骤。按定义从求得 ‘ 和， ‘ ，二， … ，。若。，对于二， … ，进行，任户。，若。则。。，否则，。，。二调算法从。产生，，，和 ① 若。二，转步骤 ② 否则找出含有父支 ’ 的叮，若任则 ’ 一，否则 ’ ，。若 ’ ’ 一 ’ 二一则 ’ ，一， ’ ，，刀 “ ， ’ ，，转步骤③ ，否则转步骤② 。一 “ ， ‘ ，君’ ，。，，，。，二， … ，。 ‘ 尹 ‘ ，丁 ‘ ，才， ‘ ，‘ ， … ，。顺序处理 ’ 和 ’ 中每条超树文丁处理 “ 时 ’ ，处理 ’ 时 ‘ “ ②③

若一。则。一，，，。，转步骤省否贝。转步骤② 。找出犷的父支和父点 ’ ，，忿中离最远的树支若 ’ 舍② 则，否则，，。 ③ 若】犷二，】且 ‘ 丁 ‘ ，厂卜，且则对于每个 ‘ 罗，若，进行对于树支了与的对应基本割集的所有公共连支检查乘积厂万二八是否都相等，若否、转步骤若是，则厂二打，。若 ’ ，，否则。找出树支的子支和子点若 ‘ 二，顺序检查〔叮，否则检查任了若找到一个。满足厂且公卜，则，忿。若 “ 则，，否则。若找不到上述。，则。，。，，。。若 ’ 二则 ’ ，否则了。 ④ 若笋 ‘ 或三任厂，二，则。， ’ “ 尹一，厂十万 ’ 川，从罗找出一个使厂了并。的最长列掩，再找出使罗幻笋。，的最长行夕。对于夕与了的对应基本割集的所有公共连支检查乘积厂口厂是否都相等若否，转步骤若是，则 “ 厂爪，，，夕，夕， ‘ 十，调。停止，显示 “ ‘ 不能实现 ” 。， ‘ · 二一，结束。主算法，，、，，输人了。按定义建立的邻接表，，调求出，的分块子阵，二， ‘ 二，对于二， … ，进行初始化，。，二，价，价，，价，，功，，价，。，。，。 “ ，万 ’ ， ‘产、 ‘产、、护矛，、少一飞了瓜山了‘ 、门︺一，罗，万 ‘ ，二的最长行的行号，，夕 ’ 夕，十了， ② 调从王综合有向树，即产生的树支的方向集和始终点集、。 ⑧ 建立，二的图了的关联阵二二，， ‘ 一，， … ， “ 哎落任， ‘ 尹，二，，名二 ‘ ‘ ，二，一，、气建立的图的关联阵，〔，， ‘ 〕。结束。本算法的计算时间主要决定于步骤② ，最坏情况是，。，。，规模最大，其计算复杂度为之，和为了的树路子阵，，的行数和列数限于篇幅，应用举例从