algorithm - 非连通图中的最大边数

Question

在具有n顶点且没有边的无向图中，可以添加的最大边数是多少以使该图保持未连接状态？这是一道面试题。

1. NC2
2. (N-1)C2
3. N！
4. （N-1）！

Answer 1

具有 N 个顶点的图中的最大边数为 NC2（链接）。

请注意，要保持未连接状态，其中一个顶点不应有任何边。更正式地说，必须有一个切口（不会有任何边缘），一侧只有一个顶点。为什么不超过一个顶点？归纳证明：

0、1 和 2 个顶点的情况是微不足道的。

考虑一个有 3 个顶点的图。最好的切割是一侧有 2 个顶点，另一侧有 1 个顶点的切割。

现在假设最好的切割是一侧有 N-1 个顶点，另一侧有 1 个顶点且 N >= 3 的切割。现在尝试添加一个顶点。将顶点添加到具有一个顶点的一侧将导致可以添加一条边。将顶点添加到另一侧将导致 N-1 条可能的边。对于 N >= 3，显然 N-1 > 1。因此，最好将顶点添加到具有 N-1 个顶点的一侧。

现在有两种方法可以从这里开始：

1. 考虑没有一条边的图。该子图的最大边数为(N-1)C2。

2. 考虑图的最大边数，并从一个顶点中减去边数。这给出了NC2 - (N-1)= N(N-1)/2 - 2(N-1)/2= (N-2)(N-1)/2= (N-1)C2。

所以答案是(N-1)C2，即选项2。

Answer 2

b (n-1)C2

这种图的一个例子是 n-1 个顶点和一个孤立顶点的完整图。

在此示例中，补图将具有 nC2 - (n-1)C2 = n-1 条边。并且给定的图或其补码是连接的（证明）。因此，如果我们构造一个具有多于 (n-1)C2 条边的图，那么补集的边将少于 n-1 条并且无法连接，所以我们的图将是。