如果G是一个有28条边的非连通无向图，那么该图顶点个数最少为 。 A.10 B.9 C.8 D.7

如果一个无向图有 $n$ 个顶点，那么最少有 $\frac{n(n-1)}{2}$ 条边。因此，如果一个无向图有 28 条边，那么它至少应该有 $\frac{-1+\sqrt{1+8\times28}}{2}=7$ 个顶点。而由于该图是非连通的，它可以被分成若干个连通块。因此，该图顶点个数最少为 $7$，选D。

相关问题

若无向图g =（v，e）中含7个顶点，要保证图g在任何情况下都是连通的，则需要的边数最少是：

### 回答1：
根据欧拉公式，如果一个图是连通的，则它的顶点数、边数和面数之间有如下关系：v - e + f = 2，其中 v 是顶点数，e 是边数，f 是面数。

根据题目描述，g 包含 7 个顶点且是无向图，要保证 g 在任何情况下都是连通的，那么至少需要 6 条边才能连接这 7 个顶点。如果 g 恰好有 6 条边，则根据欧拉公式，f = 1，也就是说 g 只有一个面。如果再添加一条边，也就是 e = 7，则根据欧拉公式，f = 2，也就是说 g 有两个面。因此，g 最少有 6 条边，且最少有 2 个面。

所以，要保证 g 在任何情况下都是连通的，且至少有 2 个面，则需要满足 e ≥ 6，f ≥ 2。根据欧拉公式可以推导出 v ≤ e + 2，代入 e ≥ 6 可得 v ≤ 8。

因此，g 中顶点数最少为 7，边数最少为 6，且顶点数最多为 8。而当 g 中有 8 个顶点时，需要满足 e ≥ 7，f ≥ 2，根据欧拉公式可以推导出至少有 9 条边，这与顶点数最多为 8 矛盾，因此 g 中顶点数最多为 7。

综上所述，g 中顶点数为 7，边数至少为 6，边数至多为 12。因此，g 中的边数最少为 6。

### 回答2：
如果一个无向图要保证在任何情况下都是连通的，那么这个图应该是一个连通图。对于一个无向图G=(V,E)，如果G是连通图，则从任意一个顶点出发可以到达图中的任意一个顶点。因此，在一个有n个顶点的连通图中，至少需要n-1条边才能使得这个图连通，即达到“无孤立点，无孤立边”的状态。

所以对于本题的情况，含有7个顶点的连通图至少需要6条边才能保证它在任何情况下都是连通的。这是因为当只有1条边时，只能构成一个二分图，若这个二分图为两个独立的子图，则对于这些子图中的顶点对就不连通；当有2条边时，可以构成一个组成矩形的连通图，但是如果任意一条边去掉，则这个图就不再连通；当有3条边时，可以构成一个组成三角形的连通图，但是如果再添加一个顶点，则这个图就不再连通了；当有4条边时，可以构成一个组成平行四边形的连通图，但是如果再添加一个顶点，则这个图就不再连通了；当有5条边时，可以构成一个组成五边形的连通图，但是同样如果再添加一个顶点，则这个图就不再连通了；当有6条边时，可以构成一个组成六边形的连通图，而且添加一个顶点之后，这个图也依然连通。

综上所述，真正能保证在任何情况下都是连通的、含有7个顶点的连通图，至少需要6条边。

### 回答3：
要确保无向图g = (v, e)中含有7个顶点的任何情况下都是连通的，我们需要找到最小的边数来实现这一目标。

对于无向图，n个顶点的完全连通图有n(n-1)/2个边。在本例中，我们需要确保7个顶点都是连通的，因此我们需要一个包含所有这些顶点的最小生成树。最小生成树是一种只包含n个顶点，但仍然可能是一个复杂图的最小可能的生成子图。因此，我们可以使用Kruskal或Prim算法来寻找最小生成树。

对于7个顶点的无向图，最小生成树可能包含的最小边数为6条。我们可以按以下方式计算最小生成树的数量。首先，在图中选择任意一个顶点作为起始点，然后选择6个最短距离的边将它连接到其它点。这样我们获得的就是一个最小生成树，包含了所有这些顶点，并且只使用了6条边。如果我们再添加一条边，就会形成一个环，并且会多一个顶点与它连接。也就是说，最小生成树的数量只有一种可能性，即含6条边。

因此，7个顶点的无向图，要保证在任何情况下都是连通的，需要的边数最少是6条。

若无向图G =（V，E）中含8个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是：

当一个无向图是连通的时，它的任意两个顶点都可以通过边连接起来。在一个具有8个顶点的无向图中，最少需要7条边才能保证该图是连通的。这是因为当一个无向图中的边数小于7时，必然存在两个不相连的顶点，因此图不连通。而当边数为7时，可以构造一种连通的无向图，如下所示：

  1 -- 2 -- 3
  |    |    |
  4 -- 5 -- 6
         \  |
           7
           |
           8

因此，需要的边数最少是7条。