离散数学与图论(英文版原书第3版)/经典原版书库

内容经过多年的教学实践检验，可用于两门一学期课程。一门是为（没有图论基础的）大二学生开设的离散数学课程，另一门是为大三学生开设的应用图论课程。本书*后提供了1200多题的题解。和其他教科书相比，本书更基础一些，编排上也更易于理解一些。除了10.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 Graphs419 13.3 Circuit Testing and Facilities Design427 Review Exercises435 14 The Max Flow-Min Cut Theorem438 14.1 FlowsandCuts438 14.2 Constructing Maximal Flows445 14.3 Applications450 14.4 Matchings454 Review Exercises460 AppendixA-1 SolutionstoTrue/FalseQuestionsandSelectedExercises S-1 Glossary G-1 Index I-1