《离散数学(屈婉玲版)第七章部分答案》由会员分享，可在线阅读，更多相关《离散数学(屈婉玲版)第七章部分答案（2页珍藏版）》请在金锄头文库上搜索。
1、7.1 列各组数中，那些能构成无向图的度数列？那些能构成无向简单图的度数列？ （1）1，1，1，2，3（2）2，2，2，2，2（3）3，3，3，3 （4）1，2，3，4，5 （5）1，3，3，3 解答：（1） ， （2） ， （3） ， （5）能构成无向图的度数列。 （1） ， （2） ， （3）能构成五项简单图的度数列。 7.2 设有向简单图 D 的度数列为 2，2，3，3，入度列为 0，0，2，3，试求 D 的出度列。解：因为 出度=度数-入度，所以出度列为 2，2，1，0。 7.3 设 D 是 4 阶有向简单图，度数列为 3，3，3，3。它的入度列（或出度列）能为 1，1，1，1 吗？
2、解：由定理 7.2 可知，有向图的总入度=总出度。该有向图的总入度=1+1+1+1=4,总 出度=2+2+2+2=8,4！=8，所以它的出度列（或入度列）不能为 1，1，1，1。 7.6 35 条边，每个顶点的度数至少为 3 的图最多有几个顶点？解：根据握手定理，所有顶点的度数之和为 70，假设每个顶点的度数都为 3，则n 为小于等于的最大整数，即：370 最多有 23 个顶点 7.7设 n 阶无向简单图 G 中，（G）=n-1，问（G）应为多少？解： 假设 n 阶简单图图 n 阶无向完全图，在 Kn共有条边，各个顶点度数之2) 1( nn和为 n（n-1）每个顶点的度数为=n-1nnn) 1
3、( （G）=（G）=n-1 7.8 一个 n（n）阶无向简单图中，n 为奇数，有 r 个奇度数顶点，问的补图中有几个奇度顶点？G解：在 Kn图中，每个顶点的度均为（n-1） ，n 为奇数，在中度为奇数的顶点在中G仍然为奇数，共有 r 个奇度顶点在中G. 设是 n 阶有向简单图，是的子图，已知的边数 mn（n-1） ，问的边 数 m 为多少？解： 在中 mn（n-1） 可见为有个 n 阶有向完全图，则 即就 是本身，m=n（n-1） 7.18 有向图 D 入图所示。求 D 中长度为 4 的通路总数，并指出其中有多少条是回路？又有几条是 V3 到 V4 的通路？ 答: D 中长度为四的通路总数：15其中有 3 条是回路2 条是 V3 到 V4 的通路 评语：此题的结果是对的，但是应该写出求解过程，即：先写出邻接矩阵 A，然后求 A 的 四次幂，通过矩阵指出通路或回路的条数。 7.19 设 n 阶图 G 中有 m 条边，每个顶点的度不是 k 就是 k+1，若 G 中有 Nk个 k 度顶点，Nk+1个(k+1)度顶点，则 Nk为？解: 由题义可以得到: Nk*k+ Nk+1*(k+1)=2m 握手定理Nk+ Nk+1=n n 阶图由解得 Nk=n*(k+1)-2m
