侥息伎北水谢梦脐锑侥嗽涟面
第1讲 图的基本概念
第1讲测验
1、单选题：
具有3个顶点的互不同构的图多少个？
A: 1
B: 2
C: 3
D: 4
答案: 4
2、单选题：
设图G = (V, E)，其中V = {A,B,C,D}, E = {{A,B},{A,C},{A,D},{B,C},{C,D}},则顶点C的度为多少？
A: 1
B: 2
C: 3
D: 4
答案: 3
3、单选题：
若供选择答案中的数值表示一个图中各个顶点的度，能画出图的是哪个？
A: 1，2，2，3，4，5
B: 1，2，3，4，5，5
C: 1，1，1，2，3
D: 2，3，3，4，5，6
答案: 1，1，1，2，3
4、单选题：
关于图的同构，下列说法不正确的是（）。
A: 设图G和图G’同构，图G中包含一个子图为顶点数为n的完全图，则图G’中一定包含一个子图为顶点数为n的完全图。
B: 设图G和图G’同构，则图G和图G’的顶点数相同。
C: 设图G和图G’同构，则图G和图G’的边数相同。
D: 所有包含6个顶点的3次正则图互相同构。
答案: 所有包含6个顶点的3次正则图互相同构。
5、判断题：
有相同的顶点数和边数的两个图同构。
A: 正确
B: 错误
答案: 错误
6、判断题：
具有两个顶点的互不同构的图有2个。
A: 正确
B: 错误
答案: 正确
7、判断题：
存在一个包含5个顶点的图，其各个顶点的度依次为4，4，3，2，2。
A: 正确
B: 错误
答案: 错误
8、判断题：
存在一个包含5个顶点的图，其各个顶点的度依次为4，4，4，2，2。
A: 正确
B: 错误
答案: 错误
9、判断题：
设图G = (V, E)，其中V = {A,B,C,D}, E = {{A,B},{A,C},{A,D},{B,C},{C,D}},则G是一个3次正则图。
A: 正确
B: 错误
答案: 错误
10、判断题：
设图G = (V, E)，其中V = {A,B,C,D}, E = {{A,B},{A,C},{A,D},{B,C},{C,D}},则G是一个完全图。
A: 正确
B: 错误
答案: 错误
11、判断题：
设图G = (V, E)，其中V = {A,B,C,D}, E = {{A,B},{A,C},{A,D},{B,C},{C,D}}, 图G’={U,F}，其中U={A,B,D}, F = {{A,B}, {B,D}}，则G’是G的子图。
A: 正确
B: 错误
答案: 错误
12、判断题：
设图G = (V, E)，其中V = {A,B,C,D}, E = {{A,B},{A,C},{A,D},{B,C},{C,D}}, 图G’={U,F}，其中U={A,B,C,D}, F = {{A,B}, {B,C}}，则G’是G的生成子图。
A: 正确
B: 错误
答案: 正确
13、判断题：
设图G = (V, E)，其中V = {A,B,C,D}, E = {{A,B},{A,C},{A,D},{B,C},{C,D}}, 图G’={U,F}，其中U={A,B,C}, F = {{A,B}, {B,C}}，则G’是G的导出子图。
A: 正确
B: 错误
答案: 错误
14、判断题：
设图G = (V, E)，其中V = {A,B,C}, E = {{A,B},{A,C}}, 图G’={U,F}，其中U={D,E,F}, F = {{D,F}, {F,E}}，则图G和图G’同构。
A: 正确
B: 错误
答案: 正确
15、判断题：
设图G = (V, E)，其中V = {A,B,C}, E = {{A,B},{A,C}}, 图G’={U,F}，其中U={D,E,F}, F = {{D,E}, {E,F},{F,D}}，则图G和图G’同构。
A: 正确
B: 错误
答案: 错误
第2讲 连通图、补图、偶图
第2讲测验
1、单选题：
在
的生成子图中有多少个互不同构的连通图？
A: 5
B: 6
C: 7
D: 8
答案: 6
2、单选题：
一个非连通图有66条边，那么它至少有多少个顶点？
A: 11
B: 12
C: 13
D: 14
答案: 13
3、单选题：
下列关于无向连通图特性的叙述中，正确的是？I. 所有顶点的度之和为偶数II. 边数大于顶点个数III. 至少有一个顶点的度为1
A: 只有I
B: 只有II
C: 只有III
D: I和II
答案: 只有I
4、判断题：
设图G的顶点数为p, 
,则图G中至少有两个顶点有相同的度。
A: 正确
B: 错误
答案: 正确
5、判断题：
正方体的各个顶点和边构成的图为双图。
A: 正确
B: 错误
答案: 正确
6、判断题：
图G中存在包含顶点x和y的闭通道，则图G中一定存在包含顶点x和y的闭迹。
A: 正确
B: 错误
答案: 错误
7、判断题：
图G中存在包含顶点x和y的闭迹，则图G中一定存在包含顶点x和y的圈。
A: 正确
B: 错误
答案: 错误
8、判断题：
设图G与图G‘同构，则图G中连通分量的个数与图G’中连通分量的个数相同。
A: 正确
B: 错误
答案: 正确
9、判断题：
设图G与图G’同构，图G中有一个长度为k的圈，则图G’中有一个长度为k的圈。
A: 正确
B: 错误
答案: 正确
10、判断题：
正五边形的5个顶点和5条边所构成的图为自补图。
A: 正确
B: 错误
答案: 正确
11、判断题：
若图G不是连通图，则G的补图一定是连通图。
A: 正确
B: 错误
答案: 正确
12、判断题：
若G是连通图，则图G的补图一定不是连通图。
A: 正确
B: 错误
答案: 错误
13、判断题：
存在一个自补图，其顶点个数为7。
A: 正确
B: 错误
答案: 错误
14、判断题：
存在一个自补图，其顶点个数为6。
A: 正确
B: 错误
答案: 错误
15、判断题：
设图G=(V,E)，其中V={A,B,C,D},E= {{A,B},{B,C},{C,D}}，则图G为自补图。
A: 正确
B: 错误
答案: 正确
第3讲 欧拉图
第3讲测验
1、单选题：
以下4个图中，哪一个存在欧拉闭迹？
A: 
B: 
C: 
D: 
答案:
2、单选题：
以下4个图中，哪一个存在欧拉开迹？
A: 
B: 
C: 
D: 
答案:
3、单选题：
以下4个图中，哪一个不能一笔画成？
A: 
B: 
C: 
D: 
答案:
4、单选题：
以下4个图中，哪一个至少需要两笔才能画成？
A: 
B: 
C: 
D: 
答案:
5、单选题：
以下4个图中，哪一个至少需要三笔才能画成？
A: 
B: 
C: 
D: 
答案:
6、判断题：
K4存在欧拉闭迹。
A: 正确
B: 错误
答案: 错误
7、判断题：
K5存在欧拉闭迹。
A: 正确
B: 错误
答案: 正确
8、判断题：
K4,4存在欧拉闭迹。
A: 正确
B: 错误
答案: 正确
9、判断题：
K5.5存在欧拉闭迹。
A: 正确
B: 错误
答案: 错误
10、判断题：
K3,3至少需要三笔画成。
A: 正确
B: 错误
答案: 正确
第4讲 哈密顿图
第４讲测验
1、单选题：
具有p（p>=3）个结点的非哈密顿图的边数最多有多少条？
A: (p-1)(p-2)/2
B: (p-1)(p-2)/2+1
C: p(p-1)/2-p
D: p(p-1)/2-(p-3)
答案: (p-1)(p-2)/2+1
2、单选题：
以下4个图中，哪个有哈密顿圈？
A: 
B: 
C: 
D: 
答案:
3、单选题：
以下4个图中，哪个没有哈密顿路？
A: 
B: 
C: 
D: 