下列关于无向连通图特征的叙述中,正确的是: 所有顶点的度之和为偶数 边数大于顶点个数减1 至少有一个顶点的度为1 A. 只有1 B. 只有2 C. 1和2 D. 1和3
时间: 2024-04-07 14:29:53 浏览: 23
正确的选项是C,即1和2。
1. 所有顶点的度之和为偶数是无向图的欧拉定理,对于任何无向图都成立。
2. 边数大于顶点个数减1是无向图连通性的一个必要条件,也就是说如果这个条件不成立,则该图必定不连通。
3. 至少有一个顶点的度为1是树的特征,而不是无向连通图的特征。而且即使是树也可能不存在度为1的顶点,比如只有一个顶点的树。
相关问题
无向连通图所有顶点的度数之和为偶数
证:
设无向连通图 $G=(V,E)$ 中有 $n$ 个顶点,$m$ 条边。则 $G$ 的所有顶点的度数之和为:
$$
\sum_{v\in V} \deg(v) = 2m
$$
其中 $\deg(v)$ 表示顶点 $v$ 的度数。
我们知道,每条边都会贡献 $2$ 到度数之和中,因为每条边连接了 $2$ 个顶点,每个顶点的度数都会加 $1$。因此,上式中的 $2m$ 就是所有顶点度数之和的总和。
而一个数能够被 $2$ 整除,当且仅当它的最低位为 $0$。因此,如果所有顶点的度数之和为偶数,那么它的二进制表示的最低位为 $0$,也就是说,每个顶点的度数都是偶数。
因为 $G$ 是一个无向图,所以每个顶点的度数就是它所连接的边数。如果所有顶点的度数都是偶数,那么每条边的两个端点的度数均为偶数。因此,每条边贡献 $2$ 到所有顶点度数之和中,也就是说,所有顶点度数之和为偶数。
综上所述,无向连通图所有顶点的度数之和为偶数。
一个无向非连通图共有20条边,则至少有( )个顶点。 A 7 B 8 C 9 D
设这个图有 $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)}$ 正确。
相关推荐
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![ppt](https://img-home.csdnimg.cn/images/20210720083527.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)