第1讲 图的基本概念第1讲测验1、具有3个顶点的互不同构的图多少个？
a、1
b、2
c、3
d、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、若供选择答案中的数值表示一个图中各个顶点的度，能画出图的是哪个？
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
4、关于图的同构，下列说法不正确的是（）。
a、设图g和图g'同构，图g中包含一个子图为顶点数为n的完全图，则图g'中一定包含一个子图为顶点数为n的完全图。
b、设图g和图g'同构，则图g和图g'的顶点数相同。
c、设图g和图g'同构，则图g和图g'的边数相同。
d、所有包含6个顶点的3次正则图互相同构。
5、有相同的顶点数和边数的两个图同构。
6、具有两个顶点的互不同构的图有2个。
7、存在一个包含5个顶点的图，其各个顶点的度依次为4，4，3，2，2。
8、存在一个包含5个顶点的图，其各个顶点的度依次为4，4，4，2，2。
9、设图g = (v, e)，其中v = {a,b,c,d}, e = {{a,b},{a,c},{a,d},{b,c},{c,d}},则g是一个3次正则图。
10、设图g = (v, e)，其中v = {a,b,c,d}, e = {{a,b},{a,c},{a,d},{b,c},{c,d}},则g是一个完全图。
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的子图。
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的生成子图。
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的导出子图。
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'同构。
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'同构。
第2讲 连通图、补图、偶图第2讲测验1、在的生成子图中有多少个互不同构的连通图？
a、5
b、6
c、7
d、8
2、一个非连通图有66条边，那么它至少有多少个顶点？
a、11
b、12
c、13
d、14
3、下列关于无向连通图特性的叙述中，正确的是？ i. 所有顶点的度之和为偶数 ii. 边数大于顶点个数 iii. 至少有一个顶点的度为1
a、只有i
b、只有ii
c、只有iii
d、i和ii
4、设图g的顶点数为p, ,则图g中至少有两个顶点有相同的度。
5、正方体的各个顶点和边构成的图为双图。
6、图g中存在包含顶点x和y的闭通道，则图g中一定存在包含顶点x和y的闭迹。
7、图g中存在包含顶点x和y的闭迹，则图g中一定存在包含顶点x和y的圈。
8、设图g与图g‘同构，则图g中连通分量的个数与图g'中连通分量的个数相同。
9、设图g与图g'同构，图g中有一个长度为k的圈，则图g'中有一个长度为k的圈。
10、正五边形的5个顶点和5条边所构成的图为自补图。
11、若图g不是连通图，则g的补图一定是连通图。
12、若g是连通图，则图g的补图一定不是连通图。
13、存在一个自补图，其顶点个数为7。
14、存在一个自补图，其顶点个数为6。
15、设图g=(v,e)，其中v={a,b,c,d},e= {{a,b},{b,c},{c,d}}，则图g为自补图。
第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存在欧拉闭迹。
7、k5存在欧拉闭迹。
8、k4,4存在欧拉闭迹。
9、k5.5存在欧拉闭迹。
10、k3,3至少需要三笔画成。
第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)
2、以下4个图中，哪个有哈密顿圈？
a、
b、
c、
d、
3、以下4个图中，哪个没有哈密顿路？
a、
b、
c、
d、
4、k4,6是哈密顿图。
5、ｋ3,3是哈密顿图。
6、k4,5是哈密顿图。
7、结点数大于等于３的哈密顿图中任意两个不相邻结点的度数之和大于等于结点数。
8、哈密顿图中每个结点的度都大于等于２。
9、图是哈密顿图。
10、图是哈密顿图。
11、图是哈密顿图。
12、图是哈密顿图。
13、图是哈密顿图。
14、图是哈密顿图。
15、图去掉任何一个顶点及其与之关联的边之后是哈密顿图。
第5讲 图的表示、带权图第5讲测验1、图g的邻接矩阵为，则图g的顶点的最小度为（）。
a、1
b、2
c、3
d、4
2、图g的邻接矩阵为，则图g的顶点的最大度为（）。
a、1
b、2
c、3
d、4
3、图g的邻接矩阵为,则图g有几个连通分量？
a、1
b、2
c、3
d、4
4、图g的邻接矩阵为,图f的邻接矩阵为,则图g与图f同构。
5、图g的邻接矩阵为，图f的邻接矩阵为,则图g与图f同构。
6、图g的邻接矩阵为，图f的邻接矩阵为，则图g与图f同构。
7、图g的关联矩阵为，图f的关联矩阵为，则图g与图f同构。
8、图g的关联矩阵为，图f的关联矩阵为，则图g与图f同构。
9、图g的邻接矩阵为,则图g为偶图。
10、图g的邻接矩阵为，则图g为偶图。
11、图g的邻接矩阵为，则图g为偶图。
12、图g的邻接矩阵为，则图g为欧拉图。
13、图g的邻接矩阵为，则图g为哈密顿图。
14、图g的邻接矩阵为,则图g有两个连通分量。
15、图g的邻接矩阵为，则图g有两个连通分量。
第6讲 树、割集第6讲测验1、连通图g是一棵树，当且仅当g中（）。
a、有些边不是割边
b、每条边都是割边
c、无割边集
d、每条边都不是割边
2、包含3个结点的互不同构的树有（）棵。
a、1
b、2
c、3
d、4
3、下列图为树的是（）。
a、
b、
c、
d、
4、下列图为森林的是（）。
a、
b、
c、
d、
5、任何一棵树至少含有两个度为1的结点。
6、任何一棵含有p个结点的树至多含有p-1个度为1的结点。
7、一棵非平凡树t有个度为2的顶点，个度为3的顶点，...，个度为k的顶点，则t有个度为1的顶点。
8、有割点的连通图一定不是欧拉图。
9、有割边的连通图一定不是欧拉图。
10、有割点的连通图一定不是哈密顿图。
11、有割边的连通图一定不是哈密顿图。
12、设v是图g的一个割点，则v一定不是g的补图的割点。
13、设g中含有p个顶点和q条边，如果q=p-1，则g是树。
14、设g中含有p个顶点和q条边，如果g连通且q=p-1，则g是树。
15、设g中含有p个顶点和q条边，如果g中没有圈且q=p-1，则g是树。
第7讲 图的连通度第7讲测验1、图的顶点连通度为（）。
a、1
b、2
c、3
d、4
2、图的边连通度为（）。
a、1
b、2
c、3
d、4
3、关于图，下列说法错误的是（）。
a、它是1顶点连通的。
b、它是2顶点连通的。
c、它是3顶点连通的。
d、它是4顶点连通的。
4、关于图，下列说法错误的是（）。
a、它是1边连通的。
b、它是2边连通的。
c、它是3边连通的。
d、它是4边连通的。
5、关于图，下列说法错误的是（）。
a、它1顶点连通的。
b、它是2顶点连通的。
c、它是3顶点连通的。
d、它是4顶点连通的。
6、关于图，下列说法错误的是（）。
a、它是2边连通的。
b、它是3边连通的。
c、它是4边连通的。
d、它是5边连通的。
7、图的顶点连通度为（）。
a、1
b、2
c、3
d、4
8、图的边连通度为（）。
a、1
b、2
c、3
d、4
9、图的顶点连通度为（）。
a、1
b、2
c、3
d、4
10、图的边连通度为（）。
a、1
b、2
c、3
d、4
11、关于图，下列说法错误的是（）。
a、它是1顶点连通的。
b、它是2顶点连通的。
c、它是3顶点连通的。
d、它4顶点连通的。
12、关于图，下列说法错误的是（）。
a、它是1边连通的。
b、它是2边连通的。
c、它是3边连通的。
d、它是4边连通的。
13、图中顶点的最小度为5。
14、图的顶点连通度为3。
15、图的边连通度为4。
第8讲 匹配问题第8讲测验1、设集合x={1,2,...,50},则{1,2},{2,3},{3,4},...,{49,50},{50}有（）个相异代表系。
a、1
b、2
c、3
d、4
2、设集合x={1,2,3,4,5,6},则{1,2},{2,3},{3,4},{4,5},{5,6},{6,1}有（）个相异代表系。
a、1
b、2
c、3
d、4
3、设集合x={1,2,3,4,5},则{1},{2,3},{1,2},{1,3},{1,4,5}有相异代表系。
4、设集合x={1,2,3,4,5},则{1,2},{2,3},{4,5},{4,5}有相异代表系。
5、设集合x={1,2,3,4,5},则{1,3},{2,3},{1,2},{3}有相异代表系。
6、设集合x={1,2,3,4,5},则{1,3,4},{1,4,5},{2,3,5},{2,4,5}有相异代表系。
第9讲 平面图第9讲测验1、下列说法正确的是（）。
a、k2,2是可平面图。
b、k3,3是可平面图。
c、k4,4是可平面图。
d、k5,5是可平面图。
2、下列说法正确的是（）。
a、k4是可平面图。
b、k5是可平面图。
c、k6是可平面图。
d、k7是可平面图。
3、图是可平面图。
4、图是可平面图。
5、图是可平面图。
6、图是可平面图。
第10讲 图的顶点着色问题第10讲测验1、图的色数是（）。
a、1
b、2
c、3
d、4
2、图的色数是（）。
a、1
b、2
c、3
d、4
3、图的色数是（）。
a、1
b、2
c、3
d、4
4、图的色数是（）。
a、1
b、2
c、3
d、4
5、图的色数为（）。
a、1
b、2
c、3
d、4
6、图的色数是（）。
a、1
b、2
c、3
d、4
7、图的色数是（）。
a、1
b、2
c、3
d、4
8、为地图着色，使得有公共边界的区域着以不同的颜色，至少需要（）中不同的颜色。
a、1
b、2
c、3
d、4
9、设图g=（v，e)，其中v={a,b,c,d,e,f,g},e={{a,b},{a,c},{b,c},{b,d},{b,e},{c,d},{c,f},{d,e},{d,f},{e,g},{e,f},{f,g}}，则图g的色数为（）。
a、1
b、2
c、3
d、4
10、设图g=（v，e)，其中v={a,b,c,d,e,f,g},e={{a,b},{a,c},{b,c},{b,d},{b,e},{c,d},{c,f},{d,e},{d,f},{e,g},{e,f},{f,g},{a,g}}，则图g的色数为（）。
a、1
b、2
c、3
d、4
11、同构的图具有相同的色数。
12、完全图的色数为p。
13、设图g有p个顶点，如果图g的色数为p，则图g为完全图。
14、如果图g为圈，则图g的色数为2。
15、设g是一个有p个顶点的d-正则图，则。
第11讲 有向图的基本概念第11讲测验1、具有三个顶点的所有互不同构的有向图有（）个。
a、14
b、15
c、16
d、17
2、有向图d=(v,a)，其中v={1,2,3,4,5,6},a={(1,2),(2,4),(2,5),(4,1),(4,5),(5,4),(6,3)},则d有（）个强连通分量。
a、1
b、2
c、3
d、4
3、有向图d=(v,a)，其中v={1,2,3,4,5,6},a={(1,2),(2,4),(2,5),(4,1),(4,5),(5,4),(6,3)},则d中顶点2的出度为（）。
a、1
b、2
c、3
d、4
4、有向图d=(v,a)，其中v={1,2,3,4,5,6},a={(1,2),(2,4),(2,5),(4,1),(4,5),(5,4),(6,3)},则d中顶点2的入度为（）。
a、1
b、2
c、3
d、4
5、有向图d=(v,a)，其中v={1,2,3,4,5,6},a={(1,2),(2,4),(2,5),(4,1),(4,5),(5,4),(6,3)},则d中顶点2的度为（）。
a、1
b、2
c、3
d、4
6、具有p个顶点的完全有向图具有p(p-1)条弧。
7、有向图d是单向连通的当且仅当d有一条生成通道。
8、每个竞赛图都有哈密顿路。
9、设有向图d的每个顶点的出度至少为1，则有向图d中有一个有向圈。
10、有向图d有p个顶点，其邻接矩阵存储于二维数组中，则顶点i的入度为。
11、有向图d有p个顶点，其邻接矩阵存储于二维数组中，则顶点i的出度为。
12、有向图d有p个顶点，其邻接矩阵存储于二维数组中，则顶点i的度为。
13、任一有向图中，度为奇数的结点有偶数个。
14、有向图d=(v,a)，其中v={1,2,3,4,5},a={(1,2),(1,5),(2,3),(2,5),(3,4),(4,1),(4,5),(5,3)},则d可用邻接矩阵表示。
15、有向图d=(v,a)，其中v={1,2,3,4,5},a={(1,2),(1,5),(2,3),(2,5),(3,4),(4,1),(4,5),(5,3)},则从结点2到结点5长度为4的有向通道有1条。
第12讲 有根树、有序树、比赛图第12讲测验1、由3个结点所构成的二叉树有（）种不同的形态。
a、2
b、3
c、4
d、5
2、具有3个顶点的互不同构的有根树有（）个。
a、2
b、3
c、4
d、5
3、一个有向图是有向树，当且仅当该有向图
a、没有有向圈。
b、忽略边的方向后，是连通且没有圈的无向图。
c、有一个结点可以到达任何其余结点。
d、所有结点的出度之和等于入度之和。
4、设t是一个有个叶子的二元树，出度为2的顶点为,则。
5、设t是一个正则m元树，它有i个内顶点（出度为m),如果e为所有内顶点深度之和，i为所有叶顶点深度之和，则i=(m-1)e mi。
6、如果一个有序树的每个內结点至多有两个孩子结点，则该有序树为二叉树。
期末考试期末考试1、设g是平面连通图，有9个顶点，12条边，则g有（）个面。
a、5
b、6
c、7
d、8
2、设g是有7个顶点的完全图，则从g中删去（）条边，可以得到树。
a、13
b、14
c、15
d、16
3、k6的色数为（）。
a、4
b、5
c、6
d、7
4、设d=（v,a)为有向图，其中v={(1,2),(1,4),(2,3),(2,4),(3,4),(3,5),(4,1),(5,6)}，则d有（）个强连通分量。
a、1
b、2
c、3
d、4
5、图的边连通度为（）。
a、1
b、2
c、3
d、4
6、设无向图g有18条边且每个顶点的度数都是3，则图g有（）个顶点。
a、9
b、10
c、11
d、12
7、图的边连通度为（）。
a、1
b、2
c、3
d、4
8、下面四组数中能构成无向图的度数序列的是（）。
a、2，3，4，5，6，7
b、1，2，2，3，4
c、2，1，1，1，2
d、3，3，5，6，0
9、设g=(v,e)为图，其中v={1,2,3,4,5}，e={{1,3},{1,4},{2,5},{3,4}}，则g有（）个连通分量。
a、1
b、2
c、3
d、4
10、k6是欧拉图。
11、如果一棵树的结点数大于等于2，则该树为偶图。
12、至少有两个顶点的图有两个相同度数的顶点。
13、不可能有偶数个顶点，奇数条边的欧拉图。
14、图是偶图。
15、图是2-边连通的。
16、图是哈密顿图。
17、图是可平面图。
18、图的色数为2。
19、若图g中只有两个奇数度顶点，则这两个顶点之间一定存在一条路。
20、图g的邻接矩阵为,则图g是可平面的。
猜你喜欢
- 2022-12-05 21:31
- 2022-12-05 21:25
- 2022-12-05 21:25
- 2022-12-05 21:14
- 2022-12-05 20:47
- 2022-12-05 20:43
- 2022-12-05 20:39
- 2022-12-05 19:43
- 2022-12-05 19:34
- 2022-12-05 19:22