图论复习题
（二）图论复习题
一、选择题
1．设图G ＝<V , E >，v ∈V ，则下列结论成立的是 ( C ) ．国营东方仪器厂
A ．deg(v )=2∣E ∣
方正ripB ． deg(v )=∣E ∣
C ．E v V v 2)deg(=∑∈ [PPT 23]
D ．
E v V
v =∑∈)deg(
定理1 图G=（V ，E ）中，所有点的次之和为边数的两倍
2．设无向图G 的邻接矩阵为
摩士集团⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡010*******
000011100100110
则G 的边数为( B )．
A ．6
B ．5
C ．4
D ．3
3、 设完全图K n 有n 个结点(n ≥2)，m 条边，当（ C ）时，K n 中存在欧拉回路． A ．m 为奇数
C ．n 为奇数
D ．m 为偶数 解释：K n 每个结点的度都为n －1，所以若存在欧拉回路则n －1必为偶数。n 必为奇数。
4．欧拉回路是（ B ）
A. 路径
B. 简单回路[PPT 40]
C. 既是基本回路也是简单回路
D.既非基本回路也非简单回路
5．哈密尔顿回路是（ C ）
A. 路径
B. 简单回路
C. 既是基本回路也是简单回路
D.既非基本回路也非简单回路
[PPT 40]：哈密尔顿回路要求走遍所有的点，即是基本回路的点不重复，也可
以是简单回路的边不重复。
6．设G 是简单有向图，可达矩阵P(G)刻划下列关系中的是（ C ）大和恒粮行
A 、点与边
B 、边与点
C 、点与点北京科瑞集团
D 、边与边
7．下列哪一种图不一定是树（C ）。
A.无简单回路的连通图
C. 每对顶点间都有通路的图
D. 连通但删去一条边便不连通的图
8．在有n 个结点的连通图中，其边数（B ）
A.最多有n-1条
B.至少有n-1条
C.最多有n 条
D.至少有n 条
初中数学教学大纲
9．下列图为树的是（C ）。
A 、>><><><=<},,,,,{},,,,{1d c b a a a d c b a G
B 、>><><><=<},,,,,{},,,,{2d c d b b a d c b a G
C 、>><><><=<},,,,,{},,,,{3a c d a b a d c b a G
D 、>><><><=<},,,,,{},,,,{4d d c a b a d c b a G
10、下面的图7-22是（C ）。
A.完全图；
B.平面图；
C.哈密顿图；
D. 欧拉图。
二、填空题
1．无向完全图K 6有 15 条边。[6×（6-1）]/2=15
2．设连通无向图G 有k 个奇顶点，要使G 变成欧拉图，在G 中至少要 加 k/2 条边。
解：∵任何图中的奇点的个数为偶数
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议