判断题

1.在n个结点的无向图中，若边数大于n-1,则该图必是连通图。

​ T F

解释：

以下两种说法是对的：

• 在n个结点的无向图中，若该图是连通图,则其边数大于等于n-1，

• 在n个结点的无向图中，若边数大于(n-2)(n-1)/2，则该图必是连通图
  就是说连通是比较强的条件

2.用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。

​ T F

解释：

• 如果不考虑邻接矩阵的压缩存储****，则只与图的节点数目有关，若对邻接矩阵进行压缩存储，则和节点数和边数都有关

3.无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。

​ T F

解释：

• 无向图的邻接矩阵一定是对称的，而有向图的邻接矩阵不一定对称。
  因为如果一个点i到j有边，则aij=aji=1；所以都是对称的。
  但是有向图就不一定了，点i 到 j 有边，aij=1，但j到i不一定有边，则aji不一定等于1。
• 有向图用邻接矩阵更加节省存储空间。
  因为无向图的邻接矩阵是对称的，所以也就是多用了一些存储空间。

4.邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。

​ T F

解释：

• 邻接矩阵存储带权图时，若Vi-Vj存在路径，则在矩阵中的(i,j)位置写入权值即可。

5.下列关于最小生成树的说法中，正确的是（）。

Ⅰ．最小生成树的代价唯一
Ⅱ．所有权值最小的边一定会出现在所有的最小生成树中
Ⅲ．使用普里姆（ Prim）算法从不同顶点开始得到的最小生成树一定相同
Ⅳ．使用普里姆算法和克鲁斯卡尔（ Kruskal）算法得到的最小生成树总不相同

​ A. 仅Ⅰ
​ B. 仅Ⅱ
​ C. 仅Ⅰ、 Ⅲ
​ D. 仅Ⅱ、 Ⅳ

解释：

A、既然是最小生成树，那么代价一定是唯一确定的最小值，但是树形可能不一样
B、设想所有边权值都相同，那么当边数>顶点数-1时，自然有某些边不会出现在最小生成树里
C、情况如B
D、不一定，情况如B

任何一个带权的无向连通图的最小生成树可能有多棵。：

• 对于连通图而言从图中不同顶点出发或从同一顶点****出发按照不同的优先搜索过程可以得到不同的生成树。

• 树是e=v-1边数最少的无向连通图，故必有树（至少一棵）。

• 也****可以有多棵最小生成树，例如图(i-j k :点i到j间有边且权为k)：
  1-2 1
  2-3 1
  1-3 1
  选边1-2，2-3是边权和为2的最小生成树；
  选边1-3，2-3也是边权和为2的最小生成树。
  **所以任何一个带权的无向连通图的最小生成树可能有多棵

6.连通图上各边权值均不相同，则该图的最小生成树是唯一的。

​ T F

解释：

• 如果各边权值不同，在生成树时，每次连接新结点的选择就唯一，因此最小生成树唯一

7.关于图的遍历图的广度优先遍历相当于二叉树的层次遍历。

​ T F

8.如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则G中一定有回路。

​ T F

解释：

• 如果不存在回路，那么这个无向图g就是一个森林（由多个不相交的树组成），而每一次广度优先搜索只能访问一棵树，因此需要进行两次广度优先搜索才能访问所有顶点。
• G肯定不是完全图，也一定不是连通图（如上述而言），有两个连通分量（如上述）。

引出知识点：

可以看该博客：这次一定弄懂完全图、连通图、连通分量、强连通图、强连通分量、极大连通分量、极小联通分量、生成树、生成森林的区别-CSDN博客

1.完全图：

也称简单完全图。假设一个图有n个顶点，那么如果任意两个顶点之间都有边的话，该图就称为完全图。

2.连通图（一般都是指无向图）：

从顶点v到w有路径，就称顶点v和m连通。（路径是由顶点和相邻顶点序偶构成的边所形成的序列，其实就是一堆相连的顶点及其边）
如果图中任意俩顶点都连通，则该图为连通图。

3.连通分量：

与连通图对应，一般书上说的都是特指无向图！！
极大连通子图是无向图的连通分量。（暗指极大连通子图也指无向图！！）

4.极大连通分量：

极大是要求该连通子图包含其所有的边（暗指无向图）

5.极小连通分量：

极小是在保持连通的情况下使边数最少的子图（暗指无向图）

6.强连通图（特指有向图）：

在有向图中，若从顶点v到m有路径，则称这俩顶点时强连通的。若任意一对顶点都是强连通的，称此图为强连通图。
和无向图其实一毛一样，就换个名字以便和无向图区分。

7.强连通分量：

有向图中的极大强连通子图称为有向图的强连通分量。

8.极大强连通分量：

这里的极大和无向图完全一致

9.极小强连通分量：

这里的极小和无向图完全一致

10.生成树：

连通图的生成树是包含图中全部顶点的一个极小连通子图
11.生成森林：

在非连通图中，连通分量的生成树构成了非连通图的生成森林。

9.如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则G一定有2个连通分量。

​ 如上！

10.图的关键路径上任意活动的延期都会引起工期的延长。

​ T F

解释：

解析：

• 按着定义，AOE网中关键路径是从“源点”到“汇点”路径长度最长的路径。自然，关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少。
• 如果是工期缩短的话，那么关键路径会被另一条代替，但是这里是延长工期不是缩短，所以关键路径肯定是最长的那条
• 按照关键路径的定义，假如有多条关键路径，那么这些路径的各个的长度也应该一致，如果其中某一条关键路径的长度延长，则关键路径就会只是延长了的那条路径。