课堂练习

1. 【NOIP2016】Lucia和她的朋友以及朋友的朋友都在某社交网站上注册了账号。下图是他们之间的关系图，两个人之间有边相连代表这两个人是朋友，没有边相连代表不是朋友。这个社交网站的规则为如果某人A向他（她）的朋友B分享了某张照片，那么B就可以对该照片进行评论；如果B评论了该照片，那么他（她）的所有朋友都可以看见这个评论以及被评论的照片，但是不能对该照片进行评论（除非A也向他（她）分享了该照片）。现在Lucia已经上传了一张照片，但是她不想让Jacob看见这张照片，那么她可以向以下朋友（）分享该照片。 A. Dana, Michael,Eve B. Dana,Eve,Monica C. Michael,Eve,Jacob D. Micheal, Peter, Monica 【答案】A 【分析】为使Jacob看不到照片，Lucia不可以向Jacob及他们共同的朋友Monica和Peter分享照片，就是找图中没有与Jacob连线的人。
2. 【NOIP2014】有向图中每个顶点的度等于该顶点的（）。 A.入度 B.出度 C.入度与出度之和 D.入度与出度之差 【答案】C 【分析】有向图中每个顶点的度分成两种，分别是入度和出度，所有的入度之和与所有的出度之和相等，对于一个顶点来说，该顶点的度等于该顶点的入度与出度之和。
3. 【NOIP2014】在无向图中，所有顶点的度数之和是边数的（）倍。 A.0.5 B.1 C.2 D.4 【答案】C 【分析】图论基础题，每条边都会使两个端点的度增加1，所以度数之和为点数两倍。
4. 【NOIP2016】设简单无向图G有16条边且每个顶点的度数都是2，则图G有（）个顶点。 A.10 B.12 C.8 D.16 【答案】D 【分析】考察图论基本知识。简单无向图中两个顶点之间最多有一条边，一个有16条边并且每个点都有两条边相连接（每个顶点的度数都是2），那么它应该是一个16个顶点首尾相接组成的环。
5. 【NOIP2010】关于拓扑排序，下面说法正确的是（ ） A.所有连通的有向图都可以实现拓扑排序 B.对一个图而言，拓扑排序的结果是唯一的 C.拓扑排序中入度为0的结点总会排在人度大于0的结点的前面 D.拓扑排序结果序列中的第一个结点一定是人度为0的点 【答案】D 【分析】A选项，当图中有环，必然无法拓扑排序；B选项，同一时刻，入度为0的点不唯一，拓扑排序也就不唯一；C选项，如下1-3-2也是正确的拓扑排序，但3却在2之前。
6. 【NOIP2008】设T是一棵有n个顶点的树，下列说法不正确的是（ ） A.T有n条边 B.T是连通的 C.T是无环的 D.T有 $n - 1$ 条边 【答案】A 【分析】n个顶点的树有且仅有 $n - 1$ 条边，而且连通无环，这些都是树的性质。
7. 【NOIP2017】设G是有n个结点、m条边 $(n ≤m)$ 的连通图，必须删去G的（ ）条边，才能使得G变成一棵树。 A. $m - n + 1$ B. $m - n$ C. $m + n + 1$ D. $n - m + 1$ 【答案】A 【分析】一棵树有 $n - 1$ 条边，故答案为 $m - (n - 1)=m - n + 1$ 。
8. 【NOIP2015】6个顶点的连通图的最小生成树，其边数为（ ）。 A.6 B.5 C.7 D.4 【答案】B 【分析】n个顶点的连通图的生成树的边数为 $n - 1$ 。
9. 【NOIP2014】设G是有6个结点的完全图，要得到一棵生成树，需要从G中删去（ ）条边。 A.6 B.9 C.10 D.15 【答案】C 【分析】完全图如下图所示，6个点的完全图有 $\frac{6 * 5}{2}=15$ 条边，而6个点的树有 $6 - 1 = 5$ 条边，因此需要删去 $15 - 5 = 10$ 条边。
10. 【NOIP2009】已知n个顶点的有向图，若该图是强连通的（从所有顶点都存在路径到达其他顶点），则该图中最少有（ ）条有向边。 A.n B. $n + 1$ C. $n - 1$ D. $n *(n - 1)$ 【答案】A 【分析】n个点首尾相接，构成环。
11. 【NOIP2011】无向完全图是图中每对顶点之间都恰有一条边的简单图。已知无向完全图G有7个顶点，则它共有（）条边。 A.7 B.21 C.42 D.49 【答案】B 【分析1】n个点的完全图有 $1 + 2 + \cdots + (n - 1)=\frac{(n - 1) * n}{2}$ 条边。当 $n = 7$ 时，带入公式得21。 【分析2】根据无向完全图的概念，可以知道每对顶点之间都恰有一条边，那么边的个数就是 $C(N, 2)$ 。当 $n = 7$ 时， $C(7, 2)=21$ 。
12. 【NOIP2011】对一个有向图而言，如果每个结点都存在到达其他任何结点的路径，那么就称它是强连通的。例如，下图就是一个强连通图。事实上，在删掉边（ ）后，它依然是强连通的。 A.a B.b C.c D.d 【答案】A 【分析】强联通是指在有向图中任意两点都可以互相到达，枚举四个选项根据定义判断一下即可。去掉边b后，左边的点到不了中间点；去掉边c后，下面的点到不了左边的点；去掉边d后，右边的点到不了下面的点。
13. 【NOIP2013】在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。下图是一个有4个顶点、6条边的连通图。若要使它不再是连通图，至少要删去其中的（ ）条边。 A.1 B.2 C.3 D.4 【答案】C 【分析】通过观察容易发现，只要切断3条边，就能孤立一个结点。同时不存在切断两条边就能使图不连通的情况，因此答案是3。
14. 【NOIP2013】在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。右图是一个有5个顶点、8条边的连通图。若要使它不再是连通图，至少要删去其中的（）条边。 A.2 B.3 C.4 D.5 【答案】B 【分析】通过观察容易发现，只要切断3条边，就能孤立一个结点。同时不存在切断两条边就能使图不连通的情况，因此答案是3。
15. 【NOIP2013】二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那么，12个顶点的二分图至多有（）条边。 A.18 B.24 C.36 D.66 【答案】C 【分析】二分图如下图所示，12个结点的二分图，假设一边有x个结点，另一边则有 $(12 - x)$ 个结点，因此最多有 $x(12 - x)$ 条边，当x取6时得到最大值为36。
16. 【NOIP2015】对图G中各个结点分别指定一种颜色，使相邻结点颜色不同，则称为图G的一个正常着色。正常着色图G所必需的最少颜色数，称为G的色数。那么下图的色数是（ ）。 A.3 B.4 C.5 D.6 【答案】A 【分析】手动染色。选取度数最多的点，开始染色，直接模拟，最终只要3种颜色即可。
17. 【NOIP2016】G是一个非连通简单无向图，共有28条边，则该图至少有（ ）个顶点。 A.10 B.9 C.8 D.7 【答案】B 【分析】8个顶点的简单无向图只有在为完全图的情况下才会有 $\frac{8 * 7}{2}=28$ 条边，但完全图不符合“非连通”的要求。存在9个顶点28条边的非连通简单无向图，例如1个孤立点和一个8个顶点的完全图。
18. 【NOIP2017】由四个不同的点构成的简单无向连通图的个数是（）。 A.32 B.35 C.38 D.41 【答案】C 【分析】4个不同点构成简单无向连通图，最多有 $C(4, 2)=4 *(4 - 1)/2 = 6$ 条边，最少有 $4 - 1 = 3$ 条边（树），但不是所有的任选3条边都满足条件，有一种情况是三个点形成一个三角形而孤立一个点，这种情况共有4种，比如A、B、C、D这4个点三条边分别连接A - B、B - C、C - A，而D孤立着，这样就不行，所以总个数为 $C_{6}^{3}-4 + C_{6}^{4}+ C_{6}^{5}+ C_{6}^{6}=38$ 。
19. 【NOIP2018】由四个没有区别的点构成的简单无向连通图的个数是（）。 A.6 B.7 C.8 D.9 【答案】A 【分析】考察图论基础知识。连通图指的是两个点之间都有路径可以到达，简单图是既不含平行边也不含自环的图，无向图指的是图中的边是无向边。枚举可得有6种由4个没有区别的点构成不同结构的简单无向连通图。 三条边的图有两个（长为3的路、星图）； 四条边的图有两个（图、三角形加一条边）； 五条边的图有一个（完全图挖掉一条边）； 六条边的图有一个（即4个点的完全图）。 综上，一共有6种。

课堂练习（续）

20. 【NOIP2013】以 $A_{0}$ 作为起点，对下面的无向图进行深度优先遍历时，遍历顺序不可能是（ ）。
    A. $A_{0}$ , $A_{1}$ , $A_{2}$ , $A_{3}$
    B. $A_{0}$ , $A_{1}$ , $A_{3}$ , $A_{2}$
    C. $A_{0}$ , $A_{2}$ , $A_{3}$ , $A_{1}$
    D. $A_{0}$ , $A_{3}$ , $A_{1}$ , $A_{2}$
    【答案】A
    【分析】从题中 $A_{0}$ 出发深度优先遍历，分析选项A：从 $A_{0}$ 到 $A_{1}$ 后，$A_{1}$ 的邻接点包括 $A_{3}$（而非 $A_{2}$），因此无法从 $A_{1}$ 直接到达 $A_{2}$，必须回溯到 $A_{0}$ 后再访问 $A_{2}$。所有可能的路径为 $(A_{0}, A_{1}, A_{3}, A_{2})$、$(A_{0}, A_{3}, A_{1}, A_{2})$、$(A_{0}, A_{2}, A_{1}, A_{3})$、$(A_{0}, A_{2}, A_{3}, A_{1})$，故A选项不可能。

21. 【NOIP2015】具有n个顶点，e条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为（ ）。
    A. $O(n^{2})$
    B. $O(e^{2})$
    C. $O(ne)$
    D. $O(n+e)$
    【答案】D
    【分析】用邻接表存储时，遍历每个顶点需 $O(n)$，遍历每条边需 $O(e)$，总时间复杂度为 $O(n+e)$。

22. 【NOIP2013】对一个n个顶点、m条边的带权有向简单图用Dijkstra算法计算单源最短路径时，如果不使用堆或其他优先队列进行优化，则其时间复杂度为（ ）。
    A. $O(mn+n^{3})$
    B. $O(n^{2})$
    C. $O((m+n)\log n)$
    D. $O((m+n^{2})\log n)$
    【答案】B
    【分析】未使用堆优化时，Dijkstra算法每次寻找当前最短路径顶点需 $O(n)$，共执行n次，总时间复杂度为 $O(n^{2})$。

23. 【NOIP2009】右图给出了一个加权无向图，从顶点 $V_{0}$ 开始用Prim算法求最小生成树，则依次加入最小生成树的顶点集合的顶点序列为（ ）。
    A. $V_{0}, V_{1}, V_{2}, V_{3}, V_{5}, V_{4}$
    B. $V_{0}, V_{1}, V_{5}, V_{4}, V_{3}, V_{2}$
    C. $V_{1}, V_{2}, V_{3}, V_{0}, V_{5}, V_{4}$
    D. $V_{1}, V_{2}, V_{3}, V_{0}, V_{4}, V_{5}$
    【答案】A
    【分析】Prim算法从 $V_{0}$ 开始，每次选择与已选顶点集合连边权值最小的顶点：

• 初始集合 $\{V_{0}\}$，最小边为 $V_{0}V_{1}$（权10），加入 $V_{1}$；
• 集合 $\{V_{0}, V_{1}\}$，最小边为 $V_{1}V_{2}$（权5），加入 $V_{2}$；
• 集合 $\{V_{0}, V_{1}, V_{2}\}$，最小边为 $V_{2}V_{3}$（权6），加入 $V_{3}$；
• 集合 $\{V_{0}, V_{1}, V_{2}, V_{3}\}$，最小边为 $V_{1}V_{5}$（权11），加入 $V_{5}$；
• 集合 $\{V_{0}, V_{1}, V_{2}, V_{3}, V_{5}\}$，最小边为 $V_{3}V_{4}$（权18），加入 $V_{4}$。

不定项选择题

1. 【NOIP2014】以下哪些结构可以用来存储图（ ）。
   A. 邻接矩阵
   B. 栈
   C. 邻接表
   D. 二叉树
   【答案】AC
   【分析】邻接矩阵和邻接表是存储图的两种基本结构，栈和二叉树无法直接存储图的边信息。

2. 【NOIP2009】若3个顶点的无权图G的邻接矩阵用数组存储为 $\{(0,1,1),(1,0,1),(0,1,0)\}$，假定顶点依次为 $v_{1}, v_{2}, v_{3}$，关于该图，下面的说法正确的是（ ）。
   A. 该图是有向图
   B. 该图是强连通的
   C. 该图所有顶点的入度之和等于出度之和
   D. 从 $v_{1}$ 开始的深度优先遍历所经过的顶点序列与广度优先的顶点序列是相同的
   【答案】ABD
   【分析】邻接矩阵非对称，为有向图；任意两点可达，是强连通图；有向图入度之和等于出度之和；深度优先和广度优先遍历序列均为 $v_{1}→v_{2}→v_{3}$。

3. 【NOIP2012】已知带权有向图G上的所有权值均为正整数，顶点 $u$ 到顶点 $v$ 的最短路径权值为 $d(u, v)$。若 $v_{1}, v_{2}, v_{3}, v_{4}, v_{5}$ 两两可达，则以下说法正确的有（ ）。
   A. $v_{1}$ 到 $v_{2}$ 的最短路径可能包含环
   B. $d(v_{1}, v_{2}) = d(v_{2}, v_{1})$
   C. $d(v_{1}, v_{3}) \leq d(v_{1}, v_{2}) + d(v_{2}, v_{3})$
   D. 若 $v_{1}→v_{2}→v_{3}→v_{4}→v_{5}$ 是 $v_{1}$ 到 $v_{5}$ 的最短路径，则 $v_{2}→v_{3}→v_{4}$ 是 $v_{2}$ 到 $v_{4}$ 的最短路径
   【答案】CD
   【分析】最短路径不能包含环（权值为正），A错误；有向图中 $d(v_{1}, v_{2})$ 与 $d(v_{2}, v_{1})$ 不一定相等，B错误；C符合三角不等式，D正确（最短路径的子路径必为最短路径）。

4. 【NOIP2015】以下图中一定可以进行黑白染色的有（ ）。
   A. 二分图
   B. 完全图
   C. 树
   D. 连通图
   【答案】AC
   【分析】二分图和树均不含奇环，可以黑白染色（相邻顶点颜色不同）；完全图（如 $K_3$）含奇环，无法黑白染色；连通图可能含奇环，不一定可行。

5. 【NOIP2018】下列关于最短路算法的说法，正确的是（ ）。
   A. 图中存在负权边但无负权回路时，Dijkstra算法不一定能求出所有点的最短路
   B. 图中无负权边时，多次调用Dijkstra算法能求出每对顶点间最短路径
   C. 图中存在负权回路时，Dijkstra算法无法求出源点到所有点的最短路
   D. 图中无负权边时，一次Dijkstra算法不能求出每对顶点间最短路
   【答案】ABD
   【分析】Dijkstra算法不支持负权边，A正确；无负权边时，多次调用Dijkstra（以每个点为源点）可求每对最短路径，B正确；负权回路存在时，最短路不存在，C正确；一次Dijkstra只能求单源最短路径，D正确。

6. 【NOIP2011】对下图使用Dijkstra算法计算S点到其余各点的最短路径长度时，到B点的距离 $d[B]$ 初始时赋为8，在算法执行过程中还会出现的值有（ ）。
   A. 3
   B. 7
   C. 6
   D. 5
   【答案】BCD
   【分析】初始 $d[B]=8$，首次选中A点（$d[A]=2$），更新 $d[B]=2+5=7$；选中D点（$d[D]=3$），更新 $d[B]=3+3=6$；选中C点（$d[C]=4$），更新 $d[B]=4+1=5$，故B、C、D正确。