有向功能關(guān)系圖ofrg關(guān)聯(lián)矩陣右逆的形成

有向功能關(guān)系圖ofrg關(guān)聯(lián)矩陣右逆的形成

rg函數(shù)關(guān)系圖（或函數(shù)關(guān)系圖）是描述機(jī)械產(chǎn)品二維結(jié)構(gòu)的圖模型。一般,它為一簡(jiǎn)單有向連通圖,研究OFRG關(guān)聯(lián)矩陣右逆的圖特征是實(shí)現(xiàn)OFRG模型功能的關(guān)鍵。筆者對(duì)OFRG關(guān)聯(lián)矩陣右逆的形成進(jìn)行探討。揭示出OFRG關(guān)聯(lián)矩陣右逆、n-1階傳導(dǎo)矩陣伴隨陣的圖特征;提出一種尋找OFRG模型全部生成樹(shù)的方法。1點(diǎn)v的關(guān)聯(lián)矩陣設(shè)n階簡(jiǎn)單有向連通圖D(V,U)具有m(≥n-1)段弧uk(k=1,2,…,m).在其完全關(guān)聯(lián)矩陣Me中刪去參考點(diǎn)vσ對(duì)應(yīng)的行所得到的矩陣Mσ稱為圖D關(guān)于頂點(diǎn)vσ的關(guān)聯(lián)矩陣,且rankMσ=n-1.n-1階方陣C?MσMTσ,稱為圖D關(guān)于vσ的n-1階傳導(dǎo)矩陣(T為轉(zhuǎn)置符),具有下列性質(zhì)。1)行列式detC=τ(D),(τ(D)為圖D中生成樹(shù)的數(shù)目);2)矩陣C中元cij為:cij={dii=jdi為圖D中頂點(diǎn)vi的度；0-1i≠j當(dāng)頂點(diǎn)vi與vj不相鄰當(dāng)頂點(diǎn)vi與vj相鄰cij=???dii=jdi為圖D中頂點(diǎn)vi的度；0?1i≠j當(dāng)頂點(diǎn)vi與vj不相鄰當(dāng)頂點(diǎn)vi與vj相鄰3)矩陣C為M方陣,其逆存在且C-1≥0.2矩陣c的伴隨矩陣c*2.1生成n-2階大子陣在圖D的關(guān)聯(lián)矩陣Mσ中刪去第t行得到的矩陣記為Mtσtσ.根據(jù)畢內(nèi)-柯西定理,矩陣C*中元c*ij由下式計(jì)算c*ij=(-1)i+jl∑k=1detΜiσ(Uk)?detΜjσ(Uk)(1)其中Mtσ(Uk)(t=i,j),為矩陣Mtσ的n-2階大子陣;l=cn-2m,Uk為由圖D的弧集U中任意n-2段弧組成的弧集。即Uk是每次在U中選取n-2段弧的不同組合中的一種。2.2元素m2h2的余子式引理1若n階簡(jiǎn)單有向連通圖D的矩陣Mtσ,其某大子陣的行列式非零,則有detMtσ(Uk)=±1.證明設(shè)detMtσ(Uk)≠0.根據(jù)行列式的性質(zhì),Mtσ(Uk)每列至少有一個(gè)非零元(最多有兩個(gè)非零元,且為1、-1).Mtσ(Uk)中至少有一列只有一個(gè)非零元±1.否則Mtσ(Uk)每列均有兩個(gè)非零元,將前n-3行加到第n-2行上,Mtσ(Uk)的第n-2行變?yōu)槿?。故detMtσ(Uk)=0,與假設(shè)矛盾。令Mtσ(Uk)的第h1列元素mλ1h1=±1,其余元素為零。按第h1列展開(kāi),detMtσ(Uk)=±(-1)λ1+h1·|Mtσ(Uk)λ1h1|,其中|Mtσ(Uk)λ1h1|為Mtσ(Uk)中元素mλ1h1的余子式。|Mtσ(Uk)λ1h1|中至少有一列僅有一個(gè)非零元。否則可推得|Mtσ(Uk)λ1h1|=0,從而有detMtσ(Uk)=0,這與假設(shè)矛盾。設(shè)Mtσ(Uk)λ1h1中第h2列除第λ2行元素為±1,其余元素均為零,則有detMtσ(Uk)=±(-1)λ1+h1·±(-1)λ2+h2·|Mtσ(Uk)λ1h1,λ1h2|.其中|Mtσ(Uk)λ1h1,λ2h2||是|Mtσ(Uk)λ1h1|中元素mλ2h2的余子式。依此類推可知,detMtσ(Uk)=±1.引理得證。對(duì)于M1σ、M2σ同一弧集uk的大子陣列行列式之積有引理2.引理2矩陣Mσ中第1行、第2行對(duì)應(yīng)矩陣M1σ、M2σ同一弧集uk的大子陣的行列式之積非零時(shí),其積等于-1.證明由于n=1,2時(shí),Mtσ不存在,故令n≥3.采用歸納法證明。當(dāng)n=3時(shí),根據(jù)引理1及Mσ的定義(同列的非零元異號(hào))得:detM1σ(Uk)·detM2σ(Uk)=m1j1m2j1=-1.故引理成立。當(dāng)n=4時(shí),令:c1=detΜ2σ(Uk)=|m1j1m1j2mλj1mλj2|c2=detΜ1σ(Uk)=|m2j1m2j2mλj1mλj2|不失一般性。當(dāng)m1j1≠0時(shí),因c2≠0,故m2j1、mλj1不能同時(shí)為零。1)若m2j1≠0,則mλj1=0,且m1j1·m2j1=-1.因c1≠0,故mλj2≠0.c1,c2均按第1列展開(kāi)得:c1?c2=m1j1A1j1?m2j1A2j1=-A1j1A2j1Atj1為行列式ct中元mtj1的余子式(t=1,2).顯然有:A1j1=A2j1,故c1·c2=-1.2)若mλj1≠0,則m2j1=0,因c1≠0,c2≠0,故必有m2j2≠0,m1j1+mλj2≠0,而m1j2mλj2=0.即此時(shí)m1j2,mλj2必恰有一個(gè)為零。c1、c2均按第1列展開(kāi)得:c1?c2=(m1j1A1j1+(-1)2+1mλj1Aλj1(c1))?(-1)2+1mλj1Aλj1(c2)=A1j1Aλj1(c2)+Aλj1(c1)Aλj1(c2)Aλj1(ct)為ct中元mλj1的余子式(t=1,2).根據(jù)上述條件得:當(dāng)mλj2=A1j1(c1)≠0時(shí),m1j2=Aλj1(c1)=0有c1?c2=A1j1Aλj1(c2)=-1同理,當(dāng)m1j2≠0時(shí),mλj2=0有:c1?c2=Aλj1(c1)Aλj1(c2)=-1故當(dāng)n=4時(shí),引理成立。假設(shè)n=N-1時(shí),引理成立,令n=N,此時(shí):c1=detΜ2σ(Uk)=[m1j1m1j2?m1jn-2mλ1j1mλ1j2?mλ1jn-2mλ2j1mλ2j2?mλ2jn-2????mλn-3j1mλn-3j2?mλn-3jn-2]c2=detΜ1σ(Uk)=[m2j1m2j2?m2jn-2mλ1j1mλ1j2?mλ1jn-2mλ2j1mλ2j2?mλ2jn-2????mλn-3j1mλn-3j2?mλn-3jn-2]1)當(dāng)mtj1≠0(t=1,2),c1、c2均按第1列展開(kāi)得(此時(shí),mλij1=0,i=1,2,…,n-3):c1?c2=m1j1A1j1?m2j1A2j1因m1j1·m2j1=-1,A1j1=A2j1=±1.故c1·c2=-1.2)當(dāng)m1j1≠0,m2j1=0時(shí),因c2≠0,故必有mλkj1≠0,mλtj1=0(t=1,2,…,k-1,k+1,…,n-3).c1、c2均按第1列展開(kāi)得:c1?c2=(m1j1A1j1+(-1)k+2mλkj1Aλkj1(c1))?(-1)k+2mλkj1Aλkj1(c2)=(-1)k+3A1j1Aλkj1(c2)+Aλkj1(c1)Aλkj1(c2)按引理1,ct之值必為±1(t=1,2).故以上兩項(xiàng)必恰好只有一項(xiàng)非零。令A(yù)k1j1為A1j1的第k行作k-1次互換到第1行位置時(shí)的行列式,故A1j1=(-1)k-1Ak1j1.代入c1·c2中得:c1?c2=Ak1j1Aλkj1(c2)+Aλkj1(c1)Aλkj1(c2)由上述證明,結(jié)合歸納法假設(shè)有:c1?c2=Ak1j1Aλkj1(c2)=-1或c1?c2=Aλkj1(c1)Aλkj1(c2)=-1故當(dāng)n=N時(shí),引理成立。綜上所述,引理成立。引理3對(duì)矩陣Mσ的第i行、第j行的Miσ、Mjσ,若其對(duì)同一弧集Uk大子陣行列式之積非零,其積等于(-1)i+j.證明設(shè)bi=detMiσ(Uk),bj=detMjσ(Uk),因bibj≠0,故bi≠0,bj≠0.當(dāng)i=j時(shí),bi=bj,由引理1得:bibj=(-1)i+j當(dāng)i≠j時(shí),不失一般性設(shè)i<j.對(duì)Miσ的第i行作i-1次行互換,將第i行換到第1行,則行列式bi變?yōu)閏i.對(duì)Mjσ的第j行作j-2次行互換,將第j行換到第2行,則行列式bj變?yōu)閏j.故bi=(-1)i-1ci,bj=(-1)j-2cjbibj=(-1)i+j-3cicj根據(jù)引理2得:bibj=(-1)i+j-4=(-1)i+j綜上所述,引理成立。2.3子圖中的二元相關(guān)證明在有m段弧的n階簡(jiǎn)單有向連通圖D(V,U)中去掉m-n+2段弧得到的圖D的子圖稱為圖D的n-2子圖。其弧集Uk恰含n-2段弧。定義1在n階簡(jiǎn)單有向連通圖D(V,U)中滿足detMtσ(Uk)≠0的n-2子圖稱為圖D關(guān)于頂點(diǎn)vt、vσ的n-2主子圖,記為Htσ.根據(jù)定義,圖D的主子圖Htσ是與detMtσ(Uk)(≠0)1-1對(duì)應(yīng)的。若記ˉVtσ=V-Vt∪vσ(t≠σ),則圖D的主子圖具有下述性質(zhì)。定理1n階簡(jiǎn)單有向連通圖D(V,U)的主子圖Htσ具有以下性質(zhì):1)ˉVtσ中任一元至少與Uk中一元相關(guān)聯(lián);2)Uk中任一元至少與ˉVtσ中一元關(guān)聯(lián);3)子圖中無(wú)回路;4)子圖由兩個(gè)分圖組成,且vt、vσ各在一個(gè)分圖上。證明因主子圖Htσ與detMtσ(Uk)≠01-1對(duì)應(yīng),由行列式的性質(zhì)及引理1證明知:因detMtσ(Uk)≠0,故其每行、每列必有非零元,故其對(duì)應(yīng)的Htσ具有性質(zhì)1)和2).性質(zhì)3)的證明:若在Uk中有k段弧組成回路,其頂點(diǎn)集Vk?ˉVtσ,則其在detMtσ(Uk)中的對(duì)應(yīng)列均含1,-1兩個(gè)非零元。將其中的K-1列累加到剩下的一列上,此列變?yōu)槿?故detMtσ(Uk)=0,與假設(shè)矛盾。性質(zhì)4)的證明:因Htσ有n個(gè)頂點(diǎn),但只有n-2段弧。由n階連通圖的連通條件知,Htσ由若干分圖組成。設(shè)Htσ由k個(gè)分圖組成,各分圖的弧段數(shù)為lλ(λ=1,2,…,k).由于每個(gè)分圖都是無(wú)回路的連通圖,故每個(gè)分圖必為一棵樹(shù)(孤立點(diǎn)構(gòu)成的分圖是一種特殊的樹(shù),稱為樹(shù)種)。由樹(shù)圖頂點(diǎn)數(shù)與弧段數(shù)的關(guān)系得:k∑λ=1lλ=n-2Htσ的頂點(diǎn)數(shù)p=k∑λ=1lλ+k=n-2+k當(dāng)k=1時(shí),p=n-1與假設(shè)矛盾;當(dāng)k>2時(shí),p>n與假設(shè)矛盾;只有當(dāng)k=2時(shí),p=n,故主子圖Htσ有且只有兩個(gè)分圖。設(shè)V1、V2分別為Htσ兩個(gè)分圖的頂點(diǎn)集,且vt∈V1,vσ∈V1,則V2?ˉVtσ.故Mtσ(Uk)包含了頂點(diǎn)集為V2的一個(gè)樹(shù)圖完全關(guān)聯(lián)矩陣的全部行向量。由于這組行向量線性相關(guān),累加時(shí)可使Mtσ(Uk)的一行全部為零,故必有detMtσ(Uk)=0.與假設(shè)矛盾。證畢定義2在子圖中,若頂點(diǎn)vi、vj各在一個(gè)分圖中,稱頂點(diǎn)vi、vj分離。2.4n-2子圖真值向量及運(yùn)算定義31×l階向量Ct(l=Cn-2m),若滿足Ctk={1detΜtσ(Uk)≠00detΜtσ(Uk)=0k=1?2???l稱向量Ct為圖D關(guān)于發(fā)點(diǎn)vt、受點(diǎn)vσ的n-2子圖真值向量。簡(jiǎn)稱子圖向量。顯然,向量Ct的每個(gè)元對(duì)應(yīng)著圖D的一個(gè)n-2子圖。其中非零元對(duì)應(yīng)著圖D的主子圖Htσ.向量Ct的幾種運(yùn)算:1)向量元素求和Σ?ΣCt?∑kCtk;2)向量差δCij,δCij?Ci-Cj;3)向量分位積Cij,Ci=(Cik),Cj=(Cjk),k=1,2,…,l,則?Cij=Ci?Cj?(CikCjk).由?Cij的定義,若Ct(t=i,j)中非零元的個(gè)數(shù)為nt,則向量?Cij中非零元的個(gè)數(shù)n?≤min{ni,nj}.當(dāng)i=j時(shí),n?取最大值n?=ni.4)差積和運(yùn)算Cijt,Cijt?Σ(δCij?Ct);由Ct的定義,根據(jù)定理1,上述運(yùn)算結(jié)果的圖意義如下:a.ΣCt為使detMtσ(Uk)≠0的主子圖數(shù)目;b.δCij中非零元對(duì)應(yīng)著頂點(diǎn)vi、vj不同在一個(gè)分圖上的主子圖。其中正元對(duì)應(yīng)著頂點(diǎn)vi與vj、vσ分離的主子圖;負(fù)元對(duì)應(yīng)著頂點(diǎn)vj與vi、vσ分離的主子圖;c.?Cij中非零元對(duì)應(yīng)著頂點(diǎn)vi、vj同在一個(gè)分圖上,且與頂點(diǎn)vσ分離的主子圖;d.δCij?Ct中非零元對(duì)應(yīng)著頂點(diǎn)vi(vj)與vt同在一個(gè)分圖上,頂點(diǎn)vj(vi)與vσ同在另一分圖上的主子圖。2.5“多元”圖的意義根據(jù)子圖真值向量的定義及運(yùn)算,結(jié)合引理3,公式(1)可寫(xiě)為:C*ij=Σ(Ci?Cj)=Σ?Cij(2)因此,伴隨陣C*完全由圖D(V,U)的各子圖真值向量決定,且各元具有明確的圖意義。其圖意可歸結(jié)為下述定理,定理的證明已由上述分析得出。定理2n階簡(jiǎn)單有向連通圖D(V,U)的n-1階傳導(dǎo)矩陣C的伴隨陣C*中元C*ij之值等于弧段數(shù)為n-2,頂點(diǎn)數(shù)為n,頂點(diǎn)vi、vj連通,且與頂點(diǎn)vσ分離的主子圖數(shù)目。若頂點(diǎn)vσ為頂點(diǎn)vi、vj間的斷點(diǎn),則C*ij=0.且C*ij(i=j)為對(duì)應(yīng)行、列的最大元。根據(jù)定理1知:若在圖D的一個(gè)n-2主子圖的兩個(gè)分圖間加上一段弧uk(∈U,?Uk),則子圖變?yōu)橐粯?shù)圖。此時(shí),圖中每個(gè)頂點(diǎn)與受點(diǎn)vσ間有且只有一條路(半道路)。3m左右分支矩陣3.1廣義隨機(jī)陣m因矩陣Mσ行滿秩,令MTσ為其轉(zhuǎn)置矩陣,則Mσ的右逆為:M-σR=MTσ(MσMTσ)-1根據(jù)上節(jié)定義得:Μ-σR=1τΜΤσC*=1τΜ*σ(3)其中M*σ?MTσC*,稱為Mσ的廣義伴隨陣;而τ?det(MσMTσ)為圖D中生成樹(shù)的數(shù)目。3.2廣義隨機(jī)陣與m中元的相關(guān)關(guān)系定義3頂點(diǎn)vt到vσ間的路上一弧ui,當(dāng)ui指向vσ,則稱ui在路中為正向;當(dāng)ui背離vσ,稱ui在路中為負(fù)向。定理3n階簡(jiǎn)單有向連通圖D(V,U)關(guān)聯(lián)矩陣Mσ的廣義伴隨陣M*σ中元(M*σ)ij之值等于弧ui(∈U)在頂點(diǎn)vj到vσ的路上出現(xiàn)的次數(shù);或正、負(fù)向出現(xiàn)次數(shù)的代數(shù)和。證明因M*σ=MTσC*,設(shè)(MTσ)i為MTσ的第i行向量(對(duì)應(yīng)弧段為ui(∈U)).由矩陣Mσ的定義,(MTσ)i中非零元的個(gè)數(shù)λ滿足:1≤λ≤2.1vj到v道路的次數(shù)設(shè)計(jì)(ΜΤσ)ij=(ΜΤσ)i?C*j=(ΜΤσ)it?C*tj由公式(2),C*tj=Σ?Ctj,代入上式得:(ΜΤσ)ij=(ΜΤσ)it?Σ?Ctj根據(jù)向量?Ctj非零元的圖意義知:弧ui將其非零元對(duì)應(yīng)的兩個(gè)分圖組成的主子圖連為一樹(shù)圖,形成了一條vj到vσ的路,故ui必在此路上。又由于?Ctj的全部非零元同號(hào),且對(duì)應(yīng)著所有vj、vt連通,且與vσ分離的主子圖,故Σ?Ctj為弧ui包含在vj到vσ路上的次數(shù)。當(dāng)(ΜΤσ)it={1ui在路中取正向-1ui在路中取負(fù)向故(MTσ)ij為ui在vj到vσ的路上正(負(fù))向出現(xiàn)次數(shù)的代數(shù)和。若vσ為vj、vt間的斷點(diǎn),則vj、vt連通,且與vσ分離的主子圖不存在,?Ctj=0,故(M*σ)ij=0,此時(shí)弧ui不包含在任何一條vj到vσ的路上。2結(jié)構(gòu)參數(shù)及關(guān)聯(lián)矩陣(Μ*σ)ij=(ΜΤσ)i?C*j=(ΜΤσ)it1C*t1j+(ΜΤσ)it2C*t2j由公式(2),C*t1j=Σ?Ct1j,C*t2j=Σ?Ct2j代入上式(Μ*σ)ij=(ΜΤσ)it1Σ?Ct1j+(ΜΤσ)it2Σ?Ct2j化簡(jiǎn)得:(ΜΤσ)ij=(ΜΤσ)it1Σ(δCt1t2?Cj)=(ΜΤσ)it1Ct1t2j由向量δCt1t2?Cj中非零元的圖意義知:弧ui將其對(duì)應(yīng)的兩個(gè)分圖組成的主子圖連為一樹(shù)圖,形成一條vj到vσ的路,故ui必在此路上。又因向量δCt1t2?Cj中全部為1的元對(duì)應(yīng)著所有vt1、vj連通,且與vσ分離,vt2、vσ連通的主子圖,記總數(shù)為τ1;全部為-1的元對(duì)應(yīng)著所有vt2、vj連通,且與vσ分離,vt1、vσ連通的主子圖,記總數(shù)為τ2.此時(shí),(MTσ)it1=1,(MTσ)it2=-1,故Ct1t2j為弧ui在vj到vσ路上正、負(fù)向出現(xiàn)次數(shù)的代數(shù)和。由此知:當(dāng)τ1=τ2時(shí),(M*σ)ij=0;當(dāng)vσ是vj與vt1、vt2間的斷點(diǎn)時(shí),(MTσ)ij=0.綜上所述定理3成立。定理3即為n階簡(jiǎn)單有向連通圖關(guān)聯(lián)矩陣廣義