§1.1图和简单图 中的图是完全偶图K23 ( (c) 图1-2 对于一个简单图G=(V,E),令集合E={uxw≠v,u,v∈V),则图 H=(V,E\E)称为G的补图，记为H=G.图1-3中的(a),(b)两图是 互补的. (a) b 图1-3 定理1若n阶图G是自补的（即G≥G),则n=0,1(mod4)】 证明因为G是自补的，则G和G有同样多的边数，且边数 m(G)+m(G)=m(K,)=nn2卫， 从而 m(G)=na卫， 又因G的边数m(G是整数，故n(n一1)/4为整数，即只能有n=0(mod4) 或(n-1)=0(mod4). 图1-3的(a)或(b)均是自补图. 三、顶点的度，度序列 G的顶点v的度d(o)是指G中与o关联的边的数目，每个环计算两 次.用(G)和△(G)分别表示G的顶点的最小度和最大度.为方便，奇数 度的顶点称为奇点，偶数度的顶点称为偶点.设G=(V,E)为简单图，如 果对所有oEV,有d(v)=k,称图G为k正则图.完全图和完全偶图K量
第一章图的基本概念 均是正则图。 定理2图G=(V,E)中所有顶点的度的和等于边数m的2倍，即 d(w)=2m. (1.1) 证明因为在一个图中移去每一条边均使它的两个端点的度各减少 1,故上定理显然成立. 推论1在任何图中，奇点个数为偶数。 证明设V1和V2分别是G中奇点集和偶点集.则由定理2知 d)+d(-du 是偶数，而∑d(o)也是偶数，则∑d(o)是偶数，从而1V:是偶数.口 EV. 推论2正则图的阶数和度数不同时为奇数 证明设G是k正则图，若k为奇数，则由推论1知正则图G的点数 必为偶数 ▣ 一个图G的各个点的度d1,d2,.,dn构成的非负整数组(d1,d2,., d)称为G的度序列，它们的和当然是2m.反之，设有n个非负整数d1, d,d.,且∑d=2m是-个偶数，现问是否存在一个图G以数组d, d2,.,d为它的度序列，如果这样的图存在，怎样重构这个图. 以上问题，实质是数论中的一个划分问题.所谓划分是指将一个正 整数，表示为若干正整数的和，或者看作一个无序正整数组，这些正整数 的和是飞 若一个n阶简单图G各点的度为d:,则分正整数k为n个部分的划 分2d,称为是图划分.若一个划分是图划分，则一定有d:≤n一1，且是 偶数.反之不一定成立.例如，偶数4有五种划分： 4,3+1,2+2,2+1+1,1+1+1+1. 但属于图划分的却只有两种（如图1-4）. 若对一个非负整数组(d山，d,.， d),之d,=2m,存在-个简单图G, 以它为度序列，则称这个数组是可图 2+1+1 1+1+1+1 的.下面的定理给出了可图数组的判 图1-4 断和怎样构造图. 定理3设有非负整数组Ⅱ=(d,d2,.,dn),且∑d,=2m是一个 偶数，n-l≥d≥d2≥.≥d,它是可图的充要条件为Ⅱ'=(d2一1，d
§1.2子图与图的运算 1,.,d。-1-l,dn)是可图的. 为了说明这个定理，我们试鉴定下列非负整数组 Π=(5533222)， Π'=(422112)， Π1=(422211) T1=(11101). 显然Ⅱ{是可图的，所以Ⅱ也是可图的. 这样构成的图画在图1-5中. 四、图的频序列 定理4一个简单图G的n个点的 度不能互不相同. 证明因为对任何这样的图G, 图1-5 △(G)≤n-1.如果△(G)<n一1，则度不 相同的点只可能有△(G)十1个（即度是△(G),△(G)一1，.，1,0的点）， 而△(G)十1<，所以必然另外有些点与圆括弧内的点的度数相同，得证 如果△(G)=n-1,则G中没有孤立点，即6(G)>0,所以△(G)-6(G)< n一1，同上面一样，度不相同的点只有△(G)一6(G)+1个，显然小于n, 故图G中也有度相同的点。 定义3设n阶图G的各点的度取s个不同的非负整数d1,d2,., d.又设度为d的点有，(i=1,2,.,)个，则有∑6，=n故非整数组 (6,b,.,b,)是n的一个划分，称为G的频序列. 定理5一个n阶图G和它的补图G有相同的频序列. 证明因为根据补图的定义有dc(:)十d()=n一l,这就是说，若 在G中度为d,(i=1,2,)的点有6个，则同样这6，个点在C中的度就 变为d=(n一1)一d,(i=1,2,.,s),故G与C有相同的频序列. §1.2子图与图的运算 一、子图 定义1如果V(H)二V(G),E(H)二E(G),且H中边的重数不超 过G中对应边的重数，则称H是G的子图，记为H二G.有时又称G是
6 第一章图的基本概念 H的母图 当H二G,但H≠G时，则记为HCG,且称H为G的真子图.G的 生成子图是指满足V(H)=V(G)的子图H. 假设V是V的一个非空子集.以V'为顶点集，以两端点均在V中 的边的全体为边集所组成的子图，称为G的由V导出的子图，记为 GV门，简称为G的导出子图，导出子图G[八V门记为G-V',它是G中 删除V中的顶点以及与这些顶点相关联的边所得到的子图.若V'= {o},则把G-{简记为G一u, 假设E是E的非空子集.以E为边集，以E中边的端点全体为顶点 集所组成的子图称为G的由E导出的子图，记为G[E],简称为G的边 导出子图，边集为E1E的G的导出子图简记为G一E.若E={},则用 G-e来代替G-{e以. 设G=(V,E)是没有孤立点的图，其边数为m,由于每条边都有两种 选择，即包含于或不包含于某个子图中，如果子图每条边都包含就是图 G,如果每条边都不包含，就是空图.故有下面的 定理6简单图G中所有不同的生成子图（包括G和空图）的个数是 2m个. 事实上，当图包含某边时，也就意味着包含了与该边关联的两个顶 点，故不同子图的个数是 二、图的运算 设G,G2是G的子图.若G和G,无公共顶点，则称它们是不相 交的；若G和G,无公共边，则称它们是边不重的.G和G2的并图 GUG是指G的一个子图，其顶点集为V(G)UV(G),其边集为 E(G)UE(G);如果G和G2是不相交的，有时就记其并图为G十G2 类似地可定义G和G,的交图G∩G2,但此时G和G2至少要有一个 公共顶点.G和G:的差G一G2是由G中去掉G中的边组成的图. G与G,的对称差G△G2是G和G,的并中去掉G与G,的交所得到 的图，即 G△G2=(GUG2)-(G∩G)=(G-G)U(G2-G). 设G和G:如图1-6所示，它们的并、交、差及对称差分别如图1-7 所示
1.2子图与图的运算 G2△G 图1-7 定义2在不相交的G和G2的并图G十G2中，把G的每个顶点 和G2的每个顶点连接起来所得到的图称为G和G2的联图，记为GV G2.如图1-8(a),(b)所示. 不难看出，K,VK4=K5,K2VK,=K5,同理可得K6=K1VK,= K2 VK=K3 VK3 定义3设G=(V,E),G2=(V2,E2),对点集V=V1×V2中的任 意两个点u=(山，2)和v=(,2),当（山=和adj)或(w2=2和