离散数学第检测题及答案.docVIP

离散数学第七章检测题 一、 单项选择题（每小题2分，共20分） 1．下图中是哈密尔顿图的是( 2 ) 2．下面给出的四个图中，哪个不是汉密尔顿图（　（4）　）． 3．下列是欧拉图的是( 2 ) 4. 下列各图不是欧拉图的是（ 4 ） 5．设是有向图的邻接矩阵，其第列中“1”的数目为（ ）。 (C) (1)．结点的度数； (2)．结点的出度； (3)．结点的入度； (4)．结点的度数。 6．无向图中有16条边，且每个结点的度数均为2，则结点数是( 2 ) (1)．8 (2)．16 (3)．4 (4)．32 7．设Ｇ＝，，则Ｇ一定是（　（4）　）． (1)．完全图；　　(2)．零图；　　(3)．简单图；　　(4)．多重图． 8．若具有个结点的完全图是欧拉图，则为( 2 ). (1)．偶数；(2)．奇数； (3)． 9； (4)． 10． 9．无向图是欧拉图，当且仅当（　　　　）． (1) (1)．连通且所有结点的度数为偶数；　　(2)．的所有结点的度数为偶数； (3)．连通且所有结点的度数为奇数；　 (4)．的所有结点的度数为奇数． 10．下面哪一种图不一定是树（　　　　）． (3) (1)．无圈连通图；　　　　 　(2)．有个结点条边的连通图； (3)．每对结点间都有路的图；　(4)．连通但删去一条边就不连通的图． 二、 填空题（每空3分，共45分） 1．在下图中，结点v2的度数是 4 ，结点v5的度数是 3 。 2．在一棵根树中，有且只有一个结点的入度为__0___，其余所有结点的入度均为_1__。 其中入度为__0___的结点称为树根，出度为__0___的结点称为树叶。 3．设图，，如果 ，则称是的子图，如果 ，则称是的生成子图。() 4．在任何图中，= 2 │E│ ，其奇数度结点的个数必为 偶数 。 5．一棵有6个叶结点的完全二叉树，有___5__个内点；而若一棵树有2个结点度数为2，一个结点度数为3，3个结点度数为4，其余是叶结点，则该树有__9___个叶结点。 6．设图，＝｛ ,,,｝的邻接矩阵= ， 则 的入度＝ 3 ，的出度= 1 　。 7．一个无向树中有6条边，则它结点数为 7 。 三、 简答题（每小题5分，共25分） 1．对有向图求解下列问题： （1）写出邻接矩阵； （2）中长度为3的不同的路有几条？其中不同的回路有几条？ 解：（1）邻接矩阵为： ， （2） 则，中长度为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个人，将相互认识的人之间连一条线，便得到一个 无向简单图，每个结点的度数是与认识的人的数目，由题意知，有，于是中存在哈密尔顿回路，设是中的一条哈密尔顿回路，按此回路安排园桌座位即符合要求。（4分） 四．证明与应用题（10分） 1． 某次聚会的成员到会后相互握手，试用图论的知识说明与奇数个人握手的人数一定是一个偶数。 证: 用结点代表成员, 握手的成员之间连一条线, 则所有聚会的