定向图的谱半径的一个上界_孙天川

第28卷　第1期　　2006年2月　　湖州师范学院学报V o l. 28　No. 1　　　　　　　　　　　Jo ur nal of Huzhou T eachers College Feb. , 2006

定向图的谱半径的一个上界孙天川

(湖州师范学院理学院, 浙江湖州313000)

摘*要:利用定向图的邻接矩阵的特性, 得到了定向图的邻接谱的谱半径的一个可达上界. 设D 为n 阶的定向图,

n -1n -1. 当n 为奇数时, 上式取得等号当且仅当D 为出度正则(入度正则) ; 当n 为22则其邻接谱的谱半径ρ(D )≤

偶数时, 不等式严格成立.

关键词:有向图; 定向图; 谱; 谱半径

中图分类号:O 157. 5

MR (2000):05C20文献标识码:A 文章编号:10091734(2006) 01005004

0引言

设D =D (V , E ) 为n 阶有向图(V 为顶点集, E 为弧集), 其邻接矩阵A =A (D ) =(a ij ) n ×n 的所有特征根:λ1, λ2, …, λn , 被称为有向图D 的邻接谱, 记作Spec (D ) ={λ1, λ2, …, λn }(重集) . γ1, …,γn 表示矩阵A 的行和. 称1max {|λi |}为D 的谱半径, 记作ρ, ρ(D ) 或ρ(A ) . ≤i ≤n

用d D (v ) (或d v ) ) 和d D (v ) (或d (v ) ) 分别表示D 中顶点v 的入度和出度, δ(D ), δ(D ), Δ(D ) +-+-+和Δ(D ) 分别表示D 的最小入、出度和最大入、出度, 有时简写为δ, δ, Δ和Δ.

对应于每个有向图D , 可以在相同的顶点集上作一个无向图G D , 使得对应于D 的每条弧, G D 有一条与该弧有相同的端点的边与之对应. 反之, 给定任意图G , 对于它的每条边, 给其端点指定一个顺序, 从而确定一条弧, 由此得到一个有向图, 这样的有向图称为G 的一个定向图, 记作D. 在一般的情况下D 是不唯一的.

其它有关术语可参考文献[1]和[2].

图的谱理论是图论研究的重要领域之一, 也是一个非常活跃的研究领域, 它在量子学、物理学、计算机科学、通讯网络及信息科学中均有广泛的应用. 本文对定向图的邻接谱的谱半径进行了研究, 得到了谱半径的一个上界:ρ(D ) ≤, 并且当n 为奇数时, 等号成立当且仅当D 为出度正则(或入度正则); 22

当n 为偶数时, 等号不成立, 其可达上界可能为. 2--++-+-

1定向图的谱半径的上界

引理1[3]　(Perron Frobenius 定理) 设A 为n (>1) 阶不可约非负方阵, ρ(A ) 为A 的模最大的特征值, 则

(1) ρ(A ) 是A 的正特征值;

(2) ρ(A ) 作为A 的n 2个元素的函数是严格递增的, 即若有方阵B ≠A , B -A ≥0, 则ρ(B ) >ρ(A );

(3) ρ(A ) 是A 的单根;

*收稿日期:20050531-), 男, , , 图的控制参数, .

第1期　　　　　　　　　　　　　　　孙天川:定向图的谱半径的一个上界51

(4) A 有正特征向量z 与ρ(A ) 相对应, 即z >0, Az =ρ(A ) z , 而且A 的任一非负特征向量一定是z 的正数倍.

定理1设D 是n (>1) 阶强连通定向图, 则

ρ(D ) ≤, 2(1)

且当n 为奇数时, (1) 式等号成立当且仅当D 为出度正则(入度正则); 当n 为偶数时, (1) 式为严格不2

等式.

证明　设A =(a ij ) n ×n 为D 的邻接矩阵, 由于D 为强连通图, 所以A 为非负不可约方阵, 且a ij =0, a ji +a ij =0, 1, i ≠j , 1≤i , j ≤n. 根据引理1, 存在对应谱半径ρ的正特征向量z =(z 1, z 2, …,z n ) (z =

1), 使得Az =ρz. 从而有

ρ=z t ρz =z t Az =[∑(a ij +a ji ) z i z j ]≤21≤i , j ≤n

2(因为a ii =0, a ji +a ij =0, 1, i ≠j ) =(z i z j -z j ) 21≤∑i , j ≤n

22i j (z i z j -1) ≤∑) -1]=. ∑21≤i , j ≤n 21≤i , j ≤n 22

n n

ij t 上式等号成立当且仅当z i =z j , 1≤i ≤j ≤n , 即z 1=…=z n >0. 因此ρZ i =i =1∑a z j , ρ=i =1∑a ij , 1≤

i ≤n , 即A 的所有行和均等于ρ, 所以A 的所有行和均相等且为, 即D 为出度正则(利用矩阵列22

可证入度正则) . 又矩阵A 的行和为整数, 所以此时n 为奇数.

反之, D 为出度正则(入度正则) 时, 据引理1(4), 可推得ρ=. 22

当n 为偶数时, 利用反证法可证明ρ

证毕.

例1　

强连通定向图的谱半径及估计上界.

　　　　　　　　　(a )　　　　　　　　　　　(b )　　　　　　　　　　　　(c )

图1　三个强连通定向图

图1(a ) 为一7阶强连通非出度正则(入度正则) 定向图, 其邻接矩阵

.

52湖州师范学院学报　　　　　　　　　　　　　　　　　　第28卷经计算, 其最大特征根即图的谱半径ρ=0. 此时定理1给定上界为

给定上界. =3, 0

图1(b ) 为一5阶强连通出度正则(入度正则) 定向图, 其邻接矩阵

0　1　1　0　0

0　0　1　1　0

A =0　0　0　1　1.

1　0　0　0　1

1　1　0　0　经计算, 其最大特征根ρ(D ) 为2, 此时定理1给定上界为2, 此时谱半径等于给定上界. 2

图1(c ) 为一8阶强连通定向图, 其邻接矩阵

0　1　0　0　0　0　0　0

0　0　1　0　0　0　0　0

0　0　0　1　0　0　0　0

A =0　0　0　0　1　0　0　1

0　0　0　0　0　1　0　0

0　1　0　0　0　0　1　0

1　0　1　0　0　0　0　1

1　0　0　0　0　0　0　经计算, 其最大特征根ρ(D ) 为0, 此时定理1给定上界为3, 显然有0

上界.

引理2　设D 为n 阶有向图, 其谱为Spec (D ) =(λ1, λ2, …,λn ) . D 为D 添加一个出度为零的顶点所

*形成的有向图, 则Spec (D *) =(λ1, λ2, …, λn , 0), 即D 只比D 多一个零特征根. *.

证明　设有向图D 的顶点集为V (D ) ={v 1, v 2, …,v n }, 则D *的顶点集可设为V (D *) ={v 1, v 2, …,v n ,

*v n +1}, 且d +D (v n +1) =0. 从而A (D *) =A (D ) β

θ0, 其中β为n 维列向量, θ为n 维行向量且为零向量.

显然有det (λI n +1-A (D *) ) =λdet (λI N -A (D ) ), 其中det (*) 表示矩阵*的行列式, I n 表示n 阶单位阵. 这说明A (D ) 只比A (D ) 多了一个零特征根, 也就是D 比D 多一个零特征根.

证毕.

推论1　设D 是n (>1) 阶有向图, v ∈V (D ) 且d D (v ) =0, 则D -v 与D 有相同的非零特征值. 由引理3直接可得.

引理3设D 为n 阶有向图, 其谱为Spec (D ) ={λ1, λ2, …,λn }. D 为D 添加一个入度为零的顶点所

***+**形成的有向图, 则Spec (D *) ={λ1, λ2, …, λn , 0}, 即D *只比D 多一个零特征根. 证明　设有向图D 的顶点集为V (D ) ={v 1, v 2, …,v n }, 则D 的顶点集可设为V (D ) ={v 1, v 2, …,

v n , v n +1}, 且d D *(v n +1) =0. 从而A (D ) =-*A (D ) α0, 其中θ为n 维列向量且为零向量, α为n 维行向量.

同样有det (λI n +1-A (D *)) =λdet (λI n -A (D ) ) . 这说明A (D *) 只比A (D ) 多一个零特征根, 也就是D *比D 多一个零特征根.

　　证毕.

推论2设D 是n (>1) 阶有向图, v ∈V (D ) 且d -D (v ) =0, 则D -v 与D 有相同的非零特征值. 由引理5直接可得.

,

第1期　　　　　　　　　　　　　　　孙天川:定向图的谱半径的一个上界53

ρ(D ) ≤. 2(2)

且当n 为奇数时, (2) 式等号成立当且仅当D 为出度正则(入度正则); 当n 为偶数时, (2) 式为严格不2

等式.

证明由于定向图要么为强连通定向图, 要么为强连通定向图添加若干个入度或出度为零的顶点所形成的图, 所以应用定理1和推论1、推论2可得本定理结论.

　　证毕.

参考文献:

[1]Bondy J A , M urty U S R. 图论及其应用[M ]. 北京:科学出版社, 1984. 181～189.

[2]B éla Bollob ás. 现代图论(影印版)[M ]. 北京:科学出版社, 2001. 1～8.

[3]李乔. 矩阵论八讲[M ]. 上海:上海科学技术出版社, 1988. 71～72.

An Upper Bound of the Spectral Radius on the Oriented Graphs

SUN Tian chuan

(Faculty of Science , H uzhou T eacher s Co lleg e , Huzhou 313000, China )

A bstract :The spectral theory of g raphs is an important aspect of algebraic g raph theory field. In this pa -per , the author obtains an upper bound o f the spectral radius of oriented g raphs by letting D be an orien -

ted g raph w ith n vertices. Thus he concludes the spectral radius ρ(D , and the equality holds if 2

and only if that D is a reg ula r oriented g raph o n o utdeg rees (indeg rees ) as n is odd , the inequality is strict otherw ise.

Key words :dig raph ; o riented g raph ; spectrum ; spectral radius

MR (2000):05C20