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

(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；