有 n 个顶点的图中最大边数是多少

Question

带有 𝑛 的图中的最大边数 n 个顶点取决于图是有向图还是无向图。

看起来您正在询问带有 𝑛 的图中的最大边数 n 个顶点以及这如何取决于图是有向图还是无向图。

Answer 1

让我们考虑无向图。

对于 n = 4。无向图看起来像这样。

(V.a)--(V.b)
  |  \/  |
  |  /\  |
(V.c)--(V.d)

• 在无向图中，每条边连接两个顶点，每个顶点最多可以连接到（n-1）个其他顶点。
• 因此，可能的边总数就是每个顶点可以拥有的连接数之和，即 (n-1) + (n-2) + ... + 2 + 1 = n(n-1 )/2.

---

在有向图中，每条边都有一个方向，从一个顶点到另一个顶点。因此，对于每对顶点，您可以有两个可能的边（每个方向一个）。

具有 n 个顶点的完全有向图中可能的边数由下式给出： 𝑛 （ 𝑛 - 1 )