🏷️ 知识点：握手定理

一个无向图有 23 条边，度为 4 的顶点有 5 个，度为 3 的顶点有 4 个，其余顶点的度均为 2，则该图有（ ）个顶点。

A. 11 B. 12 C. 15 D. 16

[tag_link]

正确答案：D

结论

该图有 16 个顶点。

推导

由握手定理，所有顶点度数之和为 2×23=46。度为 4 和 3 的顶点贡献 5×4+4×3=32，剩余顶点贡献 46−32=14。其余顶点度为 2，所以有 14÷2=7 个；总顶点数为 5+4+7=16。

易错点

边数不是度数和；无向图每条边连接两个端点，必须先用 2|E| 求度数总和，再除以其余顶点的度。

已知无向图 (G) 含有 16 条边，其中度为 4 的顶点个数为 3，度为 3 的顶点个数为 4，其余顶点的度均小于 3。图 (G) 所含的顶点个数至少是（ ）。

A. 10 B. 11 C. 13 D. 15

[tag_link]

正确答案：B

结论

图 (G) 至少含有 11 个顶点，选项 B 正确。

推导

握手定理给出所有顶点度数之和 (2|E|=2\times16=32)。已知度为 4 和度为 3 的顶点贡献

[ 3\times4+4\times3=24。 ]

剩余顶点的度小于 3，且为了让顶点数尽可能少，应让它们尽量取最大的允许度数 2。设这样的顶点有 (x) 个，则 (24+2x=32)，解得 (x=4)。所以顶点总数至少为 (3+4+4=11)。

易错点

“度小于 3”意味着最大只能取 2，不能把余下度数 8 用 3 个顶点平均分摊；那会使每个顶点的度达到 (8/3)，且有顶点度为 3，违反条件。先用握手定理算余量，再用最大允许度数求最少顶点数。

下列关于无向连通图特性的叙述中，正确的是（ ）。

I. 所有顶点的度数之和为偶数； II. 边数大于顶点个数减 1； III. 至少有一个顶点的度为 1。

A. 只有 I B. 只有 II C. I 和 II D. I 和 III

[tag_link]

正确答案：A

结论

只有叙述 I 正确，答案为 A。

推导

由握手定理，所有顶点度数之和等于 (2|E|)，必为偶数。连通图的边数只需满足 (|E|\ge n-1)，树可取等号，所以 II 的“大于”不成立。环是连通图且所有顶点度为 2，说明连通图不保证存在度为 1 的顶点，III 也不成立。

易错点

把连通图的下界 (n-1) 误记成严格大于，或把“树至少有两个叶子”错误推广到所有连通图；含环的连通图可以没有度为 1 的顶点。

在含有 (n) 个顶点和 (e) 条边的简单无向图的邻接矩阵中，零元素的个数为（ ）。

A. (e) B. (2e) C. (n^2-e) D. (n^2-2e)

[tag_link]

正确答案：D

结论

零元素的个数为 (n^2-2e)，答案为 D。

推导

邻接矩阵共有 (n^2) 个位置。简单无向图没有自环，且每条无向边在矩阵中占据对称的两个非零位置，因此非零位置数为 (2e)，零元素数为 (n^2-2e)。

易错点

不能把每条无向边只计一次；矩阵同时记录 ((i,j)) 和 ((j,i))。若题目允许自环或使用其他特殊编码，公式需重新判断，本题明确按简单无向图处理。