Chan-Mai图定理的改进

D0I:10.13374/j.issn1001-053x.1982.02.030 北京钢铁学院学报 1982年第2期 Chan-Mai图定理的改进 自动化基础教研室黄汝激 擠 要 本文提出了关于Chan-Mai图的一个改进定理，它可用于分析含有任意多个 变量的线性系统和电子网络。这个改进定理表明，一般说来，Chan-Mai图定 理(1)、〔2)对于分析变量数超过5的线性系统和电子网络是不完全正确的。 一、定 义 下面给出的一些定义，有的是文献〔1)、〔2)中没有的，有的是文献〔1)、〔2)中对应定义 的推广。 l.Chan-Mai图Gs Chan-Mai图是伴随方阵A的一个有向图，或者说，是表示 含一个源变量xn+:的n阶线性代数方程组 AX=Bxa+1,A=〔a(axn,B=〔b,)ax1 (1) 或 ∑ax1=bixn+,i=1,2,,n (2).· =1 的一个有向图，记为G,(A),简记为Gs,图中有两行上下对齐的顶点，每行有个顶点，上 行顶点表示源变量系数b,i=1,2,…,,称为源系数頂点，下行頂点表示响应变量x, j=1,2,…,n,称为响应变量頂点，对应于系数a,1≠0，有一条权为a,的弧从点x,指向点 b,若a,1=0,则对应的弧(x1,b,)不存在。所以，图G,的弧集U(Gs)对应于方程组 (2)的系数方阵A=〔a11〕nxn。 2.图G1 把图G,中从点x出发的每条弧(x1,b)的权a:换为b,,对于A 中第列的每个O元素ak,=0,如果bx≠0，则应补画上一条权为bk的弧(x1,bk),然后 去掉所有权b,=0的弧，所得的图称为伴随方阵A,的图G,1(A),简记为G::。这里A!是 用列向量〔b,)nx1代替A中第j列后所得的方阵。图Gs,的弧集U(G:)对应于方阵A1。 3.分离S(Separation)给定图(G,或Gs,)的一个分离S是它的一个子图，满足下 列三个条件： (1)它含有该图(G,或G:)的全部頂点， (2)每个响应变量顶点x,正好发出一条弧， (3)每个源系数頂点b,正好接收一条弧（图1）。 所有弧都为垂直弧的分离称为么分离。 分离S中所有弧权的下标形成前n个自然数1,2，，n的一个置换，称为分离S的对应置 83

北 京 钢 铁 学 院 举 报 一 年第 期 一 图定理的改进 自动化 基 础教研 室 费汝激 商 要 本文提 出 了关于 一 图 的一个改进 定 理 它可用 于 分析 含有任 意多个 变量 的 线性 系统 和 电子 网络 。 这个 改进 定理表 明 ， 一 般 说来 ， 一 图定 理 〕 、 〔幻 对于分析变量数超过 的线性系统和 电子 网络是不完全正确的 。 一 、 定 义 下面 给出的一些定义 ， 的推广 。 一 图 有 的是文 献 〔 〕 、 〔幻 中没 有的 ， 有的是文献 〕 、 〔 中对应定义 一 图是伴 随方 阵 的一个有向图 ， 或者 说 ， 是表示 含一个源 变量 。 ， 的 阶线性代数方程组 。 ， ， 〔 ‘ 一 〕 。 二 。 ， ‘ 〕 。 二 乏 ‘ ， ， ‘ · ， ‘ ，， ， 一 ， 一 卜 的一个有 向图 ， 记 为 ， 简记 为 ， 图 中有两行 上下对齐的顶点 ， 每行有 个顶 点二上 行顶点表示源 变量 系数 ‘ ， ， ， 一 ， ， 称为源 系数厦点 ， 下行顶点表示响应变 ，， ， ， … ， ， 称为响应 变量填点 ， 对应于 系数 ‘ 笋 。 ， 有， 条权为 ‘ ，的弧 从点 ，指向点 ‘ ， 若 ‘ ， 。 ， 则对应 的弧 ，， ‘ 不存在 。 所以 ， 图 ， 的弧 集 对应于方程组 的系数方阵 〔 ‘ ， 〕 。 二 。 。 图 ， 把图 。 中从点 ，出发的每条弧 ，， ‘ 的权 ‘ ，换为 ‘ ， 对千 中第 列 的每个 元 素 、 ， ， 如 果 子 ， 则应补画 上一 条权为 的弧 ，， ， 然后 去掉所有权 ‘ 的弧 ， 所得 的图称为伴 随方阵 ，的图 ， ， ， 简记为 ，。 这 里 ，是 用 列 向量 〔 ‘ 〕 。 二 代 替 中第 列后所得 的方 阵 。 图 ，的弧 集 ， 对应于 方阵 。 分 离 给定 图 或 ， 的一个分 离 是它 的一个子图 ， 满足 下 列 三个条件 它 含有该 图 或 ， 的全部填点， 每个 响应变量填点 ，正好发出一条弧 ， 每个源 系数填点 ‘ 正好接收一条弧 图 。 所有弧都为垂直 弧 的分 离称为 么分 离 ， 分离 中所 有弧权的下标形成前 个 自然数 ， ， … ， 的一个置 换 ， 称为分离 的对应里 争 DOI ：10．13374／j ．issn1001－053x．1982．02．030

X11 图1分离S的一个例子 换。例如，图1所示分离S对应于下面的置换 P-(1g89g岛89g) =(1)(3)(24)(567)(810119) =(24)(567)(810119) (3) 式中置换P可分成五个独立的循环置换：其中(1)和(3)是一位循环置换，即不变下标， （24)是二位循环置换，，即对换，（567)和（810119)各为三位和四位循环 置换，三位和三位以上的循环置换统称为多位循环置换。 4.循环弧集U。 分离S中对应于一个独立循环置换的子弧集，称为循环弧集，记 为U:。循环弧集可分为三类： (1)垂直孤对应于不变下标，如图1中的弧（x1,b:)和(x,b3), (2)对称弧对(Sy mmetric pair)对应于对换，如图1中的弧对{(x2,b4), (x4 b2)} (3)多弧循环弧集对应于多位循环置换，如图1中的弧集{(x7,b。),(x,b。), (x,b)}和{(x,b11),(x11,b1a),(x1o,b),(xg,b)}。 在文献(1〕、〔2〕中没有引进多弧循环弧集的概念，而是引进“非对称支路(Asymme- tric branches)”的概念。一个非对称支路是指分离S中的一条弧，它不是垂直弧，也不 属于任何对称孤对。 ,根据高等代数〔3〕，每个置换P可唯一地分解为一些独立的循环置换的乘积，而且每一 个k位循环置换(k≥3)又可以表为k一1个对换的乘积： (i,i2,…,ix)=(i1,i2)(i1,is)…(i1,ik) (4) 用相反顺序的k-1个相反对换的乘积(is,i)(ik-1,i)…(i2,i)右乘上述k位循环 置换，可把它变为么置换（即恒等置换）。把一个置换P变为么置换所需要的对换个数称为 置换P的判数，记为dp。 对应地，每个分离S可唯一地分解为一些独立的循环弧集的和，而且每一个k弧循环弧 集{(xk,b,k-),（xik-1,b,k-2),…,(x1,b:)},如果对其源系数顶点依次施行 k:1个对换：(bk,b)，(b,k-1,bi),…,(b2,b)，可把它的所有弧都变成 垂直弧。把一个分离S变为么分离共需对其源系数顶点施行的对换个数称为该分离S的判 数，记为d,。判数为奇（偶）数的分离称为奇（偶）分离。 5.分离权f(s)(Separation weight)分离S中所有弧的权的乘积称为该分离 的权，记为f(S)。设图G,的k号分离Sk的n条弧的权为a1k1、a2*2…,ankn’则Sk的权为 f(Sk)=aikiazk2ankn (5) 分离权f(S)的符号sign f(S:)定义为 84

一 ， 一 一 ， 一 。 域 ， 麒 …， ， 一 一 二 一 ，侧 了山盆沈二 日﹄ 期琴护 换 。 例如 ， 图 所示分离 ” 萦才璧 图 分 离 的一 个例子 对应于下面 的置 换 二 、 夕 式 中置 换 可分成五个独立 的循环置 换 是二 位循环置换 ， 即对换， 其 中 和 和 是一位循环置 换 ， 即 不变下标， 各为三位和 四 位循环 置 换 ， 三位 和三位 以 上的循环置 换统 称为多位循环置 换 。 循环弧 集 。 分 离 中对应 于一 个独立 循环 置换 的 子 弧 集 ， 称为循 环弧 集 ， 记 为 。 。 循环弧 集可分为三 类 垂 直弧 对应于不变下标 ， 如图 中 均弧 ， 和 。 ， ， 对称弧对 对应于 对换 ， 如 图 中 ’ 勺弧 对 一 ， 〕 ， 。 ， ， 多弧循环弧 集 对应于多位循环置换 ， 如 图 中的弧 集笼 ， 。 ， 。 ， 。 ， 。 ， ， 和 。 ， ， ， 。 ， 。 ， 。 ， 。 ， 。 蛋 。 在文献 〔 〕 、 〔 〕中没有引进多弧循环弧 集的概念 ， 而是 引进 “ 非对称 支路 。 澎 ” 的概念 。 一个非对称 支路是指分 离 中的一 条弧 ， 它不是垂直弧 ， 也不 属于任何对称弧对 。 根据 高等代数 ， 每个置换 可唯一地分解为一些独立 的循环置换 的乘积 ， 而且每一 个 位循环置换 又可以表为 一 个对换的乘积 ， ， … ， 二 ， ， … ， 用 相反 顺 序 的 一 个相反 对换 的乘积 ， 卜 ， 卜二 ， 右乘 上述 位循环 置娘， 可 把 它变为 么置换 即恒 等置换 。 把一个置换 变为 么置换所需要 的对换 个数 称为 置换 的 判数 ， 记为 。 对应 地 ， 每个分 离 可 唯一地 分解为一些 独立 的循环弧 集的和 ， 而且 每一 个 弧循环弧 集 笼 “ ， ‘ 、 一 ， ‘ 卜 ， ‘ 卜 名 ， … ， ， ， 、 ， 如 果对 其源 系数顶点 依次施行 耘一 个对换 ‘ ， ‘ ， ‘ 卜 ， ‘ ， … ， ‘ ， ‘ ， 可 把它 的所有 弧都变成 垂 直弧 。 把一个分 离 变为 么分 离共需对其源 系数 顶 点 施 行 的对换个数 称为该分 离 的判 数 ， 记为 。 判数为 奇 偶 数 的分 离称为 奇 偶 分 离 。 分 离权 分 离 中所有弧 的权 的乘积 称为该 分 离 的权 ， 记为 。 设 图 的 号分 离 盆的 条弧 的 权为 ， ‘ 、 、 … ， ” ， 则 的权为 ‘ ‘ … 。 。 分离权 冬。 的符号 咨 定义为 吕

sign f(Sx)=(-1)4sx （6). 式中dsk为Sk的判数。 文献〔1)、〔2)把分离权称为分离积(Separation product),记为Sp。分离Sk的 分离积记为Sx。 4 二、Chan-Mai图定理的改进 根据上述分离与置换的对应关系容易得到下面的引理。 引理1如果分离S含有n条孤和ns个独立循环弧集，S的判数为ds,S的对应置换P 的判数为d,那么有 dp=ds=n-ns=n-(nv np nm) (7) 式中，nv一分离S中的垂直弧数， np一分离S中的对称弧对的对数， nm一一分离S中多弧循环弧集的数目。 应用这个引理可以证明下面的引理2，进而推得改进定理。这个定理是文献〔1)、〔2)中 关于Chan-Mai图的对应定理的改进。 引理2设Gs(A)为n阶方阵A=〔a:,)nxn的伴随Chan-Mai图，那么行列式detA 的非零项gK=（-l)4r《a1k1a2k2…ankn一一对应于而且等于图Gs(A)的带符号分离权 〔sign f(Sx)f(Sk),从而 detA=∑(sign f(S)f(S)=(-1)°∑(-1)x f(Sk) (8) SkCG S1CG。 式中；Sx一Gs（A)的第k号分离s f(Sx)=a1k1a2k2…ankn一分离Sk的权， a1k1,a2k2,,aakn一Sk中n条弧的权， k=k1k2…kn一1,2，…，n的一个排列影 nsk一Sx中独立循环孤集的数目， 求和是对Gs(A)所含的全部分离Sx进行的。 证：根据行列式的性质和分离及分离权的定义，detA中的非零项gk=(-1)·a1k1 44a(这里d是g:的下标置换Rk=(,片“，)的判数)-一对应于它的下标里 5 换Px,而Px又一一对应于Gs（A)中的分离Sk,所以gk一一对应于Sx,而且gk的量a11 a2k2…aaka=f(Sx)〔见式(5)。另外，根据引理1有(-1)4pk=（-1)4sk=(-1)a-sk= 0 (-1)n+sk,所以 gx=(-1)sxf(Sx)=(sign f(SK))f(SK) detA=∑8x=∑(sign 1(Sx))f(Sx)f(Sx)=(-1)∑(-l)sf(5) k Sk CG 证毕。 由于图G:,(A)实际上是方阵A,的伴随Chan-Mai图，因此从引理2可得下面的推 论。 推论 行列式detA,的非零项一一对应于而且等于图G,,(A,)的带符号分离权 85

主 式中 为 的判数 。 文献 〕 、 幻 把分 离权称为分 离积 分 离积 记为 ， ‘ 。 一 。 ， ， 记为 。 分 离 的 二 、 一 图定理 的改进 根据 上述分 离与置 换 的对应关系容 易得到下面 的 引理 。 引理 如 果分 离 含有 条弧 和 个独立循环弧 集 ， 的判数为 。 ， 的对应里换 的 判数为 ， 那 么有 二 一 一 ， 。 式 中 － 分 离 中的垂直 弧数， ’ － 分 离 中的对称弧 对的对数， 一一分 离 中多弧循环弧 集的数 目 。 应 用这个引理可 以 证 明下面 的 引理 ， 进 而推得改进定理 。 这个定理是文献 〔 〕 、 〕中 关于 一 图 的对应定理 的改进 。 引理 设 为 阶方阵 〔 ‘ ， 〕 二 。 的伴随 一 图 ， 那 么行列式 的非零项 一 ” ‘ … 。 一 一 对应 于 而且 等于 图 的带符号 分离权 〔 〕 ‘ ， 从而 艺 〔 ‘ ‘ 〕 “ ‘ · ‘ 一 ‘ ， 乏 ‘ 一 ‘ 。 “ “ ‘ ， ‘ 一 卜己 式中 － 的 第 号分离 ‘ … 。 ‘ 。 － 分 离 ‘ 的权， 、 ， ‘ ， … ， 。 － ‘ 中 条弧 的权， … 。 － ， ， … ， 的一个排列 ， 、 － ‘ 中独立循环弧 集的数 目， 求和是对 所 含的全部分 离 进行 的 。 证 根据 行列 式 的性质和 分 离及分离权的定义 ， 中的非零项 一 ‘ ，‘ ， ， ， … 。 ， 。 〔这 里 ， 是 ‘ ， 的 下标置 换 ， 一 产 ‘ ” 乎、 的判数 〕一 对应于 它 的下标里 吕 “ ” ’ “ “ “ ‘ 趋 土 ‘ “ 儿 “ “ ， ’ ” ，且 状 ‘ 一 … 。 少 “ 沙 月琳 沪 八 肠 。 “ ’ ” ’二 换 ， ， 而 又一 一 对应于 中的分 离 ‘ ， 所 以 一一对应于 ‘ ， 而且 的 、 · ‘ · 、 。 ‘ 见式 〕 。 另外 ， 根据 引理一有 一 ， 一 、 一 “ 一 、 一 “ 、 ， 所 以 一 〕 ‘ ， 乏“ 二 乏 〔 ， ‘ “ ‘ ，〕 “ ‘ ，〕 “ ， ‘ 一 ‘ ， ’ 一 ” · 七口 证毕 ， 由于 图 ， ， ， 实际 上是方阵 的伴随 一 图 ， 因此 从 引理 可得 下面 的推 推论 行列 式 ， 的非零项一一对应于 而且等于图 ， ， 的带符号分离权 尽争

〔sign.f(S)f(S),从而 5 detA,=∑〔sign f(S)f(S)=(-1)°∑（-1)s1fS) (9)· 8,G0,1 式中：S一G1(A)的第I号分离 f(S,)一分离S的权， n,1一S,中独立循环孤集的数目， 求和是对G,,(A)所含的全部分离S,进行的。 根据引理2及其推论可导出下面的定理。 Chan-Mai图定理（改进）如果系数方阵A是满秩的，则线性代数方程组(1)或(2) 的解可表示成： ·(-1)1f(S) =det ALSICG.1 X1 xn+i det A ,。（-1)Pkf(S),j=1,2,…,n (10) SkGG。 式中各符号的意义与引理2及其推论中的相同。 证：根据解线性代数方程组的克莱姆法则，方程组(1)或（2)的解为 会 Xn+1 再应用引理2及其推论，即把式(8)和(9)代入上式，就可推得式(10)，证毕。 三、与Chan-Mai图定理的比较 文献〔1)、〔2)中所给出的关于Chan-Mai图的定理如下， Cha-Mai图定理在一个含n变量、n个独立方程的线性代数方程组 ∑a41x1=b:(i=1,2,…,n) (11) 中，变量x,的值等于 ∑(sign Sp,)Sp,(G) X)= (sign Sr。(Gs)一，j=1,2,…,n (12) 式中：5 ign Srx=(-1)”r+“~, 对于n4中0(k=t或p) =(-1)8k,对于n,=0 (13) 这里：n,一一图Gs的r号分离S,的非对称支路数： ns,一图Gs1的τ号分离S,中的对称孤对数， Sp,(G,)一G,,的τ号分离S.的分离积， n·。一图Gs的p号分离S。的非对称支路数， ns。一图Gs的p号分离S。的对称弧对数， Sp,(Gs)一Gs的p号分离S,的分离积， 而且分母和分子的求和是分别对Gs和G:,所含的全部分离S,和S,进行的。 当源变量x。+1=1时，改进定理的公式(10)可改写成 86

〔 琪 〕 ， 从而 ‘ ， 艺 〔 ， ‘ “ ，〕 “ ， ‘ 一 刀己 一 艺 汤 盆口 一 式 中 － ， ， 的第 号分离， － 分离 ，的权， － 中独立循环弧 集的数 目， 求和是对 ， ， 所 含的全部分离 进行 的 。 根据 引理 及 其推论可 导出下面 的定理 。 加 一 从 圈定理 改进 如果系数方阵 是满袂 的 ， 的解可表示成 公 一 一 ” ， 一 则线性代数方程组 或 笼 证毕 ， 通兰业红 一 一 一 二 万币石不五瓦下 一 ， “ ， ， “ ’ ， ” 式中各符号的意义 与引理 及其推论 中的相 同 。 证 根据解线性代数方程组 的克莱姆法则 ， 方程组 或 的解为 卫丝立 七 一 再应用 引理 及其推论 ， 即把 式 和 代入 上式 ， 就可推得式 三 、 与 一 图定理 的 比较 文献 〔 〕 、 幻 中所给出的关于 一 图的定理如下 一 们 定理 在一个含 变量 、 个独立方程 的线性代数方程组 艺 ‘ ， ， “ ‘ ‘ ’， ， … ， 一 盆 中 ， 变 ，的值等于 公 ， ， ， 名 ， ， ， ， … ， 式 中 ‘ ‘ 一 ， · 一 ’ ’ 一 ， ， 对于 ， 对于 、 尹 ， 或 。 。 这 里 “ － 图 ，的 ， 号分离 、 的非对称支路数， ” ‘ ， － 图 的 ‘ 号分 离 中的对称弧对数， ， － ，的 号分 离 的分离积， “ ， － 图 的 号分离 ， 的非对称支路数， ” ， － 图 的 号分离 ， 的对称弧对数， ， ， － 的 号分 离 ， 的分 离积 ， 而且 分母和分 子 的求和是分别 对 和 ，所 含的全部分 离 ， 和 ， 进行 的 。 当源 变盘 。 ， 时 ， 改进定理的公式 可改 写成 砂争

公（-1)"®f(S)· x-SICG ∑。(-1)kf(S.) SxCGs z（-1)-n81f(S) -SICG: -9f(5） ,j=1,2,n (14) z(-1) SxCG, 现在可把式(14)与式(12)进行比较。设分离Sk含有nv个垂直弧、nP个对称弧对 和nmk个多弧循环环集，而且nmk个多弧循环弧集的弧数各为t,t2,…,t。k'那么Sx所 含弧数为 nmk n=avk+2at+∑t, (15) i=1 于是根据上式和式(7)可推得 口mk n-nsx=n-(avx+aox+nm)=nox+2to-nmk (16) i=1 适当选择下标k和p的编号，可使k=P,从而 Sk=S。,f(Sk)=Sp。(Gs) (17) nmk npk=ns。' t=a, (18) i=1 于是从式(16)和(18)得到 (-1)-fk=（-1)8。n。mk (19a) 同理可得 （-1)-091=（-1)5,+n,a1 (19b) 式(19a)和(19b)合称式(19)。比较式(19)和(13)可得下面的墙论： (1)当分离Sk和S:的多弧循环弧集个数nmk和nm:等于0或奇数时，式(13)与(19) 的计算结果相同，从而式(12)与(14)的计算结果相同。 (2)当nmk和nm:为≥2的偶数时，式(13)与(19)的计算结果相反，一个为+1，另 一个为-1。这种情况下，式(13)是不正确的，从而Chan-Mai图定理是不正确的。只有 改进定理及其公式(10)、(14)是正确的。容易看出，当·≤5时，一个分离中不会含有多 于一个的多弧循环弧集。当=6时，一个分离中就可能含有两个多弧循环弧集，每个多孤 循环弧集含有三条弧。因此，当n>5时，一般说来，Chan-Mai图定理是不正确的。 文献〔l)、〔2)中的Chan-Mai图定理的缺点是：它没有把分离与置换相对应，从而没 有考虑到多弧循环弧集的概念，而是把所有多弧循环弧集中的弧不加区别地笼统称为非对称 支路，所以导出的公式(13)不完全正确。 例：考虑下面的方程组： 87

艺 一 污 ， 云 名 ， ，… ，刀 名 ‘ ， 现在可把式 与式 一 ’ ” ‘ 一 “ 一 ‘ 一 卜 ， “ ’ 进行 比较 。 设 分 离 ‘ 含有 ， 个垂 直弧 、 ， 个对称弧 对 和 ， 、 个多弧循 环环集 ， 而且 二 ‘ 个多弧 循环弧 集的弧数 各为 ， ， 一 ， 。 。 ， 那 么 所 含弧数为 胜 · 艺“ 二 于是根据上式和式 可推得 一 ‘ 一 ‘ 、 二 ‘ ‘ 一 ‘ 适 当选择 下标 和 的编号 ， 可使 ， 从而 、 。 ， 、 ， ， 七 ， 、 ， 乏 ‘ · 。 于 是从式 和 得到 一 一 ， “ 一 “ ， 奋 ’ · ，一 二 同理可得 一 式 和 合 称式 王 一 · · 厂 。 “ 。 ‘ 比较式 和 一 可得下面 的摘论 当分离 和 ‘的多弧 循环弧 集个数 二 ‘ 和 。 ‘等于 或奇数时 ， 式 与 的计算结果相同 ， 从而式 与 的计算结果 相同 。 当 和 二 为 的偶数时 ， 式 与 的计算结果相反 ， 一个为 ， 另 一 个为 一 。 这种情况下 ， 式 · 是不正 确的 ， 从而 一 图定理是不正 确的 。 只 有 改进定 理 及 其公 式 。 、 是正 确的 。 容 易看 出 ， 当 《 时 ， 一个分 离中不会 含有多 于一个的多弧 循环弧 集 。 当 时 ， 一个分 离中就可 能 含有两个多弧循环弧 集 ， 每个多弧 循 环弧 集含有三 条弧 。 因此 ， 当 时 ， 一般说来 ， 一 图定理是 不正 确的 。 文献 〔 〕 、 〔 〕中的 一 图定理 的缺点是 它没有把分离与置 换相对应 ， 从而没 有考虑到多弧 循 环弧 集的概 念 ， 而是把所有多弧 循环弧 集中的 弧 不加 区别 地笼统称为非对称 支路 ， 所 以 导出的公式 不完全正 确 。 例 考虑下面的方程组