陈氏基本互补划分法的改进和发展

D0I:10.13374/j.issn1001-053x.1996.06.014 第18卷第6期 北京科技大学学报 VoL18 No.6 1996年12月 Journal of University of Sclence and Technology Beijing Dec.1996 陈氏基本互补划分法的改进和发展 黄汝激 北京科技大学自动化信息工程学院，北京100083 摘要应用有向超图理论引人超边的分解与收缩概念，把解决二个无源网络级联问题的陈氏基 本互补划分(ECP)法改进为更有效的分解一收缩对(DCP)法，发展为有向（正根）分解一收缩对 PDCP)法，用于解决二个有源网络级联问题.在此基础上，进一步发展为一般分解一收缩(GDC) 法，用于解决多个有源网络互联时求符号网络函数的问题. 关键词符号网络函数，有向超图理论，分解一收缩对法 中图分类号0157.5 在电子线路的分析与设计中经常用到符号网络函数，产生符号网络函数的关键是产生 网络图的全部树.陈惠开教授山提出了2个多端无源网络级联时产生全部树的基本互补划分 (ECP)法.文献[2~5]又对ECP法作了进一步研究，但无突破性进展.文献[6]阐明了m点集 V(m)的一个ECP对应于无向二超边超图m=(m,)的一棵超树T.本文首先应用有向超 图理论)引入超边的分解与收缩概念，把陈氏ECP法改进为更有效的方法，以解决2个有源 网络级联及多个有源网络互联时求符号网络函数的问题. 1超边的分解与收缩 根据有向超图理论可，e≥2个多端有源网络互联形成的超网络N的伴随超图H=(V, E),V={1,…以，E={E,…,E}.设超边E=4,UB,4∩B,=中，记作E=E[4B]4称 为被开路，若A的所有引线被移去使得E变成E,[B,]=E,-A·A,称为被收缩，若A,及其伴随 图G(4)被收缩成一点耳（称超端点）使得E变成E,-A+1端超边，记作E,石B]=E°A· m端无向超边E的一个h分解D,=D,(m,h)=E,[F,…,F】={F,…,F}是把E划分成h个 互不相交的非空子集F,i=1,…,h.F称为E,的i号子超边，并以其端点号串为其简化表示. D,的权Dy)定义为E,的伴随图G(E)中所有h树权(F,…,Fy)之和形成的多项式P[(F, …,Fy],即： D)会P[E…FA]=2F…F州ce (1) m端无向超边的h分解的数目记作[m,h].无向超边E1,…,m的分解集SD(m).h分解集 SD(m,h)和a号h分解的表达式参看文献[7]定理2.应用该定理可递归推得SD(m),m=I, 2,3,4,…(见文献[]中推论1).Bm=1SD(m川称为贝尔(Bel)数，B,=1,B2=2,B2=5, B=15,B,=52,,m端有向超边E的一个正根h分解PD,=PD(m,h),=Ew,,rw,) ={r,w1,…,w}是把E划分成h个互不相交的具有正根r,的非空正根子超边r,wi=1,…, 1996-01-02收稿第一作者男56岁教授

第 卷 第 期 年 月 北 京 科 技 大 学 学 报 。 陈氏基本互补划分法 的改进和 发展 黄汝激 北京科技大学 自动化信息工程学 院 ， 北京 摘要 应用 有 向超 图理论引人超边 的分解 与收缩概念 ， 把解决二个无源 网 络级联 问题的 陈氏基 本互补划分 法改进 为更有效的分解 一 收缩对 法 ， 发展 为有 向 正 根 分解 一 收缩对 伊 法 ， 用 于解决二个有源 网络级联 问题 在此基础上 ， 进一步发展 为一般分解 一 收缩 法 ， 用 于解决多个有 源 网络互联 时求符号 网络 函数的 问题 关键词 符号 网络函数 ， 有 向超 图理论 ， 分解 一 收缩对法 中图分类号 在 电子 线路 的分 析 与设计 中经 常 用 到符号 网络 函 数 产 生 符 号 网络 函数 的 关键是 产 生 网络 图的全 部树 陈惠开教 授 提 出了 个多 端无 源 网络级 联 时产生全部树 的基本互 补划分 法 文 献 一 又 对 法作 了进 一步 研究 ， 但 无 突破性 进展 文 献 阐 明 了 点集 的一个 对应于 无 向二超边超 图 丫 叼 ，习 的一棵超 树 本 文 首先应 用有 向超 图理 论 引人超 边 的分解 与 收缩 概 念 ， 把 陈 氏 法 改 进 为更有 效 的方 法 ， 以 解 决 个有 源 网络级联 及 多 个有 源 网络互 联 时求符号 网络 函 数的 问题 超边的分解与收缩 根 据有 向超 图理 论 ， 。 全 个 多 端有 源 网络互 联 形 成 的超 网络 的伴 随超 图 ， 习 ， 。 一 ， … ， ， 一 ， ， 一 ， 姗 · 设超 边 乓一 凡 乓 ， 毛 乓一 价 ， 记 作 乓一 乓叭 〕 · 凡称 为被 开路 ， 若 凡的所有 引线 被 移 去使得 乓变 成 乓〔凡 ， 一 ， · 凡称 为 被 收 缩 ， 若 再及 其伴 随 图 被 收缩 成 一 点 不 称超端 点 使得 乓变成 呢 一 刃 ‘ 端超 边 ， 记作 乓欧 〕 一 乓 。 凡 · 端无 向超 边 乓的一个 分解 只 一 只 ， 一 乓 ，， 一 凡 一 ， 一 凡 是 把 气划分成 个 互 不 相 交 的非 空 子集 汽 ， 一 ， 一 · 只称 为 乓的 号 子 超 边 ， 并 以 其端 点 号 串为其 简化表 示 · 几的权 几妙 定 义 为 乓的伴 随 图 乓 中所 有 树权 叹 ， 一 气‘ 之 和 形 成 的多 项 式 弓〔移 ， ” ‘ ， 气 力 ， 即 几切 “ 弓 ，’ 一， 川 一 勘 ，’ 、 称 。 ， 端无 向超边 的 分解 的数 目记作 ， 无 向超 边 ， … ， 的分解 集 分解 集 ， 和 号 分解 的表 达 式参看 文 献 〔 定 理 应 用 该定理 可 递 归推得 ， ， 乓 巧 ， 么 ’ ’ · ，， 一 、 是 把 乓划分成 个互 不相 交 的具有 正 根 数 ， ， ， ， 乡一 ， ， 一 月 ， ’ ‘ ， 介 。 的非 空 正 根 子超边 厂袱 ， 二 ， … ， 一 一 收稿 第一作 者 男 岁 教授 DOI ：10．13374／j ．issn1001－053x．1996．06．014

·558· 北京科技大学学报 1996年No.6 h.PD,的权PDy)定义为E的伴随有向图G(E)中所有正根h树权(，w,w)之和形成 的多项式P[w,rwy小，即： PD)pw]=wc) (2) m端有向超边E(1,…,m)的具有给定正根集p=p,,P}的正根分解集SPD(m)p是它的所 有具有正根集r2p的正根分解PD(m,h,c)的集合，即： SPD(m)=(PD(m,h,c)r2p;h =lpl,,m;c =1,,[m,h]} 3) 其中r=化…}=p,…,Pn+…,r,[m,是(l,…,m的具有给定正根集p的正根 h分解PD(m,h,c),的数日.例如SPD(3)23={21,3},{2,31},{2,3,1}.根据SPD(m)p和 SD(m)的定义，应用似SPARKS语言，可设计算法ASPD如下， 算法ASPD∥从SD(m求SPD(m),∥ l.p←{p1,…,Pn；np;SPD(m)p中；input m and SD(m) 2.for h+-n to m do c+0;SPD(m,h)←中 for a+-1 to [m,h]do from SD(m)take out D(m,h,a); ifD(m,h,a)=p,"“pwFa+1…,F}then for in11 to F+il do +1+F+(n)iw+1F+1-F+n+) fora+1toF月do rF(,)；ws←F6-F(；c-c+l; PD(m,h,c){p1w1…,PaWnIn+1Wn+1…,raw}: SPD(m,h)+-SPD(m,h){PD(m,h,c)} repeat repeat endif repeat;SPD(m)+-SPD(m)SPD(m ,h) repeat 3.end ASPD 推论1令SPD(m)=SPD(m),,从算法ASPD可推得 SPD(1)={1} SPD(2)={12},{1,2} SPD(3)={123},{12,3},{13,2},{1,23},{1,32},{1,2,3} SD(4)={1234},{123,4},{124,3},{12,34},{12,43},{134,2}, {13,24},{13,42},{14,23},{14,32},{1,234},{1,324}, {1,423},12,3,4},{13,2,4},f1,23,4},{1,32,4},14,2,3}, {1,24,3},{1,42,3},{1,2,34},{1,2,43},{1,2,3,4} 2DCP法和PDCP法 考虑一超网络N,它的伴随超图H=(V,E),={1,2,…,m},E={E,…,E},H和E的伴

· · 北 京 科 技 大 学 学 报 年 · 几的权 几。 定 义 为 乓 的伴 随有 向图 乓中所有 正 根 树权 ，， … ， 气 。 力之 和形 成 的多 项 式 弓 ，， 一 气 、 ， 即 。 “ 找 ， · ” ’ ， 。 ‘ 一 艺叹 ， 一、 、 少 。 ， 端有 向超边 ， … ， 的具有 给定 正根集 伽 ， 一 。 的 正 根分解 集 是 它 的所 有具有 正根集 卫 的正根分解 ， ， 的集合 ， 即 ， ， ， ， 卫 夕 巨 ， ’ 一 ， … ， ， 车 其 中 犷 一 ，， 一 气 一 伽 ， 一 。 ， 、 ，， 一 ， ， 是 ， … ， 的具有 给定 正 根集 的正 根 分 解 ， ， 。 的 数 目 例 如 ，， 王 ， ， ， ， ， ， 根 据 沁和 的定 义 ， 应用 似 语言 ， 可设计算法 如下 算法 从 求 · 夕 夕 ， ‘ ” ，夕 巨 ， 沪 · ， 沪 ， ， ， ， ， 一 加 ， ’ · ‘ ，夕 。 ， 凡 ， ， ’ “ ， 气 气 气 、 。 ， 一 气 ， 凡 气 凡 一 凡 ， ， 切 ，， 一夕 。 ， 。 ， 。 ， ，， ” ’ ， 。 ，， ， 入 ， 人 口 ， ， 沁 口 ， 推论 令 一 ， 从算 法 可 推得 ， ， 笼 ， 笼 ， ， ， ， ， ， ， ， ， ， 笼 ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， 笼 ， ， ， 笼 ， ， ， 笼 ， ， ， 毛 ， ， ， ， ， ， ， ， ， 毛 ， ， ， 毛 ， ， ， ， ， ， 法和 法 考虑 一超 网络 ， 它 的伴随超 图 一 ， 习 ， ， ， 一 ， ， 一 ， 和 乓的伴

Vol.18 No.6 黄汝：陈氏基本互补划分法的改进与发展 ·559· 随混合图分别记作G=G(团和G=G(E)j=1,…,e.要求H的超树权多项式P[Ty]m.下 面先讨论2种特殊情况. 情况1H是无向二超边超图一DCP法 若H的一对分解超边D,=E,[F…,F和D2=E,[F,…,F的(h+k=m+1)构成-棵 超树T,则称D,和D,为V的一对基本互补划分，记作ECP=(D,D,).H的一个分解超边 D,=E[F,",F]与其对应收缩超边C2=E,F,…,F]组成的对称为H的一个分解-收缩 对，记作DCP=(D,C),它的权DCPy)Dy)Cy). 定理1无向二超边超图H的超树权多项式P[Ty]等于H的所有分解-收缩对权 DCPy之和，即： P[T()]EDCP(y)=ED,(y)C,(y)(D ESD (4) 式中，求和是对于E,的所有分解超边D,∈SD,进行的. 证：设与D,基本互补的分解超边D,有b个，记作D,i=1,,b,则含D的部分超树权 多项式PT心)D,]=D,)∑D).因F内的点已被D,连通，F与F≠未被连通，故据超树 定义，在D中，F,内的点应不连通，F与F0卡)的点或者由D连通，或者通过D,连通.因此 把F,0=1,…,h)收缩后所有D=1,…,b)都将变成同一个收缩超边C2,从而有： 三D0=C0 (5) P[T]=ΣP[TO)ID,]=D,y)∑DO) (ECP法) (6-1) 1 P[T(y)]=E D,(y)C,(v)=E DCP(y) (DCP法) (6-2) 例如，m=4和D=E,23,4的无向超树集和DCP,见图1.这里三P0)三Dg0 =C,0y).DCP法与ECP法的P[Ty]项数Bm与Nm=2(m+1)m-2的比较如表1所示.可见，随 着m的增大，Bn可比Nm降低几个数量级以上，因此DCP法的计算效率远高于ECP法. 情况2H是有向二超边超图一PDCP法 陈惠开教授山未解决有源网络的分解法问题.若N是有源网络，H是有向超图，必须将陈 氏ECP概念发展如下.若H的一对正根分解超边PD,=E,(C,w…,rw)和PD2=EC,w,, ,rw)(佔+k=m+1,1=,'=1)构成一棵正根超树刀T(这里选点1为正根)，则称 D D 1.0 (a)D=E[124,3](b)D-E[134,2](c)D-E[12,341(d)D=E[13,24] (e)C2=E[1234 图1m=4和D=E,[1,23,4的无向超树集{T=DUDi=L,…4}和DCP=(D,C)

黄汝激 陈氏基本互补划分法 的改进 与发展 随混合 图分别记作 一 功 和 气一 ， 一 ， 一 。 · 要 求 的超树权多项 式 期〕 〔 下 面先讨论 种 特殊情况 情况 是 无 向二 超边 超 图一 法 若 的一 对分解超 边 ， 二 ， ，， 一 气〕和 二 乓 ’ ， 一 凡勺 二 构成 一棵 超树 ， 则称 ，和 为 犷 的一 对基 本互 补划 分 ， 记作 一 ， 的一个分解超边 ， 一 ，， 一 与其 对应 收 缩 超 边 乓区 ，… ， 瓦〕组 成 的 对称 为 的 一 个分 解 一 收 缩 对 ， 记作 ，， ， 它 的权 妙 全 伽 妙 · 定 理 无 向二 超 边 超 图 的超 树 权 多 项 式 刀沙」等 于 的 所 有 分 解 一 收 缩 对权 切 之和 ， 即 尸 玲 一 妙 一 刀 吼伽 田 ， 式 中 ， 求 和 是 对于 的所 有 分解 超边 进行 的 · 证 设与 ，基本互 补 的分解 超边 有 个 ， 记作 补 ， 一 ， 则含 ，的部分超树权 多项式 尸〔期脚 切 ‘ 荟几协 因 种的点 已 被 几连 通 ， 乓与 期羊 未被 连通 ， 故据超树 定义 ， 在 玉中 ， 弓内的点应不 连通 ， 弓与 助 羊 的点或者 由 玉连通 ， 或者通 过 ，连 通 · 因此 把 乓口一 ， 一 收缩后 所有 一 ， 一 都将变成 同一个收缩超边 ， 从而 有 艺 玉 伽 尸【。 ，一 尸【孙，‘ ，一 。 。 ‘ 睿 。 。 法 尸 均 一 ， 。 。 一 即。 法 例 如 ， 二 和 ， 二 ， ， 的 无 向超 树 集 和 ， 见 图 · 这 里 一 一 菩 是。 一，菩 孟切 妙 · 法 与 法 的 玲 项 数 。 与 戈 。 一 ’ 的 比较如表 所示 可见 ， 随 着 的增 大 ， ， 可 比 凡降低 几个 数量 级 以 上 ， 因此 法 的计算效率远 高于 法 情况 是 有 向二 超 边超 图－ 法 陈惠开 教 授 川 未解 决有源 网络 的分 解 法 问题 若 是 有 源 网络 ， 是 有 向超 图 ， 必须将 陈 氏 概念 发展 如 下 若 的一 对正 根分解 超边 一 ，， 一 叭 和 一 凡 ，， ‘ ， “ 一 、 ， 一 ， 一 ‘ 一 构 成 一 棵 正 根 超 树 汇圳 爪 这 里 选 点 为 正 根 ， 则 称 瓜区口 奋 介 奋 目 内 口 石 【一 ， 刀兰一 ， 刀孟一 ， 刀里岔石 【 ， 【 图 一 和 ， 一 百 ， ， 的无 向超树集 长 一 玉 一 ， … ， 和 一

·560· 北京科技大学学报 1996年No.6 PD和PD,为V的的一对有向（正根）基本互补划分，记作PECP=(PD,PD).H的一个正根分 解超边PD,=E,(,W,,raw,(设r=1)表1DCP法与ECP法的PIIy》项数B与N的比较 与其对应正根收缩超边PC2=E2w,,“, mDCP法项数B。ECP法项数N。=2(m+)2 %)组成的对称为H的一个正根分解一收 2 2 2 缩对，记作PDCP=(PD,,PC2),它的权 3 5 e PDCP()会PD,y)PC2y),式中w,*0=1, 4 15 50 …,h)的右上标“+”表示点集w,中所有点 5 52 432 在PD,中应为正极（因它们在PD,中为负 6 203 4802 极)，收缩前应将G(E,)的w,中所有点的射人 7 877 65536 边都去掉，以保证w,中所有点在PD,中为正 4140 1062882 极. 9 21147 2×10 定理2有向二超边超图H的正根超树权多项式PLTy)]等于H的所有正根分解一收 缩对权PDCP(y)之和，即： P[Ty)]=ΣPDCP()=ΣPD,Oy)PCy(PD,ESPD) (7) 式中求和是对于E,的所有正根分解超边PD,∈SPD,进行的. 证：与定理1的类似，设与PD,正根基本互补的分解超边PD,有a个(a≤b),记作PD, i=1,…,a,则有： 含pD0)=Pc0 (8) P(T,O)=EP(T,y)IPD)=PD,y)∑PDOy)(PECP法) (9-1) 1 P(T,y)=ΣPD,y)PC,y=ΣPDCP(y)(PDCP法) (9-2) 文献[6]中第三节的方法就是PECP法，这里把它改进为PDCP法，大大简化了计算和提 高了计算效率.例如，m=4和PD,=E,(1,23,4)的正根超树集和PDCP如图2所示.这里 PD(y)=PD)+PD)=PC,0). PD PD! PD PD PC2 +o- +o 23 +0 o于 (a)PD;=E,(124,3) (b)PD3=E,(12,34) (c)PC,=E,(123F4) 图2m=4和PD,=E,(1,23,4)的正根超树集(T1=PD,UPD|i=1,2}和PDCP=(PDPC) 3一般分解-收缩(GDC)法 现在把PDCP法推广到超边数e>2的一般有向超图情况.这时每处理（收缩-分解）完

北 京 科 技 大 学 学 报 年 和 为 的 的 一 对有 向 正 根 基本互 补划分 ， 记作 ，， · 的一个 正 根分 解 超 边 一 ， 一 气 设 一 表一 法与 法的 尸 双 项数焦 与凡的比较 与 其 对 应 正 根 收 缩 超 边 一 乓 咖厂 ，二 ‘ ， 币了组 成 的对称 为 的一 个 正 根分解 一 收 缩 对 ， 记 作 ， ， 它 的 权 伽 会 。 。 ， 式 中 仃一 ， 一 的 右 上 标 “ ” 表 示 点 集 玛中所 有 点 在 中 应 为 正 极 因 它 们 在 中 为 负 极 ， 收缩前应将 凡 的 中所 有 点 的射 人 边都去 掉 ， 以 保证 中所 有 点 在 中为正 极 法项数刀 法项数戈一 ” 定 理 有 向二 超 边 超 图 的正 根超 树权 多 项 式 几沙 等于 的所有 正 根 分解 一 收 缩 对权 伽 之 和 ， 即 尸 界。 一 妙 一 妙 妙 ，。 ， 式 中求和 是 对于 ，的所有 正 根分解 超边 〔 ，进行 的 · 证 与定理 的类 似 ， 设 与 正 根 基 本 互 补 的分解 超 边 有 。 个 ‘ ， 记作 护 二 ， … ， ， 则 有 ，万 、” 玉。 一 ” 。 兀。 一 艺 。 一 艺 。 潇菩 ” 玉。 法 一 ，妙 二 艺 ，妙 妙 艺 切 法 一 文 献 〕中第三 节 的方法 就是 法 ， 这 里把它 改进 为 法 ， 大大 简化 了计算和提 高 了计算 效 率 例如 ， 和 ， ， 的正 根超 树 集 和 如 图 所示 这 里 蓦 乡 一 孟。 ” 圣。 一 。 · 一李沙 盆︸妇州十干 十叫 一 口卜 卜 叫 孟 凡 ， 盆 ， 乓 十 图 一 和 一 万 ， ， 的正根超树集 丁’ 一 玉 一 ， 和 一 ， 一般分解 一 收缩 法 现 在 把 法 推 广 到超 边 数 。 的一 般有 向超 图情 况 这 时每处理 收缩 一 分解 完

Vol.18 No.6 黄汝激：陈氏基本互补划分法的改进与发展 ·561· 一条超边，都要对其后所有超边进行收缩处理.因此有： 定理3有向超图He>2)的正根超树权多项式P[T,y)]可表达成： PTy)=ΣPDy)…ΣPCD()·PC.y (10) 式中，PCD(1<j广<e)称为E的0-1)重收缩-分解超边，它是E依据前0-1)条处理过的 超边进行（一1）重收缩后再分解（若能分解且不破坏所得超图的连通性）得到的.P℃称为 耳的(e-1)重收缩超边，它是E。依据前(e-l)条处理过的超边进行(e-1)重收缩得到的.求 和是对所有不破坏所得超图连通性的可能分解PD和PCD,l<j<e进行的.若E,(E,或E,) 是无向超边，则PD,(PCD,或PC)可用D,(CP,或C)代替. 根据定理3，应用分支定界法和状态空间树(SST)⑧概念，可设计一个通过P(T)=P(T) 产生P,)的一般分解-收缩(GDC)算法如下： Algorithm SSTGDCM II Find P (t by SST and PT of H=(V,E) Integer m,n,t,p,fl,ns ,v,e Array EM EN,DM,E,,PD,,NS,FL,Y,r,w,SN,SE,SDM 1.Initialize:vlMe·E:m0;n0;t←0；r,{l};p←l;NS←Z;FL←φ；Y ←中；Yo)←l;DM+中；EN←中；EM←E.IfEM=φthen go to step6. 2.Process state node m:From EM find a hyperedge E,incident on the positive root r,if such E,can not be found then go to step 6 else find SPD,of E by Corollary 1;DM+-SPD EM+EM-E )EN +EM 3.Generate state node n From DM take out a PD,=E(rw:,,rw).For each EEEN and each vEE,if vEw,w then v must be a positive pole of E.for generat ing T,denote it by vto indicate that in G(E)all edges incident into v,must be deleted, then contract each subhyperedge r,w,of PD into one hyperterminal rw,,stored in set r,, to yield a contracted hypergraph H expressed by EN and corresponding to a new state node n with weight PD,and father node label m,that is,n-n+1;NS(m)NS(m)+1; FL(n)+m;Yn)←PDDM←DM-{PDr←r;Uw,i=l,…,hprl 4.IfDM丰中then t←t+l;SN()←m;SE()←EM;SDM()←DM. 5.IfEN≠then m←n;EM←EN;go to step2. 6.If p=v then state node n is a leaf node,go to step 9,else go to step 7. 7.Delete state node n fl +-FL(n)NS(fl)+-NS(fl)-1;Y(N)n +n-1. 8.If NS(fl)=0 and fl SN(t)then go to step 7. 9.If t>0 then m +SN(();EM+SE(f);DM SDM(t);tt-1;go to step 3. 10.Ift=0 then the search process forms a SST.From SST the required P(T)and P()=P[T (y)]can be found by the following Theorem 4 and above Theorem 3 respec- tively. 11.End SSTGDCM. 定理4从算法SSTGDCM产生的状态空间树SST按照节点标号n的顺序写下它的所 有状态节点权Y),并插入某些符号+”，“[”和]'使得每个子树权等于该子树根点权乘以 其所有子子树权之和，结果形成一多项式P.那么P(T)=P.P的展开式的每一项P是H的

黄汝激 陈氏基本互 补划分法 的改进 与发展 一条超边 ， 都要 对其后 所有 超 边 进行 收缩处理 因 此 有 定理 有 向超 图 的正根超树权多 项 式 兀砂 可 表 达成 兀沙 “ 艺 仁 切 ” ‘ 。 式 中 ， 仁， 称 为 乓的 仃一 重 收缩 一 分解 超 边 ， 它是 依 据前 口一 条处理 过 的 超 边 进 行 仃一 重 收 缩 后 再 分 解 若 能 分 解 且 不 破 坏 所 得 超 图 的 连 通 性 得 到 的 称 为 乓的 一 重 收缩超边 ， 它是 依据前 一 条处理过 的超 边 进行 一 重 收缩 得 到 的 求 和是 对所 有不 破坏所 得 超 图连通 性 的可 能分解 ，和 几几 ， 。 进 行 的 · 若 ， 乓或 是 无 向超 边 ， 则 ， 沪或 可 用 ， 砚 声或 代替 · 根据定理 ， 应 用 分支定 界 法 和 状态 空 间树 概念 ， 可 设计 一 个通 过 探 产生 凡 的一般分解 一 收缩 算法 如下 。 探兀 ， 习 ， ， ， 夕 ， ， ， ， ， ， ， 乓 ， 几 ， ， ， ， ‘ ， ，， ， ， · 川 尸 沪 沪 沪 沪 · 神 · · ‘ ‘ 如 ‘ ， ‘ ， 乓 ， ‘ ‘ 几 乓 一 · · ‘ ‘ ‘ 刀 ‘ ，， ” ’ ， · 乓 ‘ 〔 ， ，‘ … ‘ · 爪 ， ‘ ‘千 ， ， ， 几 即 ， ‘ ， ‘ ‘ ， 凡 ， 几 ， ， 马 一 几 ‘ ， 一 ， 一 ， 一 · 举 沪 手 沪 ‘ 一 · ， ， · · 一 玖川 沪 一 羊 一 · 气 兀 ， 妙 定 理 从算 法 产生 的状 态 空 间树 按 照 节 点 标 号 的顺序 写 下 它 的所 有 状 态 节 点权 ， 并 插 人 某 些 符 号 “ ” ， “ 「 ” 和 “ 」 ” 使得 每 个子 树 权 等 于 该 子 树根 点权乘 以 其所有 子 子树权 之 和 ， 结果形 成一 多项 式 尸 那 么 探 一 尸 尸 的展 开式 的每一 项 只是 的