为什么具有 n 个顶点的有向图的最大边数是 $n(n-1)$？

适用条件

• G 是有向图。
• G 有 n 个顶点。
• 我们正在寻找可能的最大边数。

理解与推导

1. 回忆具有 n 个顶点的无向完全图有 $n(n-1)/2$ 条边。
2. 认识到在有向图中，每对无序顶点可以支持两条有向边（每个方向一条）。
3. 将无向最大值乘以 2：$2 * [n(n-1)/2]$。
4. 化简得到有向最大值：$n(n-1)$。

例子

讲师解释说，因为有向图在一对顶点之间有两条边——一条向前，一条向后——所以我们将无向基础计数乘以二，得到 $n(n-1)$。

容易误解的地方

• 错误地将有向图的最大边数与无向图的最大边数（$n(n-1)/2$）等同起来。
• 假设自环（从顶点到其自身的边）包含在这个标准最大计数中。

观看对应讲解

继续追问

• 为什么具有 n 个顶点的无向图最多有 $n(n-1)/2$ 条边？
• 为什么具有 n 个顶点的强连通有向图至少需要 n 条边？
• 非连通无向图的最大边数是多少？