离散数学 第七章检测题及答案

离散数学第七章检测题

一、 单项选择题（每小题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． 某次聚会的成员到会后相互握手，试用图论的知识说明与奇数个人握手的人数一定是一

个偶数。

证: 用结点代表成员, 握手的成员之间连一条线, 则所有聚会的成员之间的握手

情况可以用一个图来表示，其中每个结点的度数就是该结点所代表的成员握

手的人数,由于任一图中奇数度结点的个数为偶数,所以与奇数个人握手的人数一定是一个偶数。

本文来源：https://www.bwwdw.com/article/r7ae.html