图论复习题.docx

WORD格式
专业资料整理
（二）图论复****题
一、选择题
1．设图G＝<V,E>，vV，则下列结论成立的是 ( C )．
A．deg(v)=2E B．deg(v)=E
C． deg(v) 2E [PPT23] D． deg(v) E
vV vV
定理1 图G=（V，E）中，所有点的次之和为边数的两倍
2．设无向图G的邻接矩阵为
0 1 1 0 0
1 0 0 1 1
1 0 0 0 0
0 1 0 0 1
0 1 0 1 0
则G的边数为( B )．
A．6 B．5 C．4 D．3
3、设完全图Kn有n个结点(n2)，m条边，当（C）时，Kn中存在欧拉回路．
A．m为奇数 B ．n为偶数 C．n为奇数 D ．m为偶数
解释：Kn每个结点的度都为 n－1，所以若存在欧拉回路则 n－1必为偶数。n必
为奇数。
4．欧拉回路是（ B ）
[PPT40] C. 既是基本回路也是简单回路

5．哈密尔顿回路是（ C ）
B. 简单回路
基本回路也非简单回路
[PPT40]：哈密尔顿回路要求走遍所有的点，即是基本回路的点不重复，也可以
WORD格式
专业资料整理
是简单回路的边不重复。
6．设G是简单有向图，可达矩阵 P(G)刻划下列关系中的是（ C ）
A、点与边 B 、边与点 C、点与点 D 、边与边
7．下列哪一种图不一定是树（ C）。
WORD格式
专业资料整理

C. 每对顶点间都有通路的图

B. 有n个顶点n-1条边的连通图

WORD格式
专业资料整理
图
WORD格式
专业资料整理
8．在有n个结点的连通图中，其边数（ B）
-1条 -1条 C. 最多有n条 D. 至少有n
条
9．下列图为树的是（C）。
A、G1
{a,b,c,d},{
a,a
,
a,b
,
c,d
}
B、G2
{a,b,c,d},{
a,b
,
b,d
,
c,d
}
C、G3
{a,b,c,d},{
a,b
,
a,d
,
c,a
}
D、G4
{a,b,c,d},{
a,b
,
a,c
,
d,d
}
10、下面的图7-22
是（C）。
；；；D. 欧拉图。
二、填空题
WORD格式
专业资料整理
1．无向完全图

K6有

15 条边。[6

×（6-1）]/2=15
WORD格式
专业资料整理
2．设连通无向图G有k个奇顶点，要使G变成欧拉图，在G中至少要
加 k/2 条边。
解：∵任何图中的奇点的个数为偶数
WORD格式
专业资料整理
∴在每对奇点处多加一条边形成了多重边， G图就成了欧拉图。
∵连通无向图G有k个奇顶点
∴有k/2对奇顶点
∴有多少对奇点就加多少条边
3、n阶无向完全图K的边数是(
n(n-1)
)，每个结点的度数是(n-1)。
2
n
证明：∵1个顶点的图有
0条边
2个顶点的图有
1条边
2（2 1）
∴满足1
2
当3个顶点以上时 假如n=k-1k>=3时
∵k-1个顶点的图有(k
1)(k
2)
k2
3k
1条边
2
k2
2
2
k(k
1)
k
条边
k个顶点的图有
2
2
2
∴k-1个顶点的图与k
个顶点的图产生的边数为
(
k2
3k
k2
k
k
1
2
1)
(