离散数学第七章答案
【篇一：离散数学第七章检测题及答案】
>一、 单项选择题（每小题2分，共20分） 1．下图中是哈密尔顿图的是(2 )
2．下面给出的四个图中，哪个不是汉密尔顿图（ （4） ）． 3．下列是欧拉图的是( 2 )
4. 下列各图不是欧拉图的是（4 ） 5．设a(g
)是有向图g?,e的邻接矩阵，其第i列中“1”的数目为（）。 (c) (1)．结点vi的度数； (2)．结点vi的出度； (3)．结点vi的入度； (4)．结点vj的度数。 6．无向图g中有16条边，且每个结点的度数均为2，则结点数是( 2 )
(1)．8(2)．16(3)．4(4)．32 7．设Ｇ＝?v,e?为无向图，?7,e?23，则Ｇ一定是（ （4） ）．
(1)．完全图； (2)．零图； (3)．简单图； (4)．多重图． 8．若具有n个结点的完全图是欧拉图，则n为( 2 ). (1)．偶数；(2)．奇数； (3)． 9；(4)． 10．
9．无向图g是欧拉图，当且仅当（ ）．(1)
(1)．g连通且所有结点的度数为偶数； (2)．g的所有结点的度数为偶数； (3)．g连通且所有结点的度数为奇数；(4)．g的所有结点的度数为奇数． 10．下面哪一种图不一定是树（ ）． (3) (1)．无圈连通图； (2)．有n个结点n?1条边的连通图；
(3)．每对结点间都有路的图； (4)．连通但删去一条边就不连通的图． 二、 填空题（每空3分，共45分）
1．在下图中，结点v2的度数是 4 ，结点v5的度数是3。
2．在一棵根树中，有且只有一个结点的入度为，其余所有结点的入度均为。
其中入度为__0___的结点称为树根，出度为__0___的结点称为树叶。 3．设图g1?1,e1，g2?2,e2,且e2?e1，如果 ，则称g2是g1的子图，如果 ，则称g2是g1的生成子图。(v2?v1,v2?v1)
4．在任何图g?,e中，?deg(v)= ，其奇数度结点的个数必为 v?v
偶数。
5．一棵有6个叶结点的完全二叉树，有___5__个内点；而若一棵树有2个结点度数为2，一个结点度数为3，3个结点度数为4，其余是叶结点，则该树有__9___个叶结点。 ?0?1 6
．设图g?v,e，v＝｛ v1,v2,v3,v4｝的邻接矩阵a(g)= ? ?1??1 1010 0100 1??1
?， 0??0?
则 v1 的入度deg(v1)＝，v4的出度deg(v4)。 7．一个无向树中有6。
三、 简答题（每小题5分，共25分）
1．对有向图g?,e求解下列问题： （1）写出邻接矩阵a； （2
）g?,e中长度为3的不同的路有几条？其中不同的回路有几条？ 解：（1）邻接矩阵为： ?0
?0?a??0 ??1??0 10010 01000
0000100011 1?
?0?1?， ?0?0??10010 10100 0??1 ??10?? 3
0?,a??1??1??0 ?0???0 10101 00011 01010 1?
?0?0? ?1?1?? ?0
?0?2
（2）a??0 ??0??1
则，g?,e中长度为3的不同的路有10条，其中有1条不同的回路。 2．设有２８盏灯，拟公用一个电源，求至少需要４插头的接线板的数目。
解：设至少需要4插头的接线板i个，则有 （4-1）i=28-1（3分） 故 i=9
即至少需要9个4插头的接线板。 （2分）
3．设有6个城市v1，v2，?，v6，它们之间有输油管连通，其布置如下图,si(数字)中si为边的编号，括号内数字为边的权，它是两城市间的距离，为了保卫油管不受破坏，在每段油管间派一连士兵看守，为保证每个城市石油的正常供应最少需多少连士兵看守?输油管道总长度越短，士兵越好防守。求他们看守的最短管道的长度。(要求写出求解过程 )
解：为保证每个城市石油的正常供应最少需5连士兵看守.
求看守的最短管道相当于求图的最小生成树问题，此图的最小生成树为：
因此看守的最短管道的长度为： Ｗ（Ｔ）＝１＋1＋2＋2＋2＝８． 4．以给定权1, 4, 9, 16, 25, 36, 49, 64, 81, 100构造一棵最优二叉树。
5．一次学术会议的理事会共有20个人参加，他们之间有的相互认识，但有的相互不认识。但对任意两个人，他们各自认识的人的数目之和不小于20，说明能否把这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人？根据是什么？
解：可以把这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人。（1分） 根据是：分别用20个结点代表这20个人，将相互认识的人之间连一条线，便得到一个 无向简单
图g?v,e，每个结点vi?v的度数是与vi认识的人的数目，由题意知 vi,vj?v，有degv(i?) devg(?)，2于
是g?v,中存在哈密尔顿回路，设j c?vi1vi2?
vi20vg?v,e中的一条哈密尔顿回路，按此回路安排园桌座位即符合要是i
求。（4分）
四．证明与应用题（10分）
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个顶点
解： 假设n阶简单图图n阶无向完全图，在kn共有 为n（n-1）
∴每个顶点的度数为n(n?1)条边，各个顶点度数之和2n(n?1)=n-1 n
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
【篇三：华东师范大学离散数学章炯民课后习题第7章
答案】
注意
(p123) 2，6，7
1. 6个学生：alice、bob、carol、dean、santos和tom，其中，alice和carol不和，dean和carol不和，santos、tom和alice两两不和。请给出表示这种情形的图模型。 2. 至少含一个顶点的c3的子图有多少个？
离散数学第七章答案
