找到最大数量.图中的边缘

Question

无向图有'n'个顶点和0个边.我们可以绘制的最大边数可以使图形保持断开状态.

我已经做出了解决方案,我们可以排除一个顶点,并且可以找到无向图的n-1个顶点之间的最大边数,这样图形仍然保持断开状态.n个顶点为n(n-1)/ 2,n-1个顶点为(n-1)(n-2)/ 2可以有更好的解吗？

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.所以你的直觉是最佳的.

Answer 2

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

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