第一章图的基本概念 本次课主要内容 邻接谱与图的邻接代数 (一)、邻接谱 (二)、 图的邻接代数 (三)、图空间简介
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的邻接矩阵为：