图论初赛知识点
Description
1. 【NOIP2019 提高组】8. G 是一个非连通无向图（没有重边和自环），共有 28 条边，则该图至少有（）个顶点
A. 10
B. 9
C. 11
D. 8
B. 9
C. 11
D. 8
2. 【NOIP2019 提高组】12.以下哪个结构可以用来存储图（ ）
A. 栈
B. 二叉树
C. 队列
D. 邻接矩阵
B. 二叉树
C. 队列
D. 邻接矩阵
3. 【NOIP2017 普及组】10. 设 G 是有 n 个结点、m 条边（n ≤ m）的连通图，必须删去 G 的（ ）条边，才能使得 G 变成一棵树。
A. m – n + 1
B. m - n
C. m + n + 1
D. n – m + 1
B. m - n
C. m + n + 1
D. n – m + 1
4. 【NOIP2015 普及组】15.设简单无向图 G 有 16 条边且每个顶点的度数都是 2，则图 G 有（ ）个顶点。
A. 10
B. 12
C. 8
D. 16
B. 12
C. 8
D. 16
5. 在一个无向图中，所有顶点的度数之和等于所有边数的（ ）倍。
A. 1/2
B. 1
C. 2
D. 4
B. 1
C. 2
D. 4
6. 含 n 个顶点的连通图中的任意一条简单路径，其长度不可能超过（ ）。
A. 1
B. n/2
C. n-1
D. n
B. n/2
C. n-1
D. n
7. 对于一个具有 n 个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是（ ）。
A. n
B. (n-1)²
C. n-1
D. n²
B. (n-1)²
C. n-1
D. n²
8. 图的生成树（ ），n 个顶点的生成树有（ ）条边。
A. 唯一性不能确定 、n-1
B. 不唯一、任意
C. 唯一性不能确定、n
D. 无解
B. 不唯一、任意
C. 唯一性不能确定、n
D. 无解
9. G 是一个非连通无向图，共有 28 条边，则该图至少有（ ）个顶点。
A. 6
B. 7
C. 8
D. 9
B. 7
C. 8
D. 9
10. 最小生成树指的是（ ）。
A. 由连通网所得到的边数最少的生成树
B. 由连通网所得到的顶点数相对较少的生成树
C. 连通网中所有生成树中权值之和为最小的生成树
D. 连通网的极小连通子图
B. 由连通网所得到的顶点数相对较少的生成树
C. 连通网中所有生成树中权值之和为最小的生成树
D. 连通网的极小连通子图
11. 某无向图的邻接矩阵
，但根据邻接矩阵的性质，可以判断该图共有（ ）个顶
点。
A. 3
B. 6
C. 9
D. 以上答案均不正确
B. 6
C. 9
D. 以上答案均不正确
12. 在一个具有 n 个顶点的有向完全图中包含有（ ）条边。
A. n(n-1)/2
B. n(n-1)
C. n(n+1)/2
D. n²
B. n(n-1)
C. n(n+1)/2
D. n²
13. 在一个图中，所有顶点的度数之和等于所有边数的倍。（ ）
A. 1/2
B. 1
C. 2
D. 4
B. 1
C. 2
D. 4
14. 具有 4 个顶点的无向完全图有（ ）条边。
A. 6
B. 12
C. 16
D. 20
B. 12
C. 16
D. 20
15. 具有 6 个顶点的无向图至少应有（ ）条边才能确保是一个连通图。
A. 5
B. 6
C. 7
D. 8
B. 6
C. 7
D. 8
16. n 个结点的完全有向图含有边的数目（ ）。
A. n*n
B. n(n+1)
C. n/2
D. n(n-1)
B. n(n+1)
C. n/2
D. n(n-1)
17. 有向图中一个顶点的度是该顶点的（ ）。
A. 入度
B. 出度
C. 入度与出度之和
D. (入度+出度)/2
B. 出度
C. 入度与出度之和
D. (入度+出度)/2
18. 在含 n 个顶点和 e 条边的无向图的邻接矩阵中，零元素的个数为（ ）
A. e
B. 2e
C. n²-e
D. n²-2e
B. 2e
C. n²-e
D. n²-2e
19. 在无向图中，所有顶点的度数之和等于（ ）。
A. 图的边数
B. 图的边数的两倍
C. 图的顶点数
D. 图的顶点数的两倍
B. 图的边数的两倍
C. 图的顶点数
D. 图的顶点数的两倍
20. 假设有一个包含 n 个顶点的无向图，且该图是欧拉图。以下关于该图的描述中哪一项不一定正确？
A. 所有顶点的度数均为偶数
B. 该图连通
C. 该图存在一个欧拉回路
D. 该图的边数是奇数
B. 该图连通
C. 该图存在一个欧拉回路
D. 该图的边数是奇数
Source
初赛 图论相关
在下列比赛中: