1

For a algorithms final review, this question came up:

For a Graph G with V vertices and E edges, what is the largest number of edges 
this graph can have IF there are more than one connected components within G

Since a connected component is essentially a graph within a graph, that means all vertices within the subgraph must be removed from the larger graph while remaining internally connective. I can understand the intuition, but am having a hard time converting it into a formula.

Here's what I've come up with so far:

For connected component n, each graph Gn has a corresponding vertex set {Vn} such that the contents of the vertex set are internally connected, while remaining externally disconnected.

Graph G1 = {V1}
Graph G2 = {V2}
    ...
Graph Gn = {Vn}

Now, each {Vn} contains a maximum of V * (V-1) edges.

How can I express the maximum number of edges using a formula?

4

1 回答 1

1

如果它是多图（具有自环和平行边），那么当然可以有任意数量的边，但我相信这是关于边被定义为无向非自反边的图。

在这种情况下，K 个节点的每个组件最多可以有k* (k-1)边。由于这是二次性质的，如果你有一个巨大的组件和一个最小的组件，你可以实现的最大边数。所以只有两个组件，每个组件都有 N-1 和 1 个元素。

该图将具有( N - 1 ) * ((N - 1) - 1) = (N - 1) * (N - 2) = (N^2 -3N +2)边，我相信这是具有多个组件的图中的最大边数的公式。

于 2013-05-07T13:38:05.477 回答