具有k个连通分量的n个顶点的无向图中的最大边数？ [英] Maximum number of edges in undirected graph with n vertices with k connected components?

问题描述

我自己无法回答这个问题，因为我没有看到我尝试过的所有例子都有类似的行为。
问题再次提出：
具有k个连通分量的n个顶点的无向图中的最大边数？
Thanks。

解决方案

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

如果您有一个连接的组件，其中包含x个节点，您可以使用的最大边数那么连接的分量是x（x-1）/ 2。因此，如果你有n个总节点和k个不同的连通分量，你可以想象将节点分配到连通分量中的方式可以使x（x - 1 ）/ 2跨越连接的组件。

具体而言，假设您的CC具有n ₁ ，...，n <sub>k <每个子节点。你想解决下面的二次方程：

blockquote
最大化：n 1 1（n 1） 1）/ 2 + ... + nk（nk-1）/ 2</sub>

符合：n ₁ + ... + n = n

我会声称当连通组件的k-1有1个节点而最后连接的组件有n-k + 1个节点时，这是最大化的。直观地说，这是真实的，因为从巨大的CC中删除的任何节点都会导致可能边的数量大幅下降，这些边不会因为节点添加到其他连接组件中可能边的数量微薄增加而被抵消。

在此设置下，k-1个单独CC中可能边的最大数量将为0，另一个CC中可能边的最大数将为因此，总数应该是（n - k + 1）（n - k）/ 2。

希望这有助于！

I couldn't answer the question myself because i don't see any similar behavior for all the examples i tried. The question again: Maximum number of edges in undirected graph with n vertices with k connected components? Thanks.

解决方案

This answer depends on whether your graphs are allowed to have self-loops or not. For simplicity, I'm going to assume they aren't.

If you have a connected component with x nodes in it, the maximum number of edges you can have in that connected component is x(x - 1) / 2. Therefore, if you have n total nodes and k different connected components, you can imagine distributing the nodes into the connected components in a way that maximizes the sum of x(x - 1) / 2 across the connected components.

Specifically, suppose your CC's have n₁, ..., n_k nodes each. You want to solve the following quadratic program:

Maximize: n₁(n₁ - 1) / 2 + ... + n_k(n_k - 1) / 2

Subject to: n₁ + ... + n_k = n

I'm going to claim that this is maximized when k - 1 of the connected components have 1 node and the last connected component has n - k + 1 nodes in it. Intuitively, this is true because any node you remove from the huge CC will cause a large drop in the number of possible edges that will not be offset by the meager increase in the number of possible edges in the other connected component the node was added to.

Under this setup, the maximum number of possible edges in the k - 1 singleton CC's will be 0 and the maximum number of possible edges in the other CC will be (n - k + 1)(n - k) / 2. Therefore, the total should be (n - k + 1)(n - k) / 2.

Hope this helps!

这篇关于具有k个连通分量的n个顶点的无向图中的最大边数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！