图论题解与解析

【单选题】以下说法错误的是（ A ）。

解析：

• A、邻接表法只能用于有向图的存储，而邻接矩阵法对于有向图和无向图的存储都适用。

  这是错误的。实际上，邻接表法可以用于存储有向图和无向图。在无向图中，每条边在邻接表中会在两个顶点的列表中各出现一次。因此，选项A的描述是错误的。

• B、存储无向图的邻接矩阵是对称的，因此也可以只要存储邻接矩阵的下（或上）三角部分。

  这是正确的。由于无向图的邻接矩阵是对称的，只需存储下三角或上三角部分即可节省存储空间。

• C、用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。

  这是正确的。邻接矩阵的大小是固定的 $n \times n$（其中 $n$ 是节点数），与边的数量无关。

• D、连通图的生成树，是该连通图的一个极小连通子图。

  这是正确的。生成树是连通图的一个极小连通子图，且包含所有顶点且没有环。

【判断题】

1. 带权无向图的最小生成树是唯一的。

   错误。 最小生成树的唯一性取决于图中边的权重是否唯一。如果存在多条边具有相同的权重，可能会有多个最小生成树。

2. 图的连通分量是无向图的极小连通子图。

   错误。 连通分量是图中极大连通子图，而不是极小的。极小连通子图通常指的是生成树。

3. 邻接表只能用于存储有向图，而邻接矩阵则可存储有向图和无向图。

   错误。 邻接表同样可以用于存储无向图。

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

   错误。 边数大于 $n-1$ 并不保证图的连通性。例如，可以有多个连通分量，每个分量内部的边数满足条件，但整体图仍然不连通。

5. 任何无向图都存在生成树。

   错误。 只有连通的无向图才存在生成树。对于非连通图，只能存在生成森林。

6. 一个网（带权图）都有唯一的最小生成树。

   错误。 当图中存在多条边权相同的情况下，可能存在多个最小生成树。

总结：

• 单选题答案：A
• 判断题：
  1. 错误
  2. 错误
  3. 错误
  4. 错误
  5. 错误
  6. 错误