图论¶
方法速览¶
| 任务 | 方法 | 口诀 |
|---|---|---|
| 非连通图最少点数 | 找最小 n 使 \(\binom{n-1}{2} \ge m\)（n−1 个点抱团 + 1 孤点） | 团加孤点 |
| 二分图最多边 | 两侧尽量均分：\(\left\lfloor \dfrac{n^2}{4} \right\rfloor\) | 对半最密 |
| 二分图判定 | 能两种颜色染色 ⟺ 无奇环 | 无奇环可二染 |
| 欧拉回路存在 | 连通 + 全度偶；欧拉路径：恰 0 或 2 个奇点 | 全偶有回路 |
| 强连通 | 任意两点互达（不等于任意两点有边） | 互达非相邻 |
| 环计数（n 点标号） | \((n-1)!/2\) 个不同 n 元环 | 环排再除二 |
| 完全图 K_n 中 4 环 | \(\binom{n}{4} \times 3\) | 选四再乘三 |
| 边权 \(\|i-j\|\) 的 K_n MST | 权 1 的链 \((1,2),\dots,(n,n{-}1)\)，总权 \(n-1\) | 相邻连成链 |
边数的上下界¶
| 图 | 边数界限 | 取等条件 |
|---|---|---|
| n 点无向简单图 | \(\le \binom{n}{2}\) | 完全图 \(K_n\) |
| n 点二分图 | \(\le \left\lfloor n^2/4 \right\rfloor\) | 两侧 \(\lceil n/2\rceil\) 与 \(\lfloor n/2\rfloor\) 全连接 |
| n 点不连通简单图 | \(\le \binom{n-1}{2}\) | n−1 个点构成完全图 + 1 个孤立点 |
| n 点连通图 | \(\ge n-1\) | 树 |
【例】（2019 真题）不连通、28 条边，至少几个点？倒着推：n−1 个点最多 \(\binom{n-1}{2}\) 条——
| n−1 | \(\binom{n-1}{2}\) | 够 28 吗 |
|---|---|---|
| 7 | 21 | ✗ |
| 8 | 28 | ✓ |
n−1 = 8 → n = 9 个点（8 点完全图 + 1 孤点）。2021 年 36 条边同理：\(\binom{9}{2} = 36\) → 10 个点。
特殊图：二分图、欧拉图、强连通¶
| 图类 | 定义 | 判定要点 |
|---|---|---|
| 二分图 | 顶点分两部分，边只跨部分 | 两种颜色可染色 ⟺ 无奇环 |
| 欧拉图 | 存在经过每条边恰一次的回路 | 连通 + 所有顶点度数为偶 |
| 强连通（有向） | 任意两点互相可达 | 有路径 ≠ 有边；最少 n 条弧（大环） |
【例】（2020 真题）24 个顶点的二分图至多几条边？均分两侧 12 + 12，全连接 \(12 \times 12 = 144\) 条——不均分（13+11）只有 143，均分最密。
【例】（2022 真题）2 正规图（每点度恰 2）中含欧拉回路的：度全为 2（偶）只需连通——即整个图就是一个 n 元环，n 个标号点的环共 \((n-1)!/2\) 个（环排列除翻转）。
拓扑排序与 DAG¶
- 拓扑序存在 ⟺ 有向无环；
- 计数没有通用公式：链只有 1 种、无边 DAG 有 \(n!\) 种——具体图具体模拟（删入度 0 顶点逐步枚举分支）。
最小生成树 MST¶
Kruskal：边按权从小到大，不成环就选；Prim：从任意点长出，每次接跨集合最短边。
【例】（2025 真题）\(K_8\)、边权 \(w(i,j) = |i-j|\)，MST 总权：权为 1 的边 \((1,2),(2,3),\dots,(7,8)\) 共 7 条恰好连成链、总权 \(7\times1 = 7\)——更小的权不存在，7 条权 1 已是最优。
通用结论：边权 \(|i-j|\) 的 \(K_n\)，MST = n − 1（相邻链）。
树的重心¶
重心：以它为根时，最大子树结点数最小的那个结点。
- 重心只有 1 个或 2 个，若有 2 个则它们相邻；
- 有 2 个重心 ⟺ 某条边两侧结点数都是 \(n/2\) → n 必为偶数；
- 推论：n 为奇数的树重心唯一（2023 真题：7 个结点的树）。
稀疏图与稠密图的算法选型¶
\(m = \Theta(n)\)（稀疏）时代入检验：把每个选项的 m 换成 n 比较——
| 选项（2023 真题） | 代入 m = Θ(n) |
|---|---|
| \(O(m\sqrt{\log n\cdot\log\log n})\) | \(O(n\sqrt{\log n \log\log n})\) ← 最小 ✓ |
| \(O(n^2 + m)\) | \(O(n^2)\) |
| \(O(n^2/\log m + m\log n)\) | \(O(n^2/\log n)\) |
| \(O(m + n\log n)\) | \(O(n\log n)\) |
注意 \(O(n\sqrt{\log n\log\log n})\) 比 \(O(n\log n)\) 小（\(\sqrt{\log n} < \log n\)）——“代进去、比阶”是万能流程。
练习题目¶
练习 1 · 完全图边数¶
题目
完全图 \(K_9\) 的边数是（ ）
- A. \(72\)
- B. \(81\)
- C. \(36\)
- D. \(45\)
答案与解析
答案：C
\(\binom{9}{2} = \dfrac{9\times8}{2} = 36\)——有向版才是 \(n(n-1) = 72\)。
练习 2 · 非连通最少点（小例）¶
题目
不连通简单无向图有 10 条边，至少（ ）个顶点。
- A. \(5\)
- B. \(7\)
- C. \(6\)
- D. \(4\)
答案与解析
答案：C
\(\binom{5}{2} = 10\)：5 个点完全图 + 1 孤点 = 6 个。
练习 3 · 非连通最少点（变式）¶
题目
不连通简单无向图有 45 条边，至少（ ）个顶点。
- A. \(10\)
- B. \(11\)
- C. \(12\)
- D. \(9\)
答案与解析
答案：B
\(\binom{10}{2} = 45\) → 10 点抱团 + 1 孤点 = 11。
练习 4 · 非连通最多边¶
题目
9 个顶点的不连通简单无向图最多有（ ）条边。
- A. \(36\)
- B. \(29\)
- C. \(35\)
- D. \(28\)
答案与解析
答案：D
8 个点完全图 \(\binom{8}{2} = 28\) + 1 孤点——与“28 条边至少 9 点”互为镜像。
练习 5 · 二分图最多边¶
题目
10 个顶点的二分图最多有（ ）条边。
- A. \(45\)
- B. \(50\)
- C. \(25\)
- D. \(20\)
答案与解析
答案：C
均分 5 + 5 全连接：\(5\times5 = 25 = \lfloor 10^2/4\rfloor\)。
练习 6 · 二分图最多边（奇数点）¶
题目
7 个顶点的二分图最多有（ ）条边。
- A. \(12\)
- B. \(21\)
- C. \(10\)
- D. \(9\)
答案与解析
答案：A
分 3 + 4 全连接：\(3\times4 = 12 = \lfloor 49/4\rfloor\)——奇数点不能整半。
练习 7 · 二分图判定¶
题目
下列图一定可以两种颜色染色（相邻异色）的是（ ）
- A. 含奇环的图
- B. 树
- C. 完全图 \(K_4\)
- D. 三角形
答案与解析
答案：B
二分 ⟺ 无奇环；树无环天然满足；\(K_4\) 与三角形内部两两相邻，同部两点也有边，不合法。
练习 8 · 奇环与染色¶
题目
一个图不能用两种颜色染色，则它（ ）
- A. 是完全图
- B. 一定含偶环
- C. 不连通
- D. 一定含奇环
答案与解析
答案：D
染色失败的本质：绕奇环一圈颜色要求翻转——非二分 ⟺ 存在奇环。
练习 9 · 欧拉回路条件¶
题目
无向连通图存在欧拉回路的充要条件是（ ）
- A. 是完全图
- B. 恰有两个奇点
- C. 所有顶点度数为偶数
- D. 边数为偶数
答案与解析
答案：C
连通 + 全度偶 ⟺ 欧拉回路；恰两奇点是欧拉路径（一进一出）的条件。
练习 10 · 欧拉路径¶
题目
一笔画（每条边恰走一次，不要求回起点）能完成的条件是奇点个数为（ ）
- A. \(0\)
- B. 恰好 \(2\)
- C. 任意偶数
- D. \(0\) 或 \(2\)
答案与解析
答案：D
0 个奇点：回路（起点终点重合）；2 个：从一奇点到另一奇点。哥尼斯堡七桥 4 个奇点 → 画不成。
练习 11 · 欧拉图辨析¶
题目
欧拉图中（ ）一定成立。
- A. 边数是偶数
- B. 所有顶点度数为偶数且图连通
- C. 顶点数是偶数
- D. 每个顶点度数相同
答案与解析
答案：B
这是定义的判定式；边数奇偶（A）、点数奇偶（C）与欧拉性无关——三角形是欧拉图但只有 3 条边 3 个点。
练习 12 · 强连通¶
题目
n 个顶点的有向图强连通，至少（ ）条弧。
- A. \(n-1\)
- B. \(2n\)
- C. \(n\)
- D. \(\binom{n}{2}\)
答案与解析
答案：C
一个大环 \(1\to2\to\cdots\to n\to 1\) 恰 n 条互达；\(n-1\) 条像树，回不去。
练习 13 · 强连通与完全¶
题目
有向完全图（任意有序对都有弧）与强连通的关系（ ）
- A. 等价
- B. 强连通必是完全图
- C. 互不相关
- D. 完全图必强连通
答案与解析
答案：D
全都有边 ⇒ 全都互达；反方向不成立（环强连通但边少）——互达不等于相邻。
练习 14 · 环计数¶
题目
n 个标号顶点能构成的不同三元环（三角形）有（ ）个。
- A. \(3\binom{n}{3}\)
- B. \(n!\)
- C. \(\binom{n}{3}\)
- D. \(n^3\)
答案与解析
答案：C
任选 3 个点恰构成一个三角形（3 点环无不同排法）；4 点环才要乘 3。
练习 15 · 四元环计数¶
题目
完全图 \(K_6\) 中不同的 4 长度环有（ ）个。
- A. \(15\)
- B. \(45\)
- C. \(60\)
- D. \(360\)
答案与解析
答案：B
\(\binom{6}{4}\times3 = 15\times3 = 45\)：选 4 点后，固定一点起、除翻转，共 3 种环序。
练习 16 · 四元环计数（大例）¶
题目
完全图 \(K_{10}\) 中不同的 4 长度环有（ ）个。
- A. \(210\)
- B. \(630\)
- C. \(1260\)
- D. \(5040\)
答案与解析
答案：B
\(\binom{10}{4}\times3 = 210\times3 = 630\)。
干扰项思路：A 只选了点没乘环序；C 乘 6（把翻转当成不同）；D 是排列数。
练习 17 · 拓扑排序计数¶
题目
n 个点 m 条边的 DAG，拓扑排序的可能数目（ ）
- A. 恰 1 种
- B. 恰 \(n!\) 种
- C. 恰 \(n - m\) 种
- D. 以上都不对——取决于具体连边
答案与解析
答案：D
链（每点依赖前一点）只有 1 种；无边 DAG 有 \(n!\) 种——没有任何公式只由 n、m 决定。
练习 18 · 拓扑序的约束¶
题目
5 个点的 DAG 有边 \(\langle1,2\rangle,\langle1,3\rangle,\langle2,4\rangle,\langle3,4\rangle,\langle4,5\rangle\)，拓扑序（ ）
- A. 一定是
1 2 3 4 5 - B. 是
1 2 3 4 5或1 3 2 4 5，共 2 种 - C. 有 5 种
- D. 不存在
答案与解析
答案：B
1 必须最先、5 必须最后、4 在 2、3 之后——只有 2、3 的相对顺序自由。
练习 19 · MST 边数¶
题目
n 个顶点连通图的最小生成树有（ ）条边。
- A. \(n\)
- B. \(n-1\)
- C. \(n/2\)
- D. 取决于图
答案与解析
答案：B
生成树就是树：\(n-1\) 条——“最小”只挑哪组边，不改变条数。
练习 20 · MST 手算（Kruskal）¶
题目
边集 \(\{(A,B,1),(B,C,2),(A,C,3),(C,D,4),(A,D,5)\}\) 按 Kruskal 选入 MST 的顺序是（ ）
- A. \((A,B),(B,C),(C,D)\)
- B. \((A,B),(A,C),(C,D)\)
- C. \((A,B),(B,C),(A,C),(C,D)\)
- D. \((B,C),(A,B),(C,D)\)
答案与解析
答案：A
权 1、2 直接入；权 3 的 \((A,C)\) 会成环（A-B-C 已通）跳过；权 4 入——总权 \(1+2+4=7\)。
练习 21 · MST 变式¶
题目
完全图 \(K_5\)、边权 \(w(i,j)=|i-j|\)，MST 总权是（ ）
- A. \(4\)
- B. \(5\)
- C. \(6\)
- D. \(10\)
答案与解析
答案：A
权 1 的链 \((1,2),(2,3),(3,4),(4,5)\) 恰好 4 条边连全部点：总权 \(4 = n-1\)。
练习 22 · 树的重心个数¶
题目
一棵树的重心（ ）
- A. 恰好 1 个
- B. 一定是叶子
- C. 可以有 3 个
- D. 1 个或 2 个，若有 2 个则相邻
答案与解析
答案：D
4 个结点的链 P4 重心是中间两个（相邻）；星形重心是中心 1 个。
练习 23 · 奇数点的重心¶
题目
9 个结点的树，重心（ ）
- A. 一定唯一
- B. 一定有 2 个
- C. 可能有 2 个
- D. 是度为 1 的结点
答案与解析
答案：A
两个重心 ⟺ 某边两侧各 \(n/2\) 点 → n 必须是偶数；奇数点的树重心唯一。
练习 24 · 邻接表遍历复杂度¶
题目
n 点 e 边的图用邻接表做 DFS，时间复杂度（ ）
- A. \(\Theta(n + e)\)
- B. \(\Theta(n^2)\)
- C. \(\Theta(e^2)\)
- D. \(\Theta(n)\)
答案与解析
答案：A
每点进出各一次、每条边扫一次（无向图两次）；邻接矩阵版才是 \(\Theta(n^2)\)。
练习 25 · 稀疏图选型¶
题目
\(m = \Theta(n)\) 的稀疏图上，\(O(n\log n)\) 与 \(O(n^2)\) 的算法应选（ ）
- A. \(O(n\log n)\)
- B. \(O(n^2)\)
- C. 都一样
- D. 看运气
答案与解析
答案：A
\(n = 10^5\) 时 \(n\log n \approx 1.7\times10^6\)、\(n^2 = 10^{10}\)——差四个数量级。
练习 26 · 握手定理（S 视角）¶
题目
无向图各点度数 \(4, 3, 3, 2, 2, 1\)，则（ ）
- A. 边数为 \(15\)
- B. 边数为 \(7.5\)
- C. 边数为 \(7\)
- D. 不存在这样的图
答案与解析
答案：D
度和 \(= 4+3+3+2+2+1 = 15\) 是奇数，违反握手定理（度和必为偶数 \(2m\)）——这个度序列根本不可能是图。审题先验合法性，别急着除以 2。
练习 27 · 图的存储¶
题目
下列可以用来存储图的是（ ）
- A. 邻接矩阵
- B. 二叉树
- C. 栈
- D. 哈夫曼树
答案与解析
答案：A
邻接矩阵 / 邻接表 / 边集数组是图的三大存储；栈、队列、树是操作结构，不是图的存法。
历年真题¶
2019 年 · 第 8 题¶
题目
\(G\) 是一个非连通无向图（没有重边和自环），共有 \(28\) 条边，则该图至少有（ ）个顶点。
- A. \(9\)
- B. \(8\)
- C. \(10\)
- D. \(11\)
答案与解析
答案：A
非连通 → 至少 1 个点在团外 → n−1 个点要装下 28 条边：\(\binom{8}{2} = 28\) 恰好 → n = 9（8 点完全图 + 孤点）。
2019 年 · 第 12 题¶
题目
以下哪个结构可以用来存储图（ ）
- A. 二叉树
- B. 队列
- C. 邻接矩阵
- D. 栈
答案与解析
答案：C
邻接矩阵 / 邻接表是图的专用存储。
2020 年 · 第 7 题¶
题目
具有 \(n\) 个顶点、\(e\) 条边的图采用邻接表存储结构，进行深度优先遍历运算的时间复杂度为（ ）。
- A. \(\Theta(n+e)\)
- B. \(\Theta(n^2)\)
- C. \(\Theta(e^2)\)
- D. \(\Theta(n)\)
答案与解析
答案：A
每点访问一次 + 每边扫一次；只有当图很稠密（\(e \approx n^2\)）时它才退化到 \(n^2\) 量级。
2020 年 · 第 8 题¶
题目
二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那么，\(24\) 个顶点的二分图至多有（ ）条边。
- A. \(144\)
- B. \(100\)
- C. \(48\)
- D. \(122\)
答案与解析
答案：A
均分 12 + 12 全连接：\(12\times12 = 144\)；不均分只会更少——\(\lfloor n^2/4\rfloor\)。
2021 年 · 第 7 题¶
题目
\(G\) 是一个非连通简单无向图（没有自环和重边），共有 \(36\) 条边，则该图至少有（ ）个点。
- A. \(8\)
- B. \(9\)
- C. \(10\)
- D. \(11\)
答案与解析
答案：C
\(\binom{9}{2} = 36\) → 9 点完全图 + 1 孤点 = 10 个（与 2019 年 28 边同一模型，两年复现）。
2022 年 · 第 8 题¶
题目
强连通图的性质不包括（ ）。
- A. 每个顶点的度数至少为 \(1\)。
- B. 任意两个顶点之间都有边相连。
- C. 任意两个顶点之间都有路径相连。
- D. 每个顶点至少都连有一条边。
答案与解析
答案：B
强连通要的是互相可达（路径），不是两两相邻（边）——环是强连通的但边只有 n 条；B 描述的是有向完全图。
2022 年 · 第 9 题¶
题目
每个顶点度数均为 \(2\) 的无向图称为 2 正规图。由编号为从 \(1\) 到 \(n\) 的顶点构成的所有 2 正规图中，包含欧拉回路的不同 2 正规图的数量为（ ）。
- A. \(n!\)
- B. \((n-1)!\)
- C. \(\frac{n!}{2}\)
- D. \(\frac{(n-1)!}{2}\)
答案与解析
答案：D
度全为 2 已满足偶度；含欧拉回路还需连通 → 恰是一个 n 元环。n 个标号点的环 = 环排列 \((n-1)!\) 再除翻转 2。
2023 年 · 第 3 题¶
题目
假设 \(n\) 是图的顶点个数，\(m\) 是图的边数，为求解某一问题有下面四种不同时间复杂度的算法。对于 \(m=\Theta(n)\) 的稀疏图而言，下面四个选项中哪一项的渐近时间复杂度最小？（ ）
- A. \(O\!\left(m\sqrt{\log n\cdot\log\log n}\right)\)
- B. \(O(n^2+m)\)
- C. \(O\!\left(\frac{n^2}{\log m}+m\log n\right)\)
- D. \(O(m+n\log n)\)
答案与解析
答案：A
代入 \(m=\Theta(n)\)：A 为 \(n\sqrt{\log n\log\log n}\)；D 为 \(n\log n\)。因 \(\sqrt{\log n\log\log n} < \log n\)（n 足够大时），A 比 D 还小；B、C 都含 \(n^2\) 量级项。
2023 年 · 第 6 题¶
题目
以下连通无向图中，（ ）一定可以用不超过两种颜色进行染色。
- A. 完全三叉树
- B. 平面图
- C. 边双连通分量图
- D. 欧拉图
答案与解析
答案：A
树无环 → 无奇环 → 可二染；B/C/D 都能构造出奇环（如三角形既是平面图也是欧拉图）。
2023 年 · 第 12 题¶
题目
在图论中，树的重心是树上的一个结点，以该结点为根时，使得其所有子树中结点数最多的子树的结点数最少。一棵树可能有多个重心。下面哪种树一定只有一个重心？（ ）
- A. \(4\) 个结点的树
- B. \(6\) 个结点的树
- C. \(7\) 个结点的树
- D. \(8\) 个结点的树
答案与解析
答案：C
双重心 ⟺ 某边两侧各 \(n/2\) 点 ⟹ n 为偶数；奇数点的树重心必唯一，7 是唯一奇数选项。
2024 年 · 第 7 题¶
题目
假设有一个包含 \(n\) 个顶点的无向图，且该图是欧拉图。以下关于该图的描述中哪一项不一定正确？（ ）
- A. 所有顶点的度数均为偶数
- B. 该图连通
- C. 该图存在一个欧拉回路
- D. 该图的边数是奇数
答案与解析
答案：D
A/B/C 是欧拉图的定义组成；边数奇偶与欧拉性无关（三角形 3 条边是欧拉图，正方形 4 条边也是）。
2024 年 · 第 12 题¶
题目
设有一个有 \(10\) 个顶点的完全图，每两个顶点之间都有一条边。有多少个长度为 \(4\) 的环？
- A. \(120\)
- B. \(210\)
- C. \(630\)
- D. \(5040\)
答案与解析
答案：C
选 4 点 \(\binom{10}{4} = 210\)；每 4 点上不同 4 环有 3 个（固定起点去方向）：\(210\times3 = 630\)。
2025 年 · 第 5 题¶
题目
对于一个包含 \(n\) 个结点和 \(m\) 条边的有向无环图（DAG），其拓扑排序的结果有多少种可能？
- A. 只有 \(1\) 种
- B. 最多 \(n\) 种
- C. 等于 \(n-m\) 种
- D. 以上都不对
答案与解析
答案：D
拓扑序数由具体连边决定：链 1 种、无边图 \(n!\) 种——n 和 m 固定时也能有不同答案（同 n、m 不同构）。
2025 年 · 第 7 题¶
题目
一个包含 \(8\) 个顶点的完全图（顶点的编号为 \(1\) 到 \(8\)），任意两点之间的边权重等于两顶点编号的差的绝对值。例如，顶点 \(3\) 和 \(7\) 之间的边权重为 \(|7-3| = 4\)。该图的最小生成树总权重是多少？
- A. \(9\)
- B. \(8\)
- C. \(7\)
- D. \(10\)
答案与解析
答案：C
权 1 的边是相邻编号对 \((1,2),\dots,(7,8)\)，共 7 条恰好连成生成树、总权 7——不存在权更小的边，7 条权 1 已是最优下界。
易错小结¶
- 非连通图边数上限 \(\binom{n-1}{2}\)；由边数反推最少点数找最小 n 使 \(\binom{n-1}{2} \ge m\)（2019/2021 两次原题）；
- 二分图最多边 \(\lfloor n^2/4 \rfloor\) 要均分；可二染 ⟺ 无奇环——树天然可染；
- 欧拉回路 = 连通 + 全偶度；欧拉路径 = 连通 + 恰 0 或 2 奇点；边数奇偶无关；
- 强连通是互达不是两两相邻（2022 反向词陷阱）；
- 标号点 n 元环 \((n-1)!/2\)；\(K_n\) 的 4 环 \(3\binom{n}{4}\)；
- DAG 拓扑序计数无公式（2025“以上都不对”）；MST 恒 n−1 条边；边权 \(|i-j|\) 的 \(K_n\) MST 总权 \(n-1\)；
- 树重心 1 或 2 个；奇数点必唯一（2023）；
- 稀疏图 \(m=\Theta(n)\) 选型：逐项代入比阶（2023），注意 \(\sqrt{\log n\log\log n} < \log n\)。