内容发布更新时间 : 2024/11/2 14:27:05星期一 下面是文章的全部内容请认真阅读。

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吗？

解：由定理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为小于等于

70的最大整数，即：２３ 3 ∴ 最多有23个顶点 7.7 设n阶无向简单图G中，δ（G）=n-1，问△（G）应为多少？

解： 假设n阶简单图图n阶无向完全图，在Kn共有为n（n-1）

∴每个顶点的度数为

n(n?1)条边，各个顶点度数之和2n(n?1)=n-1 n ∴△（G）=δ（G）=n-1

7.8 一个n（n≥２）阶无向简单图Ｇ中，n为奇数，有r个奇度数顶点，问Ｇ的补图G中有几个奇度顶点？

解：在Kn图中，每个顶点的度均为（n-1），n为奇数，在Ｇ中度为奇数的顶点在G中仍然为奇数，

∴共有r个奇度顶点在G中

７.９ 设Ｄ是n阶有向简单图，Ｄ’是Ｄ的子图，已知Ｄ’的边数m’＝n（n-1），问Ｄ的边数m为多少？

解： 在Ｄ’中m’＝n（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