为什么具有 n 个顶点的强连通有向图至少需要 n 条边？

适用条件

• G 是有向图。
• G 有 n 个顶点。
• G 是强连通图。

理解与推导

1. 认识到强连通性要求对于所有顶点对，存在从 u 到 v 以及从 v 到 u 的路径。
2. 推断出图必须包含一个访问所有顶点的闭合有向游走。
3. 构造一个简单的有向环，按顺序连接这 n 个顶点。
4. 计算这个环中的边数，正好是 n。
5. 得出 n 条边是强连通有向图的绝对最小值的结论。

例子

讲师画了一个包含 4 个顶点（A, B, C, D）的有向环，其中 A 指向 B，B 指向 C，C 指向 D，D 指回 A。这恰好使用了 4 条边（n）来实现强连通性。

容易误解的地方

• 假设有向图可以像无向连通图一样用 n-1 条边实现强连通。
• 将无向连通图的最小边数（n-1）与有向强连通图的最小边数（n）混淆。

观看对应讲解

继续追问

• 具有 n 个顶点的有向图最多有多少条边？
• 在有向图中，强连通图的定义是什么？
• 为什么具有 n 个顶点的连通无向图至少需要 n-1 条边？