一个无向非连通图共有20条边，则至少有（ ）个顶点。 A 7 B 8 C 9 D 10

由于一个无向非连通图可以被划分为若干个连通子图，而每个连通子图中的每个顶点都至少有一条边与其相连，因此该图至少包含连通子图的个数个顶点。又因为连通子图中的边数不少于顶点数减1，所以连通子图的边数之和不少于顶点数减去连通子图的个数。设该图包含k个连通子图，那么有20≥n-k，即k≥n-20。又因为每个连通子图至少包含一个顶点，所以n≥k，即n≥n-20，因此n至少为20+1=21。所以答案为D 10。

相关问题

设无向连通图有n个顶点e条边，若满足 ，则图中一定有回路。

根据图论中的欧拉公式，对于一个无向连通图，有：

n - e + f = 1

其中，n是顶点数，e是边数，f是图的连通分量数。对于一棵树而言，它是一个无向连通图，但是它没有回路，因此f=1。将这个值带入欧拉公式中，得到：

n - e + 1 = 1

即：

n = e

因此，如果一个无向连通图满足n=e，则它一定有回路。这是因为，如果一张无向图没有回路，那么它一定是一棵树，此时n=e+1，不符合上述条件。反之，如果n=e且它没有回路，那么它的连通分量数f大于1，根据欧拉公式，n-e+f不等于1，与条件矛盾。因此，一个无向连通图满足n=e时，一定有回路。

如果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。