伊 第一章图的基本概念 对任意的G,∈M,有 0△G,=G△0=G,G△G,=0. 故空集☑是零元素，G的负元素是G:自身. 对任意的a,b∈F和任意的G,G,∈M,有 (ab)G,=a(6G), (a+b)G,=aG,△bGi, a(Gi△G,)=aG△aG 这是因为a,b只能取0或1，故用穷举法，将a,b的各种取值情况一一代 入验算，即可证明上面三个等式成立.例如，取a=0,b=1有 (0+1)G,=1·G,=G, (0·G)△(1·G)=0△G=G 设图G的边集是E={e,e2,.,cm},考虑集合 S={g1g2,.,gm}, 其中g:是仅由一条边e:(i=1,2,.,m)组成的子图. 对任意的G∈M,如果G的边集是{ee2,e,},那么 G=g△g2△.△g 这就是说，G的任一子图均可由S生成 最后，我们来证明g1,g2,g。是线性无关的.事实上，如果有一组 不全为零的c(c1是0或1)使得 G1g1△c2g2△.△cmgm=0. 不失一般性，可假设c%=1,这时有c4ga=g.因所有的cg:(i≠k)中均不 含有ea边，故它们与g对称差必含有e4,这与上式矛盾，因此g1,g2,., gm线性无关.于是S是G的所有子图作成的线性空间M的一组基底， 且M的维数是m. 定理13设G为n阶连通图，则邻接矩阵A(G)的不同特征值数目； 满足不等式 d(G)+1≤s≤n. 证明右边的不等式显然成立. 对于左边的不等式，因A(G)是对称的，故不同的特征值的数目s等 于最小多项式的次数，即等于邻接代数的A(G)的维数，于是所要的不等 式由定理11得到. 定理14设A(G)的谱为Spec A(G)=”,则 (m2.m, ∑m=2m
§1,5图的代数表示及其特征 19 其中m:是特征值入：的重数，m为G的边数 证明因A(G)的各特征值的平方组成矩阵(A(G)2的特征值组，而 (A(G))2的对角线元素的和为 dd(u)-2m. 故A(G)的各特征值的平方和等于(A(G)2的迹，即 定理15设A是A(G)的任一特征值，则 1a1≤√/2a(n=D 证明设A(G)的n个特征值为p10,.A:不妨设入=Am:对向量 (1,l,.,1)和(p,e,.p-)应用Schwarz不等式，得 (3A)≤a-DE (1.2) 因邻接矩阵A(G)的对角元全为零，故 多a=习-0 于是 i-a-Sa 又由定理14知， 名=2n 李 2A=2m-8 现在(1.2)式变成(-A)2≤(n-1)(2m-2),即n2≤2m(n-1).故 1a1≤/2mm-D 例2若G=K.,则Spec A(K.)= -1-1） (n-11J1 证明因为G=K.的邻接矩阵是 01.1 A(K)= 10.1 （11.0J
名 第一章图的基本概念 而矩阵 11.1） 11. 1 B= 11.1 〔0n] 的谱为Spec B= ,故A(Kn)=一L.十B的谱 n-11 [-1n-11 Spec A(K.) m-11J §1.6极图 定义1若简单图G的点集V有一个划分 v=UV,V,0V,=⑦，≠i, 且所有V,非空，V,内的点均不连通，则称G是一个1部图. 如果l=2,则G就是偶图；任何一个n阶图必是一个n部图；若l< 2≤n,易知任一4部图也是2部图. 定义2如果在一个l部图G中，V,|=,任何两点u∈V,v∈V, ≠j,i,j=1,2,.,l均邻接，则称G为完全1部图.记作K.,m(如图 1-17). a 图1-17 完全L部图也可表示为K一w=KVKV.VK,它显然有 三：个点和习叫，条边. 定义3如果在一个n个点的完全l部图G中， n=kl十r,0≤r<l
51.6极图 21 1Vl=|V21=.=|V,|=k+1, IV+1l=|V+2l=.=|Vl=k, 则称G为n阶完全1几乎等部图，记为Tm,V|=|V2|=.=V,的 完全1几乎等部图称为完全1等部图。 从图1-18中可看出，当点集V的划 分为V1={u},V2={,5},V3={, %}时，则G是3部图，若点集V的划分为 V1={,5},V2={h,},V3={u4,%》 时，G也是3部图.对连通偶图就有下列 图1-18 结果 定理16连通偶图的2部划分是惟一的. 证明设连通偶图G的2部划分为V,UV2=V.取v∈V1,由于 G连通，对任何u∈V1UV2,G中有联结u和v的路，故d(v,w)有定 义.因为任何一条以v为起点的路交替地经过V1和V2的点，可知一 个点u∈V2当且仅当d(v,u)是奇数.该准则惟一地决定了G的2部 划分 定理17n阶完全偶图K的边数m=m2,且有 m≤引，其中L表示不大于实数工的最大整数 证明第一个结论是显然的。 设「x1表示不小于实数x的最小整数，且还有「x1=一L一x小.若n 为偶数，则K有=受·受=号条边：若n为奇数，则K+1有 m+别「H 故命题得证. 口 对于1部图也有类似的特征. 定理18n阶l部图G有最多边数的充要条件是G≥T. 证明由代数学知，l个正整数m地，m的函数f=∑m,在约 束条件之%=n下达到极大值的充要条件是对任何1≤<≤，有% %≤1，故若取%=kG=r十1，r十2，.，0，而n=k+1(i=1,2,.,）使 得|VI=|V2=.=|V,=m=k+1,V+1=|V+2=.=|V,|==k, 此时n阶L部图G的边数f=n”,必极大，而这时的G空T
名 第一章图的基本概念 下面我们将证明由Turan(1941)提出的一个著名的定理.它确定了 有n个顶点而不包含K+1为其子图的简单图所能具有的最大边数 Turan定理已经是称为所谓的极图理论这样一个有意义的图论分支的先 驱.我们将从Erd6s(1970)的下述结果来导出它. 定义4设G和H是两个n阶图，若存在V(G)和V(H)的一个一 对应4，使对任何点v∈V(G),有 dc()≤dH((v), 则称H的度序列优于G(简称H度优于G),或G的度序列弱于H(简 称G度弱于H). 定理19若n阶简单图G不包含K+1,则G度弱于某个完全l部图 H.且若G具有与H相同的度序列，则G空H. 证明对！用归纳.当(=1时定理显然成立.假设定理对所有<： 成立，并且设G是不包含K+1的简单图.选择G中度为△的一个定点u, 并且置G=G[N(u)](如图1-19(b).由于G不包含K+1,所以G不 包含K,因而由归纳法假设，G度弱于某个完全(l一1)部图H1(如图 1-19(c). (a)G(55444433) (b)G:=G[N(M)] (c)H (④G,VG,(55555555) (e)H=H,VG,(6655555) 图1-19