第9章 习题解答
习题 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。因为是完全图，1所以ai+bi=n-1，?ai??bi=n(n-1)，?ai－?bi?0。
2i?1i?1i?1i?1nnnn方法1：
?ai??bii?1i?1n2n2??(ai?bi)??(ai?bi)(ai?bi)
i?1i?1n22n =?(n?1)(ai?bi)?(n?1)(?ai??bi)=0
i?1i?1i?1nnnnn2所以，?ai??bi
i?1i?12方法2：
1
第9章 习题解答
?bi2??((n?1)?ai)2=?((n?1)2?2(n?1)ai?ai2)
i?1i?1ni?1nnn =?(n?1)?2?n?1??ai??ai2
2i?1i?1i?1nn12 =n?n?1??2?n?1?n?n?1???ai??ai2
2i?1i?12nn5.试证明图9.6中(a)和(b)两个图是同构的。
证明：设图(a)为G=
令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,e?，E1=?(a,b),(a,c),(a,c),(b,c),(b,d),(d,e),(c,e),(e,e)? V2= ?1,2,3,4,5?，E2=?(1,2),(1,3),(1,3),(2,3),(2,4),(4,5),(3,5),(4,4)?
E1和E2中重复出现的无序对是图中的平行边，如E1中的(a,c)和E2中的(1,3)都是平行边。
⑴ 试画出G1和G2的图形。 ⑵ 证明G1和G2不同构。
解：⑴G1如图9.77所示，G2如图9.78所示。
2
第9章 习题解答
⑵反证法。
设图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的边数为应是整数。即
11n(n-1)×，显然，它2211n(n-1)×=k。于是有n(n-1)=4k，因为n和n-1是两个相邻数，所以 n=4k22或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)≤
2m≤?(G)。 n证明：根据最小度的定义，?v?V，deg(v)≥?(G)，所以，
2m=?deg(v)≥???G?=n?(G)
i?1i?1nn即 n?(G) ≤2m，整理后得，?(G)≤
2m n另一方面，根据最大度的定义，?v?V，deg(v)≤?(G)，与前面推理类似的可得，
2m≤n?(G) 整理后得，?(G)≥
2m n2m≤?(G) n所以， ?(G)≤
9.设G=?V,E?是无向简单图，|V|=n，n≥3且为奇数，试证明G和G中奇度结点个数
3
第9章 习题解答
相等。
证明: 令G=?V,E?， deg(v)表示G中结点v的度。deg(v)表示G中结点v的度。 因为n≥3且为奇数，?v∈V，deg(v)+deg(v)=n-1，所以，n-1是偶数。故deg(v)与deg(v)同偶或同奇。
G与G中的奇度结点个数相等。
4
第9章 习题解答
习题 9.2
1.图G=?V,E?如图9.12所示，求出从a到f的所有初级路。
解：从a到f的所有初级路有 abcf，abcef，abef，abecf，adebcf，adecf，adef。 2.图G=?V,E?如图9.13所示，求出从d出发的所有初级回路。
解：从d出发的所有初级回路为：dbad，debad。
3.在无向图G中，从结点u到结点v有一条长度为偶数的基本路，从结点v到结点u又有一条长度为奇数的基本路，证明在G中必有一条长度为奇数的回路。
证明：设Cuv是结点u到结点v长度为偶数的基本路。Cvu是结点v到结点u长度为奇数的基本路。则由u沿Cuv到达v，再由v沿Cvu到达u，这是一条通过u和v的回路，它的长度是奇数。
4.试证明无向图G中恰有两个奇数度的结点，则这两结点间必有一条路。
证明：反证法。设这两个结点间无任何路，它们必属于两个不同的连通分支的(否则，它们之间必有路的)，则这两个连通分支的每一仅有一个奇度结点，与定理9.1.1的推论相矛盾。所以，这两结点间必有一条路。
5