图谱论导引.pptVIP

图谱论导引 代数图论基础 许 昱 2011年8月 作为代数图论的基础，图的谱理论在近几十年有了长足的发展。它在物理，化学，生物，计算机科学，运筹学，管理科学以及社会科学方面都有广泛的应用。图的谱理论是发展中的学科，尚有大量的理论和实际问题没有解决 。 代数图论就是用代数的方法研究图论问题。因方法上并不存在一一对应关系，有些问题是不存在充要条件的，所以必须寻求有效的方法加以解决。采用代数的方法，如特征多项式与特征根都是代数中的不变量,把这些引入到图论的研究之中后，就导出了很多新的结果，这就是本学科的基础。 The spectrum of a graph Definition1.1 The adjacency matrix of G is the n×n matrix A = A(G), over the complex field, whose entries are given by A称为图G的邻接矩阵 Definition1.2 The spectrum of a graph G is the set of numbers which are eigenvalues of A(G) , together with their multiplicities as eigenvalues of A(G) . If the distinct eigenvalues of A(G) are λ1≥2≥...≥λs, and their multiplicities are m(λ1), m(λ2), ..., m(λs), then we shall write SpecG = 定理1：对于G的特征多项式 有：(1) c1=0 ; (2) –c2 is the number of edges of G; (3) – c3 is twice the number of triangles in G. 定理2 ：图G中k步封闭游走数为 sk ,则有：k阶矩 且有:（1）图G中点的个数等于特征根的个数（含重数）； （2）G中边数等于 （3）G中点的平均度数为 （4）G中三角形个数为 （5）含给定点的三角形的个数的平均数为 命题1. d+1≤ G中不同特征根个数≤n. 其中d为图的直径. 定理3. G连通 (A+I)^(n-1)有非零元. G的指数λ1为单根且特征向量为正. 定理4. G为λ1度正则 定理5. G为二部图 谱关于原点对称. 定理6.连通图G是二部图 λ1=－λn . 几个特殊图举例 1. n点 零线图G, 特征多项式: 2.Kn 3.k个K2的并: 4.上图的补 5.完全二部图 特别地, 6.回路 Cn 对应邻接阵为循环阵 当n为奇数时, Spec 当n为偶数时, Spec 7.道路 Pn: 8.多部图. 其中S0=1,Si是第i个关于n1,n2,...nk的基本对称函数. 9. Pn+Pn: λ的取值为： Cn+Pn: λ对应于: Cn+Cn: λ对应于: 10.k维有限格点图. 重数为: 11.Peterson图(K5的线图的补图)O3 O3的强正则参数为(10,3,0,1) 12. SpecHs= 特别地, SpecH3= 13. The Mobius ladders 14.轮图Wk 邻接谱 Laplacian spectrum: 15.小世界图 The small world graph has been proposed by Watts and Strogatz (1998) and is further discussed in Watts (1999) to study the effect of adding random links to a regular network or of rewiring links randomly. The adjacency matrix Dswk is of the type of a symmetric circulant, Toeplitz matrix whose eigenvalue