判断题
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个顶点，那么如果任意两个顶点之间都有边的话，该图就称为完全图。
无向完全图的边数为：N*(N-1)/2。
2.连通图（一般都是指无向图）：
从顶点v到w有路径，就称顶点v和m连通。（路径是由顶点和相邻顶点序偶构成的边所形成的序列，其实就是一堆相连的顶点及其边）
如果图中任意俩顶点都连通，则该图为连通图。
3.连通分量：
与连通图对应，一般书上说的都是特指无向图！！
极大连通子图是无向图的连通分量。（暗指极大连通子图也指无向图！！）
4.极大连通分量：
极大是要求该连通子图包含其所有的边（暗指无向图）
5.极小连通分量：
极小是在保持连通的情况下使边数最少的子图（暗指无向图）
6.强连通图（特指有向图）：
在有向图中，若从顶点v到m有路径，则称这俩顶点时强连通的。若任意一对顶点都是强连通的，称此图为强连通图。
和无向图其实一毛一样，就换个名字以便和无向图区分。
7.强连通分量：
有向图中的极大强连通子图称为有向图的强连通分量。
8.极大强连通分量：
这里的极大和无向图完全一致
9.极小强连通分量：
这里的极小和无向图完全一致
10.生成树：
连通图的生成树是包含图中全部顶点的一个极小连通子图
11.生成森林：
在非连通图中，连通分量的生成树构成了非连通图的生成森林。
9.如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则G一定有2个连通分量。
如上！
10.图的关键路径上任意活动的延期都会引起工期的延长。
T F
解释：
解析：
- 按着定义，AOE网中关键路径是从“源点”到“汇点”路径长度最长的路径。自然，关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少。
- 如果是工期缩短的话，那么关键路径会被另一条代替，但是这里是延长工期不是缩短，所以关键路径肯定是最长的那条
- 按照关键路径的定义，假如有多条关键路径，那么这些路径的各个的长度也应该一致，如果其中某一条关键路径的长度延长，则关键路径就会只是延长了的那条路径。