离散数学：思维与挑战

勘 误 表

（衷心感谢指出错误的各位老师、同学）

（如果您发现了新的错误，欢迎联系我：姓名全拼@南京大学域名）

1. 第62页，例2.4.4：$T(n)$中的求和上界应为$n-1$；$R(n)$中的求和上界应为$n+1$；初始条件应当增加$T(0)=0$。

2. 第63页中间，“现在我们将最初的第一个等式重写为"：求和上界应当为$n-1$。在下一句“其中”后面，应增加“$U(0)=0$，且对$n \geq 1$，”

3. 第65页，定义2.5.2，应当增加脚注：这里最大值可能不唯一，但最大值之间在渐进意义上是等价的。

4. 第66页，例2.5.3解答的倒数第2行：公式中应当删去$\sqrt{\log M}+$。

5. 第128页，命题4.4.4证明的第3段第1行：“矩阵中的前$q-2$列”应为“矩阵中的前$p-2$列”。

6. 第130页，习题集9上面一行：“任何对它们进行区分的可以多项式时间算法”应为“任何可以对它们进行区分的多项式时间算法”。

7. 第153页，定理5.1.1：“Erdos-Gallai圈长度定理”；“Erdos-Gallai Theorem of Circuit Length”应为“Erdos-Gallai Theorem of Cycle Length”；“长度至少$k+1$的回路”应为“长度至少$k+1$的圈”。

8. 第154页，第1行：“回想例5.2”应为“回想例5.1.2”。

9. 第159页，习题182：第1行中“恰好关联$2^n$条白边”应为“恰好关联$2^n-1$条白边”；第2行中“恰好关联$2^n-1$条白边”应为“恰好关联$2^n-2$条白边”。

10. 第167页，第7行：“我们没有一个好的答案，但对于完全图”应改为“我们可以使用比如说基于Kirchhoff矩阵树定理的算法来计数，但已超出本书范围。对于完全图而言，”。

11. 第172页，习题191：“$G[V_1]$的边数和$G[V_2]$的边数”应改为"与$V_1$或$V_2$中顶点关联的边数"。

12. 第172页，习题193，应当完全改写为：假设$T$是一棵含有至少$4$个顶点的树，而$F$为一些子树的集合。对任意$r,s,t \in F$，都能找到三棵子树的共同顶点。定义$C_F(u)$为含有顶点$u$的$F$中子树数。求$\max_u C_F(u)$的最小值。

13. 第215页，例6.4.3：第一段只保留第一句话，其余全部删去。

14. 第218页，最后一行：“与第六类似”应改为“基于效用函数的连续性”。