(离散习题附答案9.docVIP

习题 9.1 1.设无向图G有16条边，有3个4度结点，4个3度结点，其余结点的度数均小于3，问：G中至少有几个结点？ 解：当其余结点都为2度时，结点数最少。根据定理9.1.1列方程：3×4+4×3+2×x=2×16。解方程得：x=4。无向图G中的结点数为：4+3+4=11。所以，G中至少有11个结点。 2.设无向图G有9个结点，每个结点的度数不是5就是6，证明：G中至少有5个6度结点或至少有6个5度结点。 证明：图G中：5度结点数可能为：0，1，2，3，4，5，6，7，8，9 6度结点数可能为：9，8，7，6，5，4，3，2，1，0 反证法，设6度结点小于5个且5度结点小于6个，则只可能有5个5度结点，4个6度结点(其他情况结点数的和小于9)。此时，各结点度数之和为：5×5+4×6=25+24=49。与结点度数之和为偶数(边数两倍)矛盾。 所以，G中至少有5个6度结点或至少有6个5度结点。 3.设图G有n个结点，n＋1条边，证明：G中至少有1个结点度数大于等于3。 证明：反证法。 设G=V,E，?v∈V，deg(v)≤2。所有结点的度数之和2(n+1)小于2n。即2(n+1)≤2n，化简后，2≤0，矛盾。 所以，G中至少有1个结点度数大于等于3。 4.证明在任何有向完全图中。所有结点入度的平方之和等于所有结点的出度平方之和。 证明：设G有n个结点，ai, bi分别是结点vi的入度和出度，i=1…n。因为是完全图，所以ai+bi=n-1，=n(n-1)，。 方法1： ==0 所以， 方法2： = = = 5.试证明图9.6中(a)和(b)两个图是同构的。 证明：设图(a)为G=V,E，图(b)为G′=V′,E′。 令g：V?V′，定义为：g(a)=1，g(b)=2，g(c)=3，g(d)=4。显然，g：V?V′是双射函数。根据双射函数g，E中的边和E′中的边有如下的对应关系： (a,b)?(1,2)，(a,c)?(1,3)，(a.d)?(1,4)，(b,c)?(2,3)，(c,d)?(3,4)。 所以 (a)与(b)同构。 6.设G1=V1,E1与G2=V2,E2是两个无向图，其中： V1= ía,b,c,d,ey，E1=í(a,b),(a,c),(a,c),(b,c),(b,d),(d,e),(c,e),(e,e)y V2= í1,2,3,4,5y，E2=í(1,2),(1,3),(1,3),(2,3),(2,4),(4,5),(3,5),(4,4)y E1和E2中重复出现的无序对是图中的平行边，如E1中的(a,c)和E2中的(1,3)都是平行边。 ⑴ 试画出G1和G2的图形。 ⑵ 证明G1和G2不同构。 解：⑴G1如图9.77所示，G2如图9.78所示。 ⑵反证法。 设图G1和G2是同构的，根据同度结点对应的原则：c?3，e?4 或c?4，e?3。 因为，c上关联了4个边，4上关联了3个边，所以，c?4，e?3是不可能的。 如果c?3，e?4，在G1中与e相邻的结点为d和c，deg(d)=2，deg(c)=4。在G2中与4相邻的结点为2和5，deg(2)=3，deg(5)=2，无论怎样对应都不能使用同度结点相对应。所以，这种情况也是不可能的。 综上所述，G1和G2不同构。 7.设G是n阶自补图，试证明n=4k或n=4k＋1，其中k为正整数。画出5个结点的自补图。是否有3个结点或6个结点的自补图？ 证明: 设G是n阶自补图，则由自补图的定义，G的边数为n(n-1)×，显然，它应是整数。即n(n-1)×=k。于是有n(n-1)=4k，因为n和n-1是两个相邻数，所以 n=4k或n-1=4k，即n=4k或n=4k+1。 5个结点的自补图如图9.79所示。 因为3和6度不能表示成为n=4k或n=4k＋1，所以，没有3个结点或6个结点的自补图。 8.设G=V,E是图，|V|=n，|E|=m，证明：?(G)≤≤?(G)。 证明：根据最小度的定义，?v?V，deg(v)≥?(G)，所以， 2m=≥=n?(G) 即 n?(G) ≤2m，整理后得，?(G)≤ 另一方面，根据最大度的定义，?v?V，deg(v)≤?(G)，与前面推理类似的可得， 2m≤n?(G) 整理后得，?(G)≥ 所以， ?(G)≤≤?(G) 9.设G=V,E是无向简单图，|V|=n，n≥3且为奇数，试证明G和中奇度结点个数相等。 证明: 令=V,， deg(v)表示G中结点v的度。表示中结点v的度。 因为n≥3且为奇数，?v∈V，deg(v)+=n-1，所以，n-1是偶数。故deg(v)与同偶或同奇。 G与中的奇度结点个数相等。