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

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(10 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的

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

·562· 北京科技大学学报 1996年No.6 一个正根超树子集，并且对应于SST中从根点0到一叶点的一条路径（称为树路）. 证：注意到伴随每一树路p的项P,对应于一个分解超图子集{H}.例如，设树路p0→6) 对应于项P2=E,(12,3)E,(123)E,(23)=E,(12,3)[E,(1,23)+E,(13,2)]E,(2,3),它包含2个 H:E(12,3)E1,23)E,(2,3)和E(12,3)E2(13,2)E,(2,3),见图3.步骤3,5,6,7和8保证每个 H,是H的一个T,对于关联根点r的每条超边E,EEM只有DM类T,每类T,含E,的一个分 解PD,所以步骤1,2,3,4和9保证无重复地产生H的全部T.因此P(T)=P.证毕. y19 9 10 Y15 4 G2」 图3超网络N的混合图G 推论4.1在算法SSTGDCM的步骤2中，若E,是无向的，仅需找出E的无向分解集SD, DM←SD,并且在步骤3中当从DM取出一个D时可以把赋于EEEN的端点v,E[E,∩(w,U …Uw,】以”+”极性的过程省去， 算法SSTGDCM中求SST部分的计算时间复杂度（决定于步骤2~9）是O(n),e是H的 超边数，n,是SST的叶点数.叶点权Y(n)=P,(w)是用算法DKTPCG9计算的，其复杂度参看 文献[9]. 需要进一步研究的问题有：(I)PDCP法和GDC法中P[T,Oy刃的项数的计算和估计；(2)分 解一收缩法在超图理论其他问题中的应用；(3)分解-收缩法与并行算法的结合. 参考文献 1 Chen W K.Computer Generation of Trees and Cotree in a Cascade of Multiterminal Netwo.ks. IEEE Trans on CT,1969,CT-16(11):518~526 2 Chen W K,Goyal I C.Tables of Essential Complementary Partitions.IEEE Trans on CT,1971.CT -18(9):562-563 3 Kajitani T,Ueno S,Chen W K.On the Number of Essential Complementary Partitions.IEEE Trans on CAS,1982,CAS-29(8):572~574 4吴新余，论k=5时基本互补划分表的产生.见：中国电子学会线路与系统学会“一般理论专题讨论会

· · 北 京 科 技 大 学 学 报 年 一个正根 超树子集 ， 并 且 对应于 中从根 点 。 到 一 叶点 的一条路径 称 为树路 证 注 意 到伴 随每一 树路 的项 对应 于 一个分解超 图子集 凡 例 如 ， 设树路 对应于 项 凡 ， ， 气 万 乓 劝 ， ， 凡 ， 乓 ， 乓 ， ， 它 包含 个 ， 乓 ， 风 ， 和 ， 乓 ， 乓 ， ， 见 图 · 步 骤 ， ， ， 和 保证每个 凡是 的一 个 兀 · 对于 关联根 点 的每条超边 乓‘ 只有 类 ， 每类 界含 乓的一个分 解 几 · 所 以 步骤 ， 么 ， 和 保证无 重复地产 生 的全 部 兀 · 因此 探兀 一 尸 · 证毕 · ， 一 … “ 一 二 … 、 一拐 平 一、 长乒 … 一 一 一 一 一 众 一 一 代 一一 一 卜 上 扮 图 超网络 的混合 图 推论 在 算法 的步骤 中 ， 若 乓是无 向的 ， 仅需 找 出 乓的无 向分解 集 犯 ， 一 ， 并且 在 步骤 中 当从 取 出一个 几时可 以把赋于 乓。 的端点 凡 ， … 以 “ ” 极性 的过程省 去 算 法 中求 部分 的计算 时 间复 杂度 决定 于 步骤 一 是 口 户 ， 。 是 的 超 边 数 ， ‘是 的 叶点数 · 叶点 权 一 弓 是 用算法 ，计算 的 ， 其复 杂度参看 文献 【 需 要 进一 步研究 的 问题有 法 和 法 中 爪妙 的项数的计算和 估计 分 解 一 收缩法 在 超 图理 论 其他 问题 中的应用 分解 一 收缩 法 与并行算 法 的结合 参 考 文 献 ， ， 一 ， ’ ， ， 一 一 ， ， ， ， 一 一 吴新余 论 时基本互补划分表的产生 见 中国 电子 学 会线路 与系统学 会 “ 一般理论专题讨论会

Vol.18 No.6 黄汝激：陈氏基本互补划分法的改进与发展 ·563· 北京，1983 5马昭彦，全一男.k=7,8,9,10的基本互补划分的生成.见：中国电子学会线路与系统学会第五届年会 论文集.西安，1984.255~259 6黄妆激.通过有向k超树产生有向图的有向k树多项式.电子学报，1987,151)：1~9 7黄汝激.超网络的有向k超树分析法.电子科学学刊，1987,9(3)：244~255 8 Horowitz E.Fundamentals of Computer Algorithms.Potomac:Computer Science Press,1978.370 9黄汝激.混合图的有向k树多项式的产生和状态空间树.电子学报，1987,15(5)：8~14. Improvement and Development for Chen's Essential Complementary Partition Method Huang Ruji College of Automation and Information Engineering,USTB,Beijing 100083,PRC ABSTRACT By applying the direted hypergraph theory,the concepts of the decomposi- tion and contraction of a hyperedge are introduced.Chens essential complementary parti- tion (ECP)method for solving the cascade problem of two passive networks is improved to form a more efficient decomposition-contraction pair (DCP)method,then it is devel- oped to form the directed (positive-rooted)decomposition-contraction pair (PDCP) method,to solve the cascade problem of two active networks.Furthermore,it is developed to form the general decomposition-contraction (GDC)method,to solve the problem of finding symbolic network functions for the interconnection of several active networks. KEY WORDS symbolic network function,directed hypergraph theory,decomposition- contraction pair method

黄汝激 陈氏基本互补划分法 的改进 与 发展 北京 ， 马 昭 彦 ， 全一男 ， ， ， 的基本互补划分 的生 成 见 中国 电子 学 会线路 与 系统学 会第 五届 年 会 论文集 西安 ， 一 黄汝激 通过有 向 超树产生有 向图的有 向 树多 项式 电子学报 ， ， 月 一 黄汝激 超 网络的有 向 超树分析法 电子科学学刊 ， ， 科 一 叮 ， · 黄汝激 混合图的有 向 树多项式 的产生和状态空 间树 电子学报 ， ， 一 ， 月翻 ， ， ， 勿 ， · 汕 一 ， 一 一 ， ， 一 ， ，