帶ray可解帶ray有向圖及其基礎圖的特征刻畫

帶ray可解帶ray有向圖及其基礎圖的特征刻畫

1基于最大周延式的降階模型近年來，一些科學家將符號矩陣推廣到復合字段的模型矩陣中，并對符號矩陣理論中的一些重要結論進行了重新推廣。涼山（z）。于是若z=reiθ(其中r>0),則ray(z)=eiθ.當z為實數(shù)時,ray(z)=sgn(z)即為z的符號.一個復矩陣A的ray模式,記作ray(A),是把A的每個元素aij換成ray(aij)之后所得的矩陣.所有與A有相同ray模式的矩陣構成的矩陣類稱為是A的ray定性矩陣類,記作Q(A).即有:Q(A)={B|ray(B)=ray(A)}.當A為實矩陣時,A的ray模式ray(A)就是A的符號模式sgn(A),而Q(A)就是A的定性矩陣類.可以將一些在(實)符號矩陣理論中的重要的矩陣類如L-陣、SNS陣、S2NS和S*-陣等,推廣到復的情形.稱一個復矩陣A為復L-陣(簡稱L-陣),若Q(A)中任一矩陣均為列線性無關.設A為n階復方陣,稱A為一個ray非異矩陣,若Q(A)中的所有矩陣均可逆;稱A為一個行列式ray唯一矩陣(簡記為DRU矩陣),若A為ray非異且Q(A)中所有矩陣的行列式均有相同ray.由上述定義易見ray非異陣和DRU矩陣都是(實的)SNS矩陣的復推廣.進一步易見,一個復方陣A為DRU陣當且僅當A的行列式展開式中有非零項且所有這些非零項的ray都相同.一個復矩陣是否是L-陣,或ray非異陣,或DRU陣均僅與它的ray模式有關,且在矩陣的行列置換和行列的非零數(shù)乘下保持不變.設A=(apq)是n階復方陣,A的伴隨有向圖D(A)是以V={1,2,…,N}為點集,以E={(i,j)|aij≠0}為弧集的有向圖.若A的某個對角元aii≠0,則D(A)中有從i到i的弧.此時稱在D(A)中的點i上有環(huán)(loop).A的帶ray伴隨有向圖S(A)是把D(A)中的每條弧(i,j)賦以ray(aij)后得到的帶ray有向圖.若一個帶ray有向圖S與某個對角元全負的ray非異矩陣A的帶ray伴隨有向圖S(A)相同,則稱S是一個ray非異的帶ray有向圖.定義1稱復線性方程組Ax=b為ray可解,若它滿足以下兩條件:(1)對任意A～∈Q(A)A～∈Q(A)和b～∈Q(b)?A～x=b～b～∈Q(b)?A～x=b～均有解.(2)對任意A1,A2∈Q(A)和b1,b2∈Q(b)及A1x1=b1,A2x2=b2,均有ray(x1)=ray(x2).當Ax=b為實線性方程組時,Ax=b為ray可解當且僅當它是符號可解.又Ax=b是否為ray可解在方程組的如下諸基本變換下保持不變:(i)增廣矩陣(A,b)的行置換,行變ray,列變ray(“變ray”相當于非零數(shù)乘).(ii)系數(shù)矩陣A的列置換.定義2設Ax=b為ray可解復線性方程組.(1)稱Ax=b為全非零ray可解,若Ax=b的解x無零分量.(2)稱Ax=b為非負ray可解,若Ax=b的解x的分量全為非負實數(shù).(3)稱Ax=b為全正ray可解,若Ax=b的解的分量全為正實數(shù).定義3稱一個方的復線性方程組Ax=b是標準形式,若它滿足:(1)A的所有對角元都是負的(實數(shù)).(2)b的所有的非零元都是負的(實數(shù)).由定義容易驗證當方陣A為滿項秩時,Ax=b總可經(jīng)若干次基本變換(i)和(ii)化為標準形.例如可先經(jīng)A的行置換使A的對角元變?yōu)槿橇?再用增廣矩陣的行變ray把b的所有非零元變?yōu)樨?最后再用系數(shù)矩陣A的列變ray把A的所有對角元變?yōu)樨?設復線性方程組Ax=b有標準形式,b=(b1,…,bn)T,S(A)為A的帶ray伴隨有向圖,記W={i|1≤i≤n,bi<0},則W可視為S(A)的一個點子集.在文獻中,已證明了系數(shù)矩陣為方陣的標準形式的復線性方程組為ray可解的充分必要條件是它的系數(shù)矩陣的帶ray有向圖為W-ray可解;系數(shù)矩陣為方陣的復線性方程組為實非負ray可解的充分必要條件是它的系數(shù)矩陣的帶ray有向圖為W+-ray可解.本文得到了W+-ray可解帶ray有向圖的特征刻畫及強連通的有向圖是W-ray可解帶ray有向圖的基礎有向圖的充要條件等結論.2強連通帶陸有向圖是w+-投資sq的充要條件在文獻中,得到了下面關于具有標準形式的方復線性方程組為ray可解的圖論特征刻畫.定理1設Ax=b為具有標準形式的方復線性方程組.記W={i|1≤i≤n,bi<0}為S(A)的一個點子集,VW={v∈V(S(A))|v到W中某點有路},SW為S(A)中由點子集VW導出的子圖,S′W為S(A)中由VW的補集導出的子圖,則Ax=b為ray可解的充要條件是S(A)和W滿足如下三條件:(1)SW中任一圈的ray均為負.(2)對任一點j∈VW,j到W中所有點的所有路均同ray.(3)S′W是ray非異帶ray有向圖.而當上述諸條件滿足時,Ax=b的解x=(x1,…,xn)T的ray模式為:ray(xj)=εj,其中εj為點j到W中所有點的所有路的公共ray.定義4設S是帶ray有向圖,W是S的一個非空點子集.若S滿足定理1中的條件(1),(2),(3),則稱S是W-ray可解的.注意到在定理1的條件(2)中,約定W中任一點到自身有一條長為零的路,且長為零的路的ray都規(guī)定為正(相當于a0=1).在這樣的約定之下,定理1中的條件(2)實際上蘊含了:W中的任一點w1到任一點w2的任一條路的ray均為正.還注意到,若帶ray有向圖S是強連通的,則Vw=V(S),Sw=S,即S′W是空圖.此時定理1的條件(3)自動成立.因此強連通帶ray有向圖S是W-ray可解的充要條件是它滿足定理1的條件(1)和(2)(其中條件(1)中的Sw可換為S).定義5帶ray有向圖S中的某點x稱為S的一個正端,若S中所有以x為終點的路的ray均為正.由定理1得下面定理:定理2設Ax=b為具有標準形式的方復線性方程組.W,VW及SW定義如定理1,則Ax=b為實非負ray可解當且僅當S(A)和W滿足如下三條件:(1)S(A)中任一圈的ray均為負.(2)W中點都是S(A)中的正端.(3)S′W是ray非異帶ray有向圖.定義6設S是帶ray有向圖,W是其非空點子集.若S滿足定理2中的條件(1),(2),(3),則稱S是W+-ray可解的.顯然,W+-ray可解帶ray有向圖必是W-ray可解的.與上面定義4之后的一段說明類似,若帶ray有向圖S是強連通的,則VW=V(S),SW=S,即S′W是空圖.此時定理2的條件(3)自動成立.因此,強連通帶ray有向圖S是W+-ray可解的充要條件是它滿足定理2的條件(1)和(2)(其中條件(1)中的SW可換為S).定義7將帶ray有向圖S中某點v的所有入弧均乘以一個非零復數(shù)ε,所有出弧均乘以1/ε的變化稱為點v的一個點變ray.性質1S是W-ray可解帶ray有向圖,則對S的任何不在W中的點進行點變ray所得的帶ray有向圖S′仍是W-ray可解的.證明因為對S′W(SW,S′W定義見定理1)中任一點進行點變ray,相當于對其矩陣進行行、列變ray,因此其矩陣的ray定性矩陣類仍為L-陣.因此只需證明SW=S情形即可.設S′是S的對某一不在W中的點v進行點變ray所得到帶ray有向圖,顯然S′中任一點到W中某點有路.對S′中任一圈L,如過點v,則L上出、入v點的弧恰好都有一條.此時易見對點v進行點變ray后不改變?nèi)的ray;如L不過點v,圈L的ray當然也保持不變.因此S′中任一圈的ray為負.設u為S′中任一點,若u≠v,u到W中某點的某條路如果經(jīng)過v點,則v必定不是此路的終點(因v不在W中).故此路必有出、入v點的弧各一條,因此與S的同一路有相同的ray,如果這條路不經(jīng)過v點,則這條路的ray與S中u點到W中的點的所有路的ray相同,因此點u到W中點的所有路均同ray.若u=v,由點變ray的定義,相對于S中的從v點出發(fā)的所有到W中點的所有路,S′中的這些路均有一條且僅有一條弧的ray發(fā)生了變化,即被乘以相同的復數(shù)ε,因此這些路的ray仍然相同.綜上所述S′為W-ray可解的.引理1設W是帶ray有向圖S的一個非空點子集.若S是W-ray可解的,則S可經(jīng)過適當?shù)狞c變ray后變成一個W+-ray可解的帶ray有向圖.證明對S中任一點x∈VW\W,記rx為x到W中所有點的所有路的公共ray.對x實施這樣的點變ray:所有以x為終點的弧的ray均乘以rx,而所有以x為始點的弧的ray均乘以r?1xx-1.對VW\W中的每一點均施以這樣的點變ray.容易驗證,經(jīng)過這樣的一系列點變ray后所得的新帶ray有向圖是一個W+-ray可解的帶ray有向圖.3w、w-現(xiàn)代大學的規(guī)則及相關定理由引理1知經(jīng)過適當?shù)狞c變ray后一個W-ray可解帶ray有向圖可變成W+-ray可解帶ray有向圖,本節(jié)著重研究W+-ray可解帶ray有向圖的一些性質.由上一節(jié)已知對強連通帶ray有向圖S而言,S是W+-ray可解的當且僅當S滿足如下條件:(1)S中所有的圈的ray均為-1.(2)W中點均為S的正端.下面給出強連通W+-ray可解帶ray有向圖的若干必要條件.引理2設S是強連通W+-ray可解帶ray有向圖,則有(1)|W|=1.(2)S+是無圈圖(其中S+是由S中所有正號弧構成的S的不帶ray的生成子圖).證明假設條件(1)不成立,則|W|≥2.設x1,x2為W中任兩點,由S是強連通帶ray有向圖知可取到P,Q分別是S中從x1到x2和x2到x1的路,則P,Q上所有弧的ray均為正.又P+Q必是S中的一條閉途徑,故P+Q必含S中某圈C,即C是S中一正圈,這與S的W+-ray性矛盾.由S中所有的圈的ray均為-1易知(2)成立.由引理2可知,在研究強連通的W+-ray,W-ray可解帶ray有向圖時,總可以假設|W|=1,W={w},并將{w}+-ray可解、{w}-ray可解簡記為w+-ray可解和w-ray可解.定義8設W是有向圖D的非空點子集,(1)如D經(jīng)過適當賦ray后是W-ray可解的,則稱D是W-ray可解基礎有向圖.(2)如D經(jīng)過適當賦ray后是W+-ray可解的,則稱D是W+-ray可解基礎有向圖.由引理1易見:有向圖D是W+-ray可解基礎有向圖,當且僅當D是W-ray可解基礎有向圖.如圖1所示,圖1是由圈C,以C上的兩個點x1,x2為始點,以不在C上的點y為終點的兩條路Q1,Q2,及以y為始點w為終點的路R(可能為空)構成的圖(注:xi是C和Qi唯一的公共點,y是Q1和Q2的唯一公共點,y也是Q1∪Q2和R的唯一公共點).定義這樣的圖為Dw型圖,其中w是圖中的唯一的出度為零的點.下面定理給出了一個強連通有向圖D為w-ray可解基礎有向圖的充要條件.定理3設w是強連通有向圖D中的一個點,則D是w-ray可解基礎有向圖的充要條件是D中不含有Dw型子圖.證明充分性:設D1是由D中所有以w為終點的路的弧集合之并在D中的導出子圖.可以證明D1為無圈圖.假設不成立,則D1中有一個圈C(見圖(2)).設P是從C到w的最短路,且x為P的始點.又設(x,y)為C上以x為始點的弧,則(x,y)是D1上的弧,必在某條以w為終點的路Q上.設z為Q的在C上的最后一個點,則z≠x(否則Q中含圈,與Q為路矛盾),且C∪P∪zQw構成的圖D2包含有Dw型子圖,矛盾.因此D1為無圈圖.現(xiàn)在按以下方式給D賦ray:D1的所有弧為+1,其他弧為-1,因此w時得到的帶ray有向圖S的正端.下面證明帶ray有向圖S中的所有圈的ray均為-1.設C′是S中任一圈,由D1為無圈圖知C′中至少有一條不在D1中的弧.設C′中含有兩條以上不在D1中的弧,由C′為圈可知至少有一條C′上的弧不在D1中且起點不是w,設此弧為h.因D為強連通有向圖,弧h的起點不是w,因此弧h在某條以w為終點的路上,與弧h不在D1中矛盾.因此S中任一圈中最多含有一條不在D1中的弧.因此S中任一圈中恰有一條不在D1中的弧,由上述給D賦ray的方法可知S中任一圈的ray均為-1.因此S是W+-ray可解的,D是w-ray可解基礎有向圖.必要性:若D中含有Dw(如圖1所示)型子圖且D是某一個w-ray可解帶ray有向圖的基礎有向圖.記ray(x1Cx2)=a,ray(x2Cx1)=b,ray(Qi)=ci(i=1,2),rayR=d.則有ab=-1且{ac2d=c1dbc1d=c2d{ac2d=c1dbc1d=c2d.兩者相乘得abc1c2d2=c1c2d2,從而ab=1.這與ab=-1矛盾.4w+-現(xiàn)代有向圖的定義第3節(jié)給出了強連通W+-ray可解基礎有向圖的特征刻畫.本節(jié)研究一般情形(不一定是強連通的)W+-ray可解帶ray有向圖及其基礎有向圖的特征刻畫問題.設W是有向圖D中的非空點子集,VW={v∈V(S(A))|v到W中某點有路},DW為點集合VW在D中的導出子圖,S是以D為基礎有向圖的帶ray有向圖,SW是點集合VW在S中的導出子圖,不難看出S是W+-ray可解帶ray有向圖的充要條件是SW是W+-ray可解的,且所有不包含在SW中的S的強連通分支是ray非異帶ray有向圖.由此可對帶ray有向圖S作以下假設:A1S=SW.相當于條件:對S中的任一點v,存在一條從v到W中某點的路.由引理2可知,如S是W+-ray可解帶ray有向圖,則S的任一強連通分支最多包含一個W中的點.由此可以對帶ray有向圖S的基礎有向圖D作假設.A2D的每個強連通分支中至多包含1個W中的點.根據(jù)假設A2,進一步引入下面記號并作為假設:A3設D1,…,Dr是D的所有的含有一個W中點的強連通分支,wi∈W∩V(Di)(i=1,…,r),Dr+1,…,Dk是D的所有的不含有W中點的強連通分支,則W={w1,…,wr}.定義9稱有向圖D中兩端屬于D的不同強連通分支的弧為D的一條“支間弧”.下面給出本節(jié)的重要定理——W+-ray可解帶ray有向圖的特征刻畫.定理4設W是帶ray有向圖S的一個非空點子集,滿足假設條件A1～A3,則S是W+-ray可解(即每個圈的ray均為負且W中點均為正端)的充要條件是S滿足如下兩條件:(1)S中所有支間弧的ray均為正.(2)S中任一強分支Si中都存在(唯一的)一點vi滿足如下三條件:(a)vi=wi對i=1,…,r.(b)每個Si都是(強連通的)v+i-ray可解.(c)S中每一條離開強分支Si的弧都以vi為始點.證明必要性:(1)設e=(x,y)為S的任意一條支間弧.由條件A1知S中存在y到W中某點的路Q.此路Q必定不經(jīng)過點x,否則x與y將屬于同一個強連通分支,這與(x,y)是支間弧矛盾.于是(x,y)+Q是x到W中某點的一條路.由W中點全是S正端(此由S為W+-ray可解可知)可知此路上的所有弧均為正弧,從而弧e的ray為正.(2)對i=1,…,r,取vi=wi;若i=r+1,…,k,則Si必有某一條出弧(因Si中點到W中點都有路而W中點都在Si之