在图中找到最大的边数

Question

有一个无向图，有'n'个顶点和0条边。我们可以画多少条最大的边，使得图保持不连通。

我已经得出了解决方案：我们可以排除一个顶点，并找到无向图中n-1个顶点之间的最大边数，以便图形仍然保持不连通。

对于n个顶点，最大边数为n(n-1)/2；对于n-1个顶点，最大边数为(n-1)(n-2)/2。这是更好的解决方案吗？

- Luv

---

我投票关闭此问题，因为它是一个数学问题，而不是一个编程问题。 - TylerH

Answer 1

你可以通过分析来解决这个问题。把你的想法概括一下。将n个顶点分成两组，大小为x和n-x。 现在边数是x的函数，表示为：

  f(x)= x(x-1)/2 + (n-x)(n-x-1)/2
  f(x) = 1/2(2x^2 - 2nx +n^2 - n)

使该函数最大化的值是您想要的分区大小。如果进行计算，您会发现它从x = 0减少到x = n / 2，然后增加到x = n。由于x = 0或x = n表示图被收集，因此您选择下一个最大值，即x = 1。因此，您的直觉是最优的。

- UmNyobe

---

+1 这个解决方案证明了为什么给出的答案也是一个局部最大值。为了完全保护自己，您可能还想找到 f''，并找出 f''(MIN) < 0，并验证 f(n)，f(0) 不是可行解，并验证 f(1)，f(n-1)。 - amit

当然，我没有仔细阅读它，我只是看了这种方法的原则，在我看来是无懈可击的。 - amit

Answer 2

你的解决方案应该是最好的解决方案。

因为任何新添加的边都必须在一端有第n个顶点。

- sukunrt

---

提供的原因“因为任何新添加的边都必须在其中一个端点上有第n个顶点”解释了为什么它是局部最大值而不是全局最大值。这个解释并没有涵盖完全不同结构的解决方案，这些解决方案可能具有更多的边 - 没有适当的证明说明它们不能。 - amit

一个多重图中的边数显然是无限的。现在，如果它不能有自环，那么必须选择两个顶点来添加一条边。你已经完全连接了前(n-1)个顶点。为了添加一条边，两个顶点都不能来自初始的n-1个顶点集合，因为你已经从初始的n-1个顶点中创建了每一条可能的边。所以其中一条边必须是第n条。如果允许自环，则可以再添加n条边，因为自环不会增加连通性。 - sukunrt

这根本不能涵盖由两个不同于1和n-1大小的完全子图组成的图的可能性。解决方案是（意外地）正确的，但推理是错误的。 - voidengine

nC2是O(n^2)。因此k^2 + r^2将小于(k+r)^2。 - sukunrt

Answer 3

如果图可以有多条边，当n>=3时答案为无穷大。
如果它还可以包含自环，当n>=2时答案也是无穷大。

如果以上两种情况都不成立，则您的解决方案是正确的。

- kilotaras