[工学]图论及其应用第1章.ppt

三、邻接代数 给定图G , 容易验证G 的邻接矩阵的全体复系数多项式在通常的矩阵运算下构成一个有限维的线性空间，它也是一个代数，称为图G的邻接代数，记为Λ(G)。 用图G的点数和直径可以给出邻接代数Λ(G)的维数的界。 定理11 n阶连通图G的邻接代数的维数有 d(G)＋１≤dimΛ(G)≤n 回忆线性代数的一些概念。设A = (aij) 是一个n 阶方阵，其中 aij∈C（复数集合）。A的行（列）组成的n维向量称为A的行（列）向量。λ称为方阵A的特征值，如果存在数域C 中一个非零列向量X，使得 AX=λX （1） 则X 称为A的属于λ的一个特征向量。 实际上λ是方程 |λIn-A | = 0 （2）的根，其中In为n阶单位矩阵。 若方程（2）有s 个相异的根λ1,λ2,…λs,其重数依次记为m1, m2,…, ms（有 m1+m2+…+ms = n），称 Spec A = 为 A 的谱。 例1 设A 为4圈C4 的邻接矩阵，求A的谱。 解 C4的邻接矩阵 于是 |λI4 -A | = =λ2(λ-2)(λ+2) 定理13 设G为n 阶连通图，则邻接矩阵A(G)的不同特征值数目s 满足不等式 d(G)+1≤ s ≤n 证明 右边的不等式显然成立。 所以A 的特征值为 - 2 , 0, 2 ; 其重数依次记为1,2,1。故 Spec A = 对于左边的不等式，因A(G) 是对称的，故不同的特征值的数目s 等于最小多项式的次数，即等于邻接代数的Λ(G)的维数，于是所要的不等式由定理11得到。 定理14 设 m为 图G 的边数，A(G) 的谱为 Spec A(G) = 则 证明 因A(G)的各特征值的平方组成矩阵[A(G) ]2的特征值组，即λi2 是[A(G) ]2 的特征值且重数相同，故由代数理论知 等于[A(G) ]2的迹（[A(G) ]2的对角线元素的和）。 而[A(G) ]2的迹有 定理10的推论及握手定理 故 证明 设A(G)的n 个特征值为ρ1, ρ2,…, ρn。不妨设λ=ρn。对向量 (1,1,…,1) 和 (ρ1, ρ2,…, ρn-1) 应用许瓦兹（Schwarz）不等式，得 （5.1） 定理15 设λ是A(G)的任一特征值，则 如4圈 的谱: 有(-2)2+22=8 因邻接矩阵A(G)的对角元全为零, 故 于是 又由定理14知 故 这样（5.1）式变成 (-λ)2≤(n-1)(2m-λ2) 即 nλ2≤2m(n-1) 故 例 C4中, n=4, m=4, 故 （5.1） §1.6 极图 定义1 若简单图G的点集V有一个划分 V= ，Vi∩Vj =φ i≠j 且所有Vi非空， Vi内的点均不相邻，则称G是一个l 部图。 说明: (1) 如果l=2，则G就是偶图； (2) 任何一个n阶图必是一个n部图； (3) 若l1l2≤n，易知任意的 l1部图也是l2部图。 定义2 如果在一个l 部图G中，|Vi|=ni，任何两点 u∈Vi ,v ∈Vj , i≠j , i,j =1,2,…, l 均邻接，则称G为完全l 部图。记作 v1 v2 v3 v5 v4 v6 K1,2,3 例 注: 它有 个点和 条边。 定义3 如果在一个n个点的完全l 部图G中， n = kl + r 0≤rl |V1| = |V2| = … = |Vr| = k + 1; |Vr+1| = |Vr+2 | = … = |Vl | = k 则称 G 为n 阶完全 l 几乎等部图，记为Tl ,n。 |V1| = |V2| = …