无向图有 'n' 个顶点和 0 条边。我们可以绘制的最大边数是多少，以使图形保持断开连接。
我已经做了一个解决方案，我们可以排除一个顶点，并且可以找到无向图的n-1个顶点之间的最大边数，以便该图仍然保持断开状态。
对于 n 个顶点，它是 n(n-1)/2，对于 n-1 个顶点，它是 (n-1)(n-2)/2。能有更好的解决方案吗？
问问题
5786 次
3 回答
7
您可以使用分析解决此问题。接受你的想法并概括它。您将 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。所以你的直觉是最佳的。
于 2012-04-08T11:18:11.873 回答
3
你的解决方案应该是最好的解决方案。
因为任何添加的新边都必须在一端有第 n 个顶点。
于 2012-04-08T10:35:58.387 回答
0
如果图可以有多条边，n>=3 的答案是无穷大。
如果它还可以包含自环，则答案是 n>=2 的无穷大，
如果这些都不成立，那么您的解决方案是正确的。
于 2012-04-08T10:56:32.030 回答