譚尚旺

(中國石油大學(xué)應(yīng)用數(shù)學(xué)系,山東東營 257061)

矩陣特征多項式的圖論計算公式

譚尚旺

(中國石油大學(xué)應(yīng)用數(shù)學(xué)系,山東東營 257061)

給出了賦權(quán)有向圖鄰接矩陣特征多項式的圖論計算公式,從而得到了一般矩陣特征多項式的圖論計算方法,并且研究了賦權(quán)有向圖鄰接矩陣特征多項式和譜半徑的一些性質(zhì).

矩陣;賦權(quán)有向圖;線性子圖;特征多項式

1 引言

文中沒有定義的概念和記號見文[1].令A(yù)=(aij)是數(shù)域F上的n階矩陣,則它的伴隨有向圖定義為賦權(quán)有向圖DA=(V,E),V={v1,v2,…,vn},其中當(dāng)且僅當(dāng)aij/=0時,vi到vj有一條權(quán)值為aij的有向邊.顯然,A是賦權(quán)有向圖DA的鄰接矩陣.因此,一般矩陣特征多項式的計算問題與一般賦權(quán)有向圖鄰接矩陣特征多項式的計算問題是等價的.

設(shè)D是頂點集為V(D)且邊集為E(D)的賦權(quán)有向圖,wD(e)表示有向邊e在D中的權(quán). 設(shè)H是D的一個子圖,如果對每個邊e∈E(H),都有wH(e)=wD(e),則稱H是D的一個賦權(quán)有向子圖.令H是D的賦權(quán)有向子圖.如果V(D)/=V(H)或E(D)/=E(H),則稱H是D的賦權(quán)有向真子圖.如果V(D)=V(H),則稱H是D的生成賦權(quán)有向子圖.D的一個i階賦權(quán)有向子圖H稱為D的一個i階線性子圖,如果H的每個點的入度和出度都是1.顯然,D的一個線性子圖是由一些頂點不交有向圈的并構(gòu)成的,其中這里把環(huán)看成長度為1的有向圈.對于D的賦權(quán)有向子圖H,如果E(H)/=?,則定義它的權(quán)wD(H)為wD(H)=∏e∈E(H)wD(e).

圖譜研究是圖論的熱點之一,如文[2]研究了具有特殊譜的圖的結(jié)構(gòu),文[3]研究了特殊圖的譜特征.如何快速計算矩陣的特征多項式對研究和計算矩陣的譜是重要的.另一方面,網(wǎng)絡(luò)和電路設(shè)計中的圖一般都是賦權(quán)有向圖并且賦權(quán)有向圖的譜時常用來解決具體問題.因此,研究矩陣或賦權(quán)有向圖鄰接矩陣特征多項式的計算問題是有意義的.1974年,文[4]給出了一般無向圖鄰接矩陣特征多項式的圖論計算公式.2000年,文[5]給出了一般有向圖鄰接矩陣特征多項式的計算公式.本文首先研究了一般矩陣或賦權(quán)有向圖鄰接矩陣特征多項式的圖論計算方法,然后研究了非負矩陣或賦權(quán)有向圖特征多項式和譜半徑的一些性質(zhì).

2 賦權(quán)有向圖特征多項式的圖論計算方法

本節(jié)研究賦權(quán)有向圖特征多項式的圖論計算方法.記n階賦權(quán)有向圖D的鄰接矩陣A(D)的特征多項式為φ(D,λ)或φ(D),令

對D的賦權(quán)有向子圖H,約定H?V(H)=?時,φ(H?V(H),λ)=1.

引理2.1[6]令Li是D的i階線性子圖的全體,ε(H)是H中的圈數(shù),則

其中當(dāng)Li=?時,約定和號取值為0.

定理2.1設(shè)v是n階賦權(quán)有向圖D=(V,E)的一個頂點,C(D,v)表示D中包含頂點v的所有有向圈的集合,則

證明記D的一個賦權(quán)有向子圖H的階為o(H).引進記號

對i=0,1,…,n,下面只要證明φ(D,λ)與g(λ)?h(λ)的λn?i的系數(shù)相等即可.顯然,λn的系數(shù)相等且都為1.因此,下面假設(shè)i≥1.取定D的一個i階線性子圖Hi,以Hif(λ)表示Hi對多項式f(λ)的λn?i系數(shù)的貢獻.對常數(shù)a,特別約定Hi(af(λ))=aHif(λ).則對任意的常數(shù)a,b和多項式p(λ),q(λ),都有

由引理2.1知Hiφ(D,λ)=(?1)ε(Hi)wD(Hi).下面分兩種情形討論Hi對g(λ)?h(λ)的λn?i系數(shù)的貢獻.

情形1假設(shè)v/∈V(Hi).

顯然,g(λ)的λn?i系數(shù)取決于φ(D?v,λ)的λn?i?1系數(shù).由于o(D?v)=n?1,于是對φ(D?v,λ)的λn?i?1系數(shù)有貢獻的D?v的線性子圖的階是i.因為v/∈V(Hi),所以Hi也是D?v的一個i階線性子圖.于是由引理2.1知

任取Z∈C(D,v).由于o(D?V(Z))=n?o(Z),于是對φ(D?V(Z),λ)的λn?i系數(shù)有貢獻的D?V(Z)的線性子圖的階為i?o(Z).既然Z不是Hi的分支,于是o(Hi?V(Z))≥i?o(Z)+1,從而Hi?V(Z)不是D?V(Z)的i?o(Z)階線性子圖,進而Hi?V(Z) 對φ(D?V(Z),λ)的λn?i系數(shù)貢獻為0,即Hi(φ(D?V(Z),λ))=0.因此,有

情形2假設(shè)v∈V(Hi).

顯然,o(Hi?v)=i?1并且o(D?v)=n?1.因此,Hi?v不是D?v的i階線性子圖,從而Hi?v對φ(D?v,λ)的λn?i?1的系數(shù)貢獻為0,即Hig(λ)=0.

由線性子圖的定義,C(D,v)中只有一個圈在Hi中,記該圈為K,則Hi?V(K)是D?V(K)的i?o(K)階線性子圖.既然o(D?V(K))=n?o(K),于是Hi?V(Z)對φ(D?V(K),λ) 的λn?i系數(shù)貢獻為

對每個Z∈C(D,v){K},Z都不是Hi的分支,所以o(Hi?V(Z))≥i?o(Z)+1,從而Hi不是D?V(Z)的i?o(Z)階線性子圖,于是Hiφ(D?V(Z),λ)=0.因此,有

根據(jù)上面兩種情形的討論,我們完成了定理的證明.

推論2.1設(shè)u和v分別是無公共頂點賦權(quán)有向圖D1和D2的頂點,D表示把u和v粘成一個頂點后得到的賦權(quán)有向圖,則

對i=0,1,2,…,n,下面只需證明φ(D,λ)和φ(D?e,λ)?h(λ)的λn?i的系數(shù)相等即可.顯然,λn的系數(shù)相等且都為1.因此,下面假設(shè)i≥1.取定D的一個i階線性子圖Hi,下面需要證明Hi對φ(D,λ)和φ(D?e,λ)?h(λ)的λn?i的系數(shù)貢獻相同.仍然沿用定理2.1中的記號,由引理2.1知Hiφ(D,λ)=(?1)ε(Hi)wD(Hi).下面分兩種情形討論Hi對φ(D?e,λ)?h(λ) 的λn?i系數(shù)的貢獻.

情形1假設(shè)e/∈E(Hi).

顯然,Hi?e=Hi是n階賦權(quán)有向圖D?e的i階線性子圖.由引理2.1有

任取Z∈C(D,e).由于o(D?V(Z))=n?o(Z),于是對φ(D?V(Z),λ)的λn?i系數(shù)有貢獻的D?V(Z)的線性子圖的階為i?o(Z).既然e/∈E(Hi),于是Z不是Hi的分支,從而o(Hi?V(Z))≥i?o(Z)+1.這表明Hi?V(Z)不是D?V(Z)的i?o(Z)階線性子圖.因此,Hi?V(Z)對φ(D?V(Z),λ)的λn?i系數(shù)貢獻為0,即Hi(φ(D?V(Z),λ))=0.于是有

情形2假設(shè)e∈E(Hi).

顯然,Hi?e是n階有向圖D?e的i階有向子圖,但不是D?e的i階線性子圖.因此, Hiφ(D?e,λ)=0.由線性子圖的定義,C(D,e)中只有一個圈在Hi中,記該圈為K.類似定理2.1情形2的證明得

根據(jù)上面兩種情形的討論,我們完成了定理的證明.

推論2.3設(shè)vu是簡單無向賦權(quán)圖G=(V,E)的一個邊,C(G,vu)表示G中包含vu的所有圈的集合,則

利用上面的結(jié)論,能夠簡單直觀的計算許多矩陣的特征多項式.注意到簡單無向圖可以看成是邊上的權(quán)值為1的賦權(quán)圖,于是由推論2.2和推論2.3,能立即得到計算簡單無向圖鄰接矩陣特征多項式的常用公式[4].

3 賦權(quán)有向圖特征多項式的一些性質(zhì)

本節(jié)研究賦權(quán)有向圖特征多項式的性質(zhì).權(quán)值都是正數(shù)的賦權(quán)有向圖稱為正賦權(quán)有向圖.由非負矩陣?yán)碚撝x權(quán)有向圖的鄰接矩陣的譜半徑是一個最大特征值.記賦權(quán)有向圖D的鄰接矩陣的譜半徑為ρ(D).

引理3.1[4]設(shè)H和D都是正賦權(quán)有向圖且D強連通,如果A(D)≥A(H)且A(D)/= A(H),或H是G的一個賦權(quán)有向真子圖,則ρ(H)＜ρ(D).

引理3.2設(shè)e是正賦權(quán)強連通有向圖D的一個邊,則當(dāng)λ≥ρ(D)時,都有φ(D,λ)＜φ(D?e,λ).

證明因為D是強連通的,所以C(D,e)/=?.任取Z∈C(D,e).一方面,wD(Z)＞0.另一方面,由引理3.1知ρ(D)＞ρ(D?V(Z)),這表明λ≥ρ(D)時,φ(D?V(Z),λ)＞0.因此, 當(dāng)λ≥ρ(D)時,由定理2.2得

于是完成了引理的證明.

定理3.1如果H是正賦權(quán)強連通有向圖D的一個真生成賦權(quán)有向子圖,則當(dāng)λ≥ρ(D) 時,有φ(D,λ)＜φ(H,λ).

[1]邦迪J A,默蒂U SR.圖論及其應(yīng)用[M].吳望名,李念祖,譯.北京:科學(xué)出版社,1984.

[3]亓健,譚尚旺,同小軍.完全等部二分圖kn,n的迭線圖Lm(kn,n)的譜特征[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué),2000, 16(2):74-78.

[4]Cvetkovi′c D M,Doob M,Sachs H.Spectra of G raphs[M].New York:Academ ic Press,1980.

[5]譚尚旺,亓健,郭紀(jì)明.有向圖和弱正則有向圖補圖的特征多項式的計算方法[J].數(shù)學(xué)雜志,2000,20(4):421-426.

[6]陳惠開.應(yīng)用圖論[M].范定松,張玲玲,譯.北京:人民郵電出版社,1988.

(Department of App lied Mathematics,China University of Petroleum,Dongying 257061,China)

We obtain formulas computing the characteristic polynomial of ad jacent matrix of a weighted digraph in graph theory,thereby the methods computing the characteristic polynomial of a matrix in graph theory are derived and some properties of characteristic polynomial and spectral radius of adjacentmatrix on a weighted digraph are investigated.

matrix,weighted digraph,linear subgraph,characteristic polynomial 2000M SC:05C50

On form u las calcu lating the characteristic polynomial ofm atrices in graph theory TAN Shang-wang

O157.5

A

1008-5513(2009)02-0209-08

2007-11-10.

國家自然科學(xué)基金資助項目(10871204).

譚尚旺(1965-),教授,研究方向：圖論.