一个无向非连通图共有20条边,则至少有( )个顶点。 A 7 B 8 C 9 D
时间: 2024-05-30 22:12:14 浏览: 178
设这个图有 $n$ 个顶点,则根据握手定理,这个图的所有顶点的度数和为 $2m$,其中 $m$ 是边数,即 $2m = \sum_{i=1}^{n} d_i$。又因为这个图是非连通图,所以至少有两个连通块,每个连通块都是连通的,因此每个连通块内都满足握手定理,即每个连通块内所有顶点度数和为偶数。因此,对于一个有 $k$ 个连通块的非连通图,有 $2m = \sum_{i=1}^{k}\sum_{j=1}^{n_i} d_{ij}$,其中 $n_i$ 是第 $i$ 个连通块的顶点数,$d_{ij}$ 是第 $i$ 个连通块中第 $j$ 个顶点的度数。显然,对于每个连通块来说,至少有一个顶点的度数为 $1$,因此 $\sum_{j=1}^{n_i} d_{ij} \geq 2$,从而得到 $2m = \sum_{i=1}^{k}\sum_{j=1}^{n_i} d_{ij} \geq 2k$,即 $k \leq m$。又因为 $m = 20$,所以 $k \leq 20$,即这个非连通图至多有 $20$ 个连通块。
现在考虑最小的非连通图,即由两个连通块构成的非连通图。设这个非连通图的两个连通块的顶点数分别为 $a$ 和 $b$,则 $2m = a+b$,即 $a+b$ 是偶数。又因为这个非连通图共有 $20$ 条边,所以 $a+b \geq 20$。因此,$a+b$ 是偶数,$a+b \geq 20$,且 $a,b$ 都是正整数,所以 $a+b$ 可以取 $20,22,24,26,28$ 中的任意一个偶数。但是,当 $a+b=20$ 时,非连通图退化为一个连通图,不符合题意。因此,$a+b$ 只能取 $22,24,26,28$ 中的一个。又因为 $a,b$ 都是正整数,所以 $a+b \geq 3+19=22$,因此 $a+b$ 只能取 $22,24,26,28$ 中的一个。对于 $a+b=22$ 的情况,由于 $a,b$ 都是正整数,所以只有 $(a,b) = (11,11)$,此时非连通图由两个连通块构成,每个连通块都是一个五边形。对于 $a+b=24$ 的情况,$a,b$ 可以取 $(12,12)$ 或 $(11,13)$,此时非连通图由两个连通块构成,第一个连通块是一个六边形,第二个连通块是一个四边形。对于 $a+b=26$ 的情况,$a,b$ 可以取 $(13,13)$、$(12,14)$ 或 $(11,15)$,此时非连通图由两个连通块构成,第一个连通块是一个七边形,第二个连通块是一个三边形、五边形或七边形。对于 $a+b=28$ 的情况,$a,b$ 可以取 $(14,14)$、$(13,15)$、$(12,16)$ 或 $(11,17)$,此时非连通图由两个连通块构成,第一个连通块是一个八边形,第二个连通块是一个二边形、四边形、六边形或八边形。
综上所述,非连通图的顶点数至少为 $7$。因此,选项 $\textbf{(A)}$ 正确。
阅读全文