HAMILTON图的特征矩阵  

THE CHARACTERISTIC MATRIX OF HAMILTONIAN GRAPH

作　　者：陈东灵[1] 闫春钢[1] 姚育志 

机构地区：[1]山东矿业学院数学软件系,山东省泰安市271000

出　　处：《曲阜师范大学学报（自然科学版）》1992年第4期36-38,共3页Journal of Qufu Normal University(Natural Science)

基　　金：山东省自然科学基金

摘　　要：讨论了Hamilton图G和它的邻接矩阵A之间的关系,得到如下结果定理1 图G是H—图当且仅当A=B+Q,这里B≥0且B≠0,Q=P CP,C是由互换单位矩阵中的第1行和第n行所得到的初等阵,P是置换阵,P是P的转置矩阵。定理2 图G是H—图当且仅当A的谱半径ρ(A)是A的单根,且存在正特征向量ξ,使得Aξ=ρ(A)ξ>η,这里η是由适当调整ξ的分量而得到的向量,满足:当ξ的第i个分量调为η的第j个分量时,A的(i,j)元a_(ij)=1。In this paper, we discuss the relation between Hamiltonian graph and its adjacency matrix. The following results are proved: Theorem 1 A graph G is a Hamiltonian graph if and only if A=B+Q, where A denotes adjacency matrix of the graph G,B≥0 and B≠0,Q=P CP. C denotes the elementary matrix, which is obtained by exchanging the l-line (row) and the n-line(row) of a unit matrix. P denotes the permutation matrix. p^T denotes the transposed matrix of P. Theorem 2 A graph G is a Hamiltonian graph if and only if the spectral radius ρ(A) of the adjacency matrix A of the graph G is a single root of A. And there is a positive characteristic vector so that Aξ=ρ(A)ξ>η, where η denotes a positive vector, which is obtained by adjusting some coordinates of the vector ξ appropriately. It is satisfied as following: the (i,j)-element of A is equal to 1 as the i-coordinate of ξ adjusting to the j-coordinate of η.

关 键 词：图 HAMILTON图 邻接矩阵 谱半径 特征向量 

分 类 号：O157.5[理学—数学]