离散数学与图论（英文版·原书第3版）

第0章　证明1
0.1　复合命题2
0.2　数学中的证明10
练习题17
第1章　逻辑19
1.1　真值表19
1.2　命题代数23
1.3　逻辑论证30
练习题36
第2章　集合与关系38
2.1　集合38
2.2　集合上的运算43
2.3　二元关系51
2.4　等价关系57
2.5　偏序64
练习题70
第3章　函数72
3.1　基本术语72
3.2　逆与合成80
3.3　一一对应与集合的基数88
练习题96
第4章　整数98
4.1　除法算法98
4.2　整除性与欧几里得算法105
4.3　素数114
4.4　同余125
4.5　同余的应用135
练习题145
第5章　归纳法与递归147
5.1　数学归纳法147
5.2　递归定义的序列160
5.3　求解递推关系式：特征多项式170
5.4　求解递推关系式：生成函数176
练习题182
第6章　计数原理184
6.1　容斥原理184
6.2　加法和乘法规则192
6.3　鸽巢原理199
练习题204
第7章　排列与组合205
7.1　排列205
7.2　组合210
7.3　初等概率216
7.4　概率论224
7.5　可重复的排列组合231
7.6　错排236
7.7　二项式定理239
练习题245
第8章　算法247
8.1　什么是算法247
8.2　复杂度253
8.3　搜索与排序265
8.4　排列组合的枚举276
练习题280
第9章　图281
9.1　引人入胜的简介281
9.2　定义与基本性质288
9.3　同构296
练习题301
第10章　路径与回路304
10.1　欧拉回路304
10.2　哈密顿回路311
10.3　邻接矩阵319
10.4　短路径算法326
练习题336
第11章　路径与回路的应用339
11.1　中国邮递员问题339
11.2　有向图344
11.3　RNA链352
11.4　锦标赛356
11.5　调度问题361
练习题367
第12章　树370
12.1　树及其性质370
12.2　生成树379
12.3　小生成树算法384
12.4　无环有向图与Bellman算法393
12.5　深度优先搜索398
12.6　单行道问题403
练习题409
第13章　平面图与着色411
13.1　平面图411
13.2　图着色419
13.3　回路测试与公用设施设计427
练习题435
第14章　流–小割集定理438
14.1　流与割集438
14.2　构造流445
14.3　应用450
14.4　匹配454
练习题460
附录AA-1
是非题及部分练习题的解题过程S-1
词汇表G-1
索引I-1
Contents
0 Yes,There Are Proofs!1
0.1 Compound Statements2
0.2 Proofs in Mathematics10
Review Exercises17
1 Logic19
1.1 Truth Tables19
1.2 The Algebra of Propositions23
1.3 Logical Arguments30
Review Exercises36
2 Sets and Relations38
2.1 Sets38
2.2 Operations on Sets43
2.3 Binary Relations51
2.4 Equivalence Relations57
2.5 Partial Orders64
Review Exercises70
3 Functions72
3.1 Basic Terminology72
3.2 Inverses and Composition80
3.3 One-to-One Correspondence and the Cardinality of a Set88
Review Exercises96
4 The Integers98
4.1 The Division Algorithm98
4.2 Divisibility and the Euclidean Algorithm105
4.3 Prime Numbers114
4.4 Congruence125
4.5 Applications of Congruence135
Review Exercises145
5 Induction and Recursion147
5.1 Mathematical Induction147
5.2 Recursively Defined Sequences160
5.3 Solving Recurrence Relations; The Characteristic Polynomial170
5.4 Solving Recurrence Relations; Generating Functions176
Review Exercises182
6 Principles of Counting184
6.1 The Principle of Inclusion-Exclusion184
6.2 The Addition and Multiplication Rules192
6.3 The Pigeonhole Principle199
Review Exercises204
7 Permutations and Combinations205
7.1 Permutations205
7.2 Combinations210
7.3 Elementary Probability216
7.4 Probability Theory224
7.5 Repetitions231
7.6 Derangements236
7.7 The Binomial Theorem239
Review Exercises245
8 Algorithms247
8.1 What Is an Algorithm?247
8.2 Complexity253
8.3 Searching and Sorting265
8.4 Enumeration of Permutations and Combinations276
Review Exercises280
9 Graphs281
9.1 A Gentle In troduction281
9.2 Definitions and Basic Properties288
9.3 Isomorphism296
Review Exercises 301
10 Paths and Circuits304
10.1 EulerianCircuits304
10.2 Hamiltonian Cycles311
10.3 The Adjacency Matrix319
10.4 Shortest Path Algorithms326
Review Exercises336
11 Applicationsof Paths and Circuits339
11.1 The Chinese Postman Problem339
11.2 Digraphs344
11.3 RNA Chains352
11.4 Tournaments356
11.5 Scheduling Problems361
Review Exercises367
12 Trees370
12.1 Trees and the irProperties370
12.2 Spanning Trees379
12.3 Minimum Spanning Tree Algorithms384
12.4 Acyclic Digraphs and Bellman's Algorithm393
12.5 Depth-FirstSearch398
12.6 The One-Way Street Problem403
Review Exercises409
13 Planar Graphs and Colorings411
13.1 Planar Graphs411
13.2 Coloring Grap