离散数学 第4版

目录 1

第1章 组合问题与技术引论 1

1.1 工程时间问题 2

1.1.1 问题 2

1.1.2 分析 3

1.1.3 关键路径分析 5

1.1.4 一个建筑的例子 5

练习1.1 6

1.2 匹配问题 9

1.2.1 问题 9

1.2.2 分析 10

1.2.3 排列 11

1.2.4 航空公司问题的解决方案的实用性 12

练习1.2 13

1.3 背包问题 14

1.3.1 问题 14

1.3.2 分析 16

1.3.3 问题的再次考察 17

练习1.3 18

1.4 算法及其效率 19

1.4.1 算法的比较 19

1.4.2 多项式求值 20

1.4.3 子集生成算法 23

1.4.4 冒泡排序 25

练习1.4 27

历史注记 29

补充练习 30

计算机题 33

推荐读物 33

第2章 集合、关系和函数 35

2.1 集合运算 35

练习2.1 39

2.2 等价关系 40

练习2.2 44

2.3 同余关系 45

练习2.3 49

2.4 部分序关系 50

2.4.1 哈斯图 55

2.4.2 拓扑排序 56

练习2.4 58

2.5 函数 60

练习2.5 67

2.6 数学归纳法 69

练习2.6 74

2.7 应用 77

练习2.7 81

历史注记 84

补充练习 85

计算机题 89

推荐读物 89

3.1 图及其表示 91

第3章 图 91

3.1.1 图的其他表示 93

3.1.2 同构 94

练习3.1 97

3.2 通路和回路 100

3.2.1 欧拉回路和欧拉通路 103

3.2.2 哈密顿回路和通路 106

练习3.2 110

3.3 最短通路和距离 116

3.3.1 带权图 118

3.3.2 通路的数目 122

练习3.3 123

3.4 图着色 126

练习3.4 131

3.5 有向图和有向多重图 134

3.5.1 有向图的表示 135

3.5.2 有向多重图 136

3.5.3 有向欧拉回路和通路 139

3.5.4 有向哈密顿回路和通路 140

练习3.5 142

历史注记 149

补充练习 150

计算机题 155

推荐读物 156

4.1 树的性质 157

第4章 树 157

练习4.1 162

4.2 生成树 165

4.2.1 广度优先搜索 167

4.2.2 最小生成树和最大生成树 169

4.2.3 普里姆算法的证明 173

练习4.2 174

4.3 深度优先搜索 179

回溯 184

练习4.3 186

4.4 根树 189

练习4.4 194

4.5.1 表达式树 197

4.5 二叉树和遍历 197

4.5.2 前序遍历 199

4.5.3 后序遍历 201

4.5.4 中序遍历 203

练习4.5 205

4.6 最优二叉树和二叉搜索树 207

4.6.1 最优二叉树 207

4.6.2 二叉搜索树 214

练习4.6 219

历史注记 224

补充练习 225

计算机题 228

推荐读物 229

5.1 相异代表系 230

第5章 匹配 230

练习5.1 233

5.2 图中的匹配 235

5.2.1 偶图的矩阵 237

5.2.2 覆盖 238

练习5.2 240

5.3 匹配算法 242

5.3.1 运用算法于最大独立集 245

5.3.2 分配课程 247

练习5.3 249

5.4 算法的应用 252

5.4.1 考尼格定理 253

5.4.2 霍尔定理的证明 254

5.4.3 瓶颈问题 256

练习5.4 257

5.5 匈牙利方法 259

练习5.5 265

历史注记 266

补充练习 267

计算机题 269

推荐读物 270

第6章 网络流 271

6.1 流和割 271

练习6.1 278

6.2 流增广算法 280

练习6.2 287

6.3 最大流最小割定理 290

练习6.3 294

6.4 流和匹配 296

练习6.4 300

历史注记 303

补充练习 304

计算机题 307

推荐读物 308

第7章 计数技术 309

7.1 帕斯卡三角形和二项式定理 309

练习7.1 312

7.2 三个基本原理 313

练习7.2 317

7.3 排列和组合 320

练习7.3 323

7.4 允许重复的排列和组合 324

练习7.4 328

7.5 概率 330

练习7.5 333

＊7.6 容斥原理 335

练习7.6 341

＊7.7 排列和r-组合的生成 344

练习7.7 349

历史注记 350

补充练习 351

计算机题 354

推荐读物 355

第8章 递推关系与生成函数 356

8.1 递推关系 356

练习8.1 363

8.2 迭代法 365

练习8.2 372

8.3 常系数线性差分方程 374

练习8.3 381

＊8.4 用递推关系分析算法的效率 383

8.4.1 分而治之算法 385

8.4.2 排序算法的效率 391

练习8.4 391

8.5 用生成函数计数 393

8.5.1 生成函数 394

8.5.2 形式幂级数 395

练习8.5 398

8.6 生成函数的代数 399

练习8.6 406

历史注记 407

补充练习 408

计算机题 412

推荐读物 412

第9章 组合电路和有限状态机 413

9.1 逻辑门 413

练习9.1 419

9.2 构造组合电路 422

练习9.2 426

9.3 卡诺图 429

练习9.3 438

9.4 有限状态机 441

9.4.1 奇偶校验机 442

9.4.2 带输出的有限状态机 444

练习9.4 446

历史注记 449

补充练习 450

计算机题 452

推荐读物 453

附录A 逻辑和证明简介 454

A.1 命题和联结词 454

练习A.1 460

A.2 逻辑等价 461

练习A.2 464

A.3 证明的方法 465

练习A.3 469

历史注记 470

补充练习 471

推荐读物 473

附录B 矩阵 474

历史注记 479

附录C 本书中的算法 481

附录D 各章奇数练习题答案 486

参考书目 531

历史注记的参考书目 535