离散数学习题第四部分 .pdfVIP

图论习题

判断题

1．连通图一定存在汉密尔顿回路（）

2．完全图K是平面图（）

4

3．非平凡树T至少有2个一度顶点（）

4．设G是一个连通图，则G的一棵生成树T是包含G的所有结点的树（）

5．设T是棵树，则T不含有任何回路（）

6．对任意n1完全图K是一个欧拉图（）

n

7．图中结点次数为零的结点称为孤立点（）

8．无初级回路的连通图是树（）

9．完全图K是平面图（）

5

10．K既是欧拉图又是哈密顿图（）

5

11．任何非平凡的无向树都是二部图。（）

单项选择题

1．下图中是哈密尔顿图的是（）

2．无向图G是欧拉图当且仅当G是连通的且（）

A．G中各顶点的度数均相等

B．G中各顶点的度数之和为偶数

C．G中各顶点的度数均为偶数

D．G中各顶点的度数均为奇数

3．设G为完全二部图K，下面命题中为真的是（）

2,3

A．G为欧拉图B．G为哈密尔顿图C．G为平面图D．G为正则图

4．若图G有一条路经过图中每个结点恰好一次,则G（）

A．有一条欧拉路B．是欧拉图

C．有一条汉密尔顿路D．是汉密尔顿图

5．在有3个结点的图中,奇结点的个数为（）

A．0B．1

C．1或3D．0或2

5．结点数为奇数且所有结点的度数也为奇数的连通图必定是（）

A．欧拉图B．汉密尔顿图

C．非平面图D．不存在的

6．设G为完全二部图K，下面命题中为真的是（）

2,3

A．G为欧拉图B．G为哈密尔顿图

C．G为平面图D．G为正则图

7．下图中（）是哈密尔顿图．

A．（1）B．（2）C．（3）D．（2）（3）

8．给定n个结点的一个图，它还是一个树的下列说法中，（）是不对的。

A．无回路的连通图

B．无回路但若增加一条新边就会变成回路

C．连通且e=v-1，其中e是边数，v是结点数

D．所有结点的度数≥2

9．设G如右图：那么G不是（）

A．平面图B．完全图