离散数学第9章习题答案

1 习题9 1. 设G 是一个(n，m)简单图。证明：，等号成立当且仅当G 是完全图。 证明：（1）先证结论： 因为G 是简单图，所以G 的结点度上限 max(d(v)) ≤ n-1, G 图的总点度上限为 max(Σ(d(v)) ≤ n﹒max(d(v)) ≤ n(n-1) 。根据握手定理，G 图边的上限为 max(m) ≤ n(n-1)/2,所以。 （2） =〉G 是完全图 因为G 具有上限边数，假设有结点的点度小于 n-1,那么 G 的总度数就小于上限值，边数就小于上限值，与条件矛盾。所以，G 的每个结点的点度都为n-1，G 为完全图。 G 是完全图 =〉 因为G 是完全图，所以每个结点的点度为n-1, 总度数为n(n-1)，根据握手定理，图G的边数 。■ 2. 设G 是一个（n，n+1）的无向图，证明G 中存在顶点u，d（u）≥3。 证明：反证法，假设,则 G 的总点度上限为max(Σ(d(u)) ≤ 2 n，根据握手定理，图边的上限为max(m) ≤ 2n/2=n。与题设m = n+1，矛盾。因此，G 中存在顶点u，d（u）≥3。■ 3．确定下面的序列中哪些是图的序列，若是图的序列，画出一个对应的图来: （1）（3，2，0，1，5）； （2）（6，3，3，2，2） （3）（4，4，2，2，4）； （4）（7，6，8，3，9，5） 解：除序列（1）不是图序列外，其余的都是图序列。因为在（1）中，总和为奇数，不满足图总度数为偶数的握手定理。 可以按如下方法构造满足要求的图：序列中每个数字 ai 对应一个点，如果序列数字是偶数，那么就在对应的点上画 ai/2 个环，如果序列是奇数，那么在对应的点上画(ai-1)/2 个环。最后，将奇数序列对应的点两两一组，添加连线即可。下面以（2）为例说明： (6 , 3, 3, 2, 2 ) 对应图G 的点集合 V= { v1,v2,v3,v4,v5} 每个结点对应的环数(6/2, (3-1)/2, (3-1)/2, 2/2,2/2) = (3,1,1,1,1) v 1 v 5 v 3v 4 v 2 2 将奇数3，3 对应的结点v2,v3 一组，画一条连线 其他序列可以类式作图，当然大家也可以画图其它不同的图形。■ 4．证明：在（n，m）图中。 证明：图的点度数是一组非负整数{d(v1),d(v2)…d(vn)}，那么这组数的算术平均值一定大于等于其中的最小值，同时小于等于其中的最大值。对应到图的术语及为：最大值为，最小值为 δ，平均值 = (d(v1)+d(v2)…+d(vn))/n = 2m/n,所以。■ 5．证明定理 10.2。 【定理 10.2】 对于任何（n,m）有向图G =（V，E）， 证明：有向图中,每条有向边为图贡献一度出度，同时贡献一度出度，...