《图论及其应用》课程教学课件（PPT讲稿）第一章 图的基本概念 1-5 邻接谱与图的邻接代数

第一章图的基本概念 本次课主要内容 邻接谱与图的邻接代数 (一)、邻接谱 (二)、 图的邻接代数 (三)、图空间简介

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 1 第一章 图的基本概念 本次课主要内容 邻接谱与图的邻接代数 (一)、邻接谱 (二)、图的邻接代数 (三)、图空间简介

(一)、邻接谱 1、图的特征多项式 定义1：图的邻接矩阵A(G)的特征多项式： fG,2)=E-A=2"+a2m+a,2m-2++an+a 称为图G的特征多项式。 例1、设单图G的特征多项式为： fG,=E-A="+a,2+a,22++a,+a, 求证：(1)a1=0;(2)-a2=m(G)； (3)-a3是G中含有不同的K3子图的个数2倍

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 2 1 2 1 2 1 ( , ) n n n n n f G E A a a a a       − − = − = + + + + + − (一)、邻接谱 1、图的特征多项式 定义1：图的邻接矩阵A(G)的特征多项式： 称为图G的特征多项式。 例1、设单图G的特征多项式为： 1 2 1 2 1 ( , ) n n n n n f G E A a a a a       − − = − = + + + + + − 求证: (1) a1=0 ; (2) –a2= m (G) ; (3) –a3是G中含有不同的K3子图的个数2倍

证明：由矩阵理论：对每个1in,(-1)ia:是A(G)的 所有阶主子式之和。 (1)由于A(G)的主对角元全为零，所以所有1阶主子 式全为零，即：a1=0; (2)对于单图G,A(G)中非零的2阶主子式必为如下形 式： 这样的一个2阶主子式对应G中的一条边，反之亦然， 所以，有： (-1)2a2=- m(G) a 2=m(G)

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 3 证明：由矩阵理论：对每个1≦i≦n,(-1)iai是A(G)的 所有i阶主子式之和。 (1) 由于A(G)的主对角元全为零，所以所有1阶主子 式全为零，即：a1=0 ; 0 1 1 1 0 = − 这样的一个2阶主子式对应G中的一条边，反之亦然， 所以，有： (2) 对于单图G,A(G)中非零的2阶主子式必为如下形 式： 2 2 ( 1) ( ) − = − a m G 2 − = a m G( )

(③)对于单图G,A(G)中非零的3阶主子式必为如下形 式： 少 这样的一个3阶主子式对应G中的一个K3,反之亦然 设G中有S个K3,则： (-1)3a3=2S 事实上，有如下一般性定理：（见李蔚萱，《图论》，湖 南科学技术出版社，1980年4月)

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 4 0 1 1 1 0 1 2 1 1 0 = 这样的一个3阶主子式对应G中的一个K3，反之亦然. 设G中有S个K3 , 则： (3) 对于单图G,A(G)中非零的3阶主子式必为如下形 式： 3 3 ( 1) 2 − = a S 事实上，有如下一般性定理：(见李蔚萱，《图论》，湖 南科学技术出版社，1980年4月)

定理1：图G的特征多项式的系数： a,=(-1)y>det H.s(G,H),i=1,2,.,n 右边对G的所有i阶点导出子图H求和。 其中，s(G,表示G的同构于H的点导出子图的数目 2、图的邻接谱 定义2：图的邻接矩阵A(G)的特征多项式的特征值 及其重数，称为G的邻接谱。 例2、求出Kn的谱。 解：K的邻接矩阵为：

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 5 定理1：图G的特征多项式的系数： ( 1) det ( , ), 1,2, , i i H a H s G H i n = − =  其中，s (G, H)表示G的同构于H的点导出子图的数目。 右边对 G的所有i 阶点导出子图H求和。 2、图的邻接谱 定义2：图的邻接矩阵A(G)的特征多项式的特征值 及其重数，称为G的邻接谱。 例2、求出K n的谱。 解：K n的邻接矩阵为：

90 A(K)= 于是： -1-1.-1-1 -1-1. -1-1 E-A(K)= -1-1 -1 -12 -n+1-1-1-1-1 -n+1元-1 2-n+1-1-1-1-1

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 6 0 1 1 1 1 1 0 1 1 1 ( ) 1 1 1 1 1 0 A Kn     =         于是： 1 1 1 1 1 1 1 1 ( ) 11111 E A Kn     − − − − − − − − − = −−−−− 1 1 1 1 1 1 1 1 1 11111 n n n      − + − − − − − + − − − = − + − − − −

1 -1-1 -1 -1 -1 =(-n+1) =(2-n+1)(2+1) -1-1-1-1 所以： n-1 Spec(K,)= n-1 例3，若两个非同构的图具有相同的谱，则称它们是同 谱图。求证：下面两图是同谱图。 NA G H

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 7 ( ) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 n    − − − − − − − = − + −−−− ( ) 1 1 ( 1)n   n − = − + + 所以： 1 1 ( ) 1 1 n n Spec K n   − − =     − 例3，若两个非同构的图具有相同的谱，则称它们是同 谱图。求证：下面两图是同谱图。 G H

证明：G与H显然不同构。 通过直接计算： fG,2)=f(H,2入)=2-724-423+722+4元-1 所以G与H是同谱图。 例4，设单图A(G)的谱为： Spec(G)= m m 则： ∑m,2=2m(G) i= 证明：由矩阵理论： m,2=2a,2

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 8 证明：G与H显然不同构。 通过直接计算： 6 4 3 2 f G f H ( , ) ( , ) 7 4 7 4 1        = = − − + + − 所以G与H是同谱图。 例4，设单图A(G)的谱为： 1 2 1 2 ( ) s s Spec G m m m      =     则： 2 1 2 ( ) S i i i m m G  =  = 证明：由矩阵理论： 2 (2) 1 1 S n i i ii i i m a  = =  =

am2表示点v的度数，由握手定理： 2m22-2a,-2a)=2mG 即： 空m=2G 例5，设入是单图G=(m,m)的任意特征值，则： ≤、 2m(n-1) n 证明：不失一般性，设=入1,2，.，n是G的全体 特征值。 G是单图，有： 2=-(23+入3++)(1)

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 9 a ii (2)表示点vi的度数，由握手定理： 即： 2 (2) 1 1 1 ( ) 2 ( ) S n n i i ii i i i i m a d v m G  = = =    = = = 2 1 2 ( ) S i i i m m G  =  = 例5，设λ是单图G = (n, m)的任意特征值，则： 2 ( 1) m n n  −  证明：不失一般性，设λ=λ1，λ2，.,λn是G的全体 特征值。 G是单图，有： 1 2 3 ( ) (1)     = − + + + n

又由例4，有： 22=2m-（22+2++2）.(2) 对向量(1,1，1)与（入2,3,4，.，入）用柯西不等式 得： 元1+元1+.+元，]≤√22+元2+.+，√n-1 所以，有： (2++.+)2≤(n-1)(22+入2+.+入2 由(1)与(2)得： ≤ 2m(n-1) 10

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 10 又由例4，有： 对向量(1,1,.,1)与(λ2,λ3,λ4,.,λn)用柯西不等式 得： 2 2 2       2 3 2 3 1 1 1 1 + + +  + + + − n n n ( ) 2 2 2 2 1 2 3 2 (2)     = − + + + m n 所以，有： ( ) ( )( ) 2 2 2 2       2 3 2 3 + + +  − + + + n n n 1 由(1)与(2)得： 2 ( 1) m n n  − 