无向图中有n个顶点和k个连通分量的最大边数？

Question

我自己无法回答这个问题,因为我没有看到我试过的所有例子都有类似的行为.问题再次出现:无向图中的最大边数,其中n个顶点具有k个连通分量？谢谢.

Answer 1

这个答案取决于您的图表是否允许自循环.为简单起见,我假设它们不是.

如果连接组件中包含x个节点,则连接组件中可以包含的最大边数为x(x - 1)/ 2.因此,如果您有n个节点和k个不同的连接组件,则可以想象一下将节点分配到连接的组件中,以最大化连接组件上x(x - 1)/ 2的总和.

具体来说,假设您的CC 每个都有n ₁,...,n _k个节点.您想要解决以下二次方案:

最大化:n ₁(n ₁ - 1)/ 2 + ... + n _k(n _k - 1)/ 2

受制于:n ₁ + ... + n _k = n

当k-1连接组件有1个节点而最后一个连接组件中有n-k + 1个节点时,我将声称这是最大化的.直观地说,这是正确的,因为从巨大CC中删除的任何节点都会导致可能边缘数量的大幅下降,这些边缘不会被添加到节点中的另一个连接组件中可能边缘数量的微小增加所抵消. .

在此设置下,k-1单例CC中可能的最大边数将为0,另一CC中可能的最大边数将为(n-k + 1)(n-k)/ 2.因此,总数应为(n - k + 1)(n - k)/ 2.

希望这可以帮助!