🏷️ 知识点：生成树

对于一个有 n 个顶点的图：若是连通无向图，其边的个数至少为（ ）；若是强连通有向图，则其边的个数至少为（ ）。

A. n−1，n B. n−1，n(n−1) C. n，n D. n，n(n−1)

[tag_link]

正确答案：A

结论

连通无向图最少有 n−1 条边，强连通有向图最少有 n 条边。

推导

无向图取一棵生成树即可连通 n 个顶点，树恰有 n−1 条边。有向图要让每个顶点可沿方向回到其他顶点，最少可用包含全部顶点的有向环，每个顶点一条出边和一条入边，共 n 条边。

易错点

不要把有向图的“强连通”误当作无向连通；n−1 条有向边至多形成有向路径，不能让所有顶点互相可达。

设 G=(V,E)，G’=(V’,E’) 是 G 的一棵生成树。下列说法中错误的是（ ）。

I. G’ 是 G 的连通分量 II. G’ 是 G 的无环子图 III. G’ 是 G 的极小连通子图，且 V’=V

A. I、II B. 仅 III C. II、III D. 仅 I

[tag_link]

正确答案：D

结论

错误的只有 I，答案为 D。

推导

生成树覆盖原图全部顶点（V’=V），是连通子图且含 n−1 条边，因此无环，并且删除任意一条边都会失去连通性，所以是极小连通子图。连通分量则是原图中的极大连通子图；生成树不要求包含该分量的全部边，故不一定是连通分量。

易错点

“极小”与“极大”相反：生成树按边数是极小连通子图，连通分量按包含关系是极大连通子图，不能混淆。

若具有 (n) 个顶点的图是一个环，则它有（ ）棵生成树。

A. (n^2) B. (n) C. (n-1) D. 1

[tag_link]

正确答案：B

结论

一个含 (n) 个顶点的环有 (n) 棵生成树。

推导

环有 (n) 条边。删除环上的任意一条边，剩下的 (n-1) 条边都连接全部顶点且不再成环，恰好得到一棵生成树。可删除的边共有 (n) 条，故生成树数为 (n)。

易错点

生成树要求覆盖全部顶点且无环，不是任意删去一条边都要重新计数为 1；环上每一条边删除后都产生不同的生成树。

下列关于图的生成树和最小生成树的叙述中，正确的是（　　）。

A. 只要无向连通图中没有权值相同的边，则其最小生成树唯一 B. 只要无向图中有权值相同的边，则其最小生成树一定不唯一 C. 从 n 个顶点的连通图中选取 n-1 条权值最小的边，即可构成最小生成树 D. 设连通图 G 含有 n 个顶点，则含有 n 个顶点、n-1 条边的子图一定是 G 的生成树

[tag_link]

正确答案：A

结论

选 A。

推导

无向连通图所有边权互异时，Kruskal 或 Prim 每一步的最小合法边唯一，故 MST 唯一。B 中等权边不一定参与竞争；C 只按权值选边可能成环；D 还需满足连通性。

易错点

“n 个顶点、n−1 条边”只是树的必要数量条件，不足以保证无环且连通。