找到最大号码。图的边缘

无向图有'n'个顶点和0个边。我们可以绘制的最大边数是什么，这样图保持断开。找到最大号码。图的边缘

我已经做出了解决方案，我们可以排除一个顶点，并且可以找到无向图的n-1顶点之间的最大边数，以便图仍然保持断开状态。这对于n个顶点是n（n-1）/ 2，对于n-1个顶点将是（n-1）（n-2）/ 2有没有更好的解决方案？

2012-04-08 Luv

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

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

2012-04-08 10:35:58 sukunrt

提供的理由“”因为添加了任何新边缘必须在第一个顶点的第一个顶点“提供了为什么它是*局部最大值*而不是全局最大值*的解释。这种解释并不包含完全不同结构的解决方案，这些解决方案可能有更多的边缘 - 没有适当的证明，为什么他们不能。 – amit 2012-04-08 11:27:20

多图的边数显然是无限的。现在，如果它不能有自循环，那么你必须选择两个顶点来添加一个边。您已完全连接了第（n-1）个顶点。要添加一个边，两个顶点都不能来自初始的n-1个顶点集，因为您已经从初始的n-1个顶点创建了每个边。所以其中一个边缘必须是第n个边缘。如果你有自循环允许，那么你可以添加更多的边缘，因为自循环不会添加到连接。 – sukunrt 2012-04-08 12:09:22

这完全没有涵盖由两个大小不等于1，n-1的完整子图组成的图的可能性。解决方案（意外）是正确的，但推理不是。 – voidengine 2012-04-08 12:53:51

如果图可以有多条边，那么对于n> = 3，答案是无穷大。
如果它也可以包含自循环，答案是对n> = 2无穷大，

如果没有那些握着你的解决方案是正确的。

来源

2012-04-08 10:56:32 kilotaras

您可以使用分析解决此问题。把你的想法和概括。您将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-08 11:18:11 UmNyobe

+1此解决方案证明了为什么给出的答案也是局部最大值。为了完全覆盖自己，你可能还想找到f''，并找出'f''（MIN）<0'，并且验证f（n），f（0）不是可行解，并且验证f（1），f（n-1） – amit 2012-04-08 11:34:09

@amit f'（x）= 4x - 2n ... – UmNyobe 2012-04-08 11:34:31

并且你正确的是f'' – UmNyobe 2012-04-08 11:35:08

找到最大号码。图的边缘

回答

相关问题