🏷️ 知识点：无向图
一个有 n 个顶点和 n 条边的无向图一定是（ ）。
A. 连通的 B. 不连通的 C. 无环的 D. 有环的
[tag_link]
正确答案：D
结论
该图一定有环。
推导
无向森林若有 n 个顶点，边数至多为 n−1；当边数达到 n 时，不可能仍为森林，必含至少一个环。
易错点
n 条边不能推出连通；图可以分成多个连通分量，但边数超过森林上限仍必有环。
一个有 28 条边的非连通无向图至少有（ ）个顶点。
A. 7 B. 8 C. 9 D. 10
[tag_link]
正确答案：C
结论
至少需要 9 个顶点。
推导
8 个顶点的完全图恰有 C(8,2)=28 条边，但它连通。要保持非连通，可取一个 8 顶点完全子图再加 1 个孤立顶点，共 9 个顶点。
易错点
只计算 C(8,2)=28 会忽略非连通条件；8 顶点无法同时容纳 28 条边并保持非连通。
对于无向图 (G=(V,E))，下列选项中，正确的是（ ）。
A. 当 (|V|>|E|) 时，(G) 一定是连通的 B. 当 (|V|<|E|) 时，(G) 一定是连通的 C. 当 (|V|=|E|+1) 时，(G) 一定是不连通的 D. 当 (|V|>|E|+1) 时，(G) 一定是不连通的
[tag_link]
正确答案：D
结论
选项 D 正确：若 (|V|>|E|+1)，则 (|E|<|V|-1)，图不可能连通。
推导
含 (|V|) 个顶点的连通无向图至少需要 (|V|-1) 条边，等号情形就是生成树。D 的条件等价于 (|E|<|V|-1)，违反连通图的必要条件，因此必不连通。
A、B 都不是充分条件：顶点数大于边数时可以有多个孤立顶点；边数大于顶点数时也可以是一个稠密连通分量加孤立顶点。C 也错误，因为 (|E|=|V|-1) 的树就是连通图。
易错点
要区分“连通的必要条件”和“充分条件”。(|E|\ge |V|-1) 只是连通所需的必要条件，不足以保证连通；只有 (|E|<|V|-1) 才能直接推出一定不连通。
一个无向图有 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=(V,E)) 含有 7 个顶点，要保证图 (G) 在任何情况下都是连通的，则需要的边数最少是（ ）。
A. 6 B. 15 C. 16 D. 21
[tag_link]
正确答案：C
结论
至少需要 16 条边，选项 C 正确。
推导
要让 7 个顶点仍然不连通，边数最多的构造是一个含 6 个顶点的完全图 (K_6) 加 1 个孤立顶点，最多有 (\binom{6}{2}=15) 条边。因此再增加 1 条边后，不可能保持不连通，保证连通所需的最少边数为
[ \binom{7-1}{2}+1=\binom{6}{2}+1=16。 ]
一般地，7 个顶点的无向图有至少 (\binom{n-1}{2}+1) 条边时必连通。
易错点
不要把连通图的下界 (n-1=6) 当成“无论如何都连通”的保证值；6 条边可以只组成一棵树，也可以分散在多个连通分量中。保证值要从“最密的不连通构造”出发计算。
已知无向图 (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，违反条件。先用握手定理算余量，再用最大允许度数求最少顶点数。
一个有 6 个顶点的无向图，至少有（ ）条边时可以保证图是连通的。
A. 8 B. 9 C. 10 D. 11
[tag_link]
正确答案：D
结论
至少 11 条边才能保证 6 个顶点的无向图连通。
推导
不连通时，为了让边尽可能多，应取一个 5 个顶点的完全图和一个孤立点，边数为 C(5,2)=10。因此 10 条边仍可能不连通，增加一条边后必连通。一般地，n 个顶点至少需要 C(n−1,2)+1 条边保证连通。
易错点
n−1 是“构造一张连通图所需的最少边数”，不是“任意图保证连通”的阈值；保证连通要从最密的不连通图反推。
下列哪种图的邻接矩阵是对称矩阵？（ ）
A. 有向网 B. 无向图 C. AOV 网 D. AOE 网
正确答案：B
结论
B 无向图的邻接矩阵必为对称矩阵。
推导
无向边 {vᵢ,vⱼ} 同时表示 i 到 j、j 到 i，因此矩阵中 aᵢⱼ=aⱼᵢ；无自环时主对角线为 0。
易错点
A 有向网不保证对称；C AOV 网和 D AOE 网都是有向网络，边方向也不保证对称。