求图中的最大边数

Question

无向图有n个顶点和0个边。我们可以画出的最大边数是多少，这样图就会保持断开。

我给出了这样的解，即我们可以排除一个顶点，并且可以找到无向图的n-1顶点之间的最大边数，这样该图仍然保持不连通。

对于n个顶点为n( n-1 )/2，对于n-1顶点为(n-1)(n-2)/2 .有更好的解决办法吗？

Answer 1

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

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

Answer 2

您可以使用分析来解决这个问题。接受你的想法并加以概括。将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。所以你的直觉是最佳的。

Answer 3

如果图可以有多个边，则n>=3的答案是无穷大的。

如果它也可以包含自循环，那么对于n>=2，答案是无穷大的，

如果所有这些都不成立，你的解决方案是正确的。