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

Question

我自己无法回答这个问题，因为我在尝试的所有示例中都没有看到任何类似的行为。
问题又来了:
具有 n 个顶点和 k 个连通分量的无向图中的最大边数？
谢谢。

Answer 1

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

如果您有一个包含 x 个节点的连通分量，则该连通分量中的最大边数为 x(x - 1)/2。因此，如果您总共有 n 个节点和 k 个不同的连通分量，则可以想象一下以最大化 x(x - 1)/2 的总和的方式将节点分布到连接的组件中。

具体来说，假设您的 CC 各有 n1, ..., nk 个节点。你想解决以下二次程序:

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

Subject to: 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。

希望这可以帮助!