mn Spec K m ,n = 1 mn mn2 1 0
有
向
图
定义：同谱图 定义：谱半径（G的最大特征值）
有
向
图
关于特征多项式的相关结论。。。
定理3：设简单图G的特征多项式为
fG c1
n n1
c2
n2
L cn
则 (1) c1=0; (2) -c2=m； (3) -c3为G中三角形的个数的两倍；
有
向
图
定义：图G的谱 Spec G
2 L 1 Spec G= m 1 m 2 L s m s
有
向
图
图的特征值与谱 定义：邻接矩阵 定义：邻接矩阵的特征值与特征多项式
有
向
图
关于特征值的相关结论。。。
2m n 1 n
有
向

图
定理2：G为n阶连通图 （ 1）
G
（2） △为G的特征值当且仅当G为正则图； 若△为G的特征值，则m（ △ ）=1 （3） 若- △为G的特征值，则G为正则偶图； （4） 若G为偶图且λ为G的特征值，则- λ也 为G的特征值且重数一样。
1 2 L s
m 1 m 2 L m s n
有
向
图
特殊图形的谱
1 0 1 Spec C3 = 1 1 1 2 0 2 Spec C4 = 1 1 1
Spec Cn =?
有
向
图
n 1 1 Spec Kn = 1 n 1