🏷️ 知识点：最少边数

对于一个有 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 条有向边至多形成有向路径，不能让所有顶点互相可达。