随着计算机技术的日益发展、计算机应用的日益拓广、计算机软件的日益丰富、计算机 理论研究的日趋完善，产生和发展了计算机科学。离散数学不仅是研究计算机科学的有力工具和方法，同时也是研究一般信息科学的基本数学工具。其基本理论涉及：集合论、代数学、数理逻辑、图论、组合数学、数论、概率论等学科。


3 Graphs, Part I: Basic Notions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
3.1 Why Graphs? Some Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
3.2 Directed Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
3.3 Path in Digraphs; Strongly Connected Components . . . . . . . . . . . . . . 171
3.4 Undirected Graphs, Chains, Cycles, Connectivity . . . . . . . . . . . . . . . . 182
3.5 Trees and Arborescences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
3.6 Minimum (or Maximum) Weight Spanning Trees . . . . . . . . . . . . . . . . 194
3.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
4 Some Counting Problems; Multinomial Coefficients . . . . . . . . . . . . . . . . 205
4.1 Counting Permutations and Functions . . . . . . . . . . . . . . . . . . . . . . . . . 205
4.2 Counting Subsets of Size k; Multinomial Coefficients . . . . . . . . . . . . 208
4.3 Some Properties of the Binomial Coefficients . . . . . . . . . . . . . . . . . . . 217
4.4 The Principle of Inclusion–Exclusion . . . . . . . . . . . . . . . . . . . . . . . . . . 229
4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255
5 Partial Orders, GCDs, RSA, Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
5.1 Partial Orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
5.2 Lattices and Tarski’s Fixed-Point Theorem . . . . . . . . . . . . . . . . . . . . . 263
5.3 Well-Founded Orderings and Complete Induction . . . . . . . . . . . . . . . 269
5.4 Unique Prime Factorization in Z and GCDs . . . . . . . . . . . . . . . . . . . . 278
5.5 Dirichlet’s Diophantine Approximation Theorem . . . . . . . . . . . . . . . . 288
5.6 Equivalence Relations and Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . 291
5.7 Transitive Closure, Reflexive and Transitive Closure . . . . . . . . . . . . . 295
5.8 Fibonacci and Lucas Numbers; Mersenne Primes . . . . . . . . . . . . . . . . 296
5.9 Public Key Cryptography; The RSA System . . . . . . . . . . . . . . . . . . . . 309
5.10 Correctness of The RSA System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
5.11 Algorithms for Computing Powers and Inverses Modulo m . . . . . . . . 318
5.12 Finding Large Primes; Signatures; Safety of RSA. . . . . . . . . . . . . . . . 322
5.13 Distributive Lattices, Boolean Algebras, Heyting Algebras . . . . . . . . 327
5.14 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362
6 Graphs, Part II: More Advanced Notions . . . . . . . . . . . . . . . . . . . . . . . . . 365
6.1 Γ -Cycles, Cocycles, Cotrees, Flows, and Tensions . . . . . . . . . . . . . . . 365
6.2 Incidence and Adjacency Matrices of a Graph . . . . . . . . . . . . . . . . . . . 381
6.3 Eulerian and Hamiltonian Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386
6.4 Network Flow Problems; The Max-Flow Min-Cut Theorem . . . . . . . 391
6.5 Matchings, Coverings, Bipartite Graphs . . . . . . . . . . . . . . . . . . . . . . . . 409
6.6 Planar Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418
6.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 439
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447


References
1. Herbert B. Enderton. Elements of Set Theory. New York: Academic Press, first edition, 1977.
2. Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. Concrete Mathematics: A Foundation
For Computer Science. Reading, MA: Addison Wesley, second edition, 1994.
3. L. Lov´asz, J. Pelik´an, and K. Vesztergombi. Discrete Mathematics. Elementary and Beyond.
Undergraduate Texts in Mathematics. New York: Springer, first edition, 2003.
4. Michael Mitzenmacher and Eli Upfal. Probability and Computing. Randomized Algorithms
and Probabilistic Analysis. Cambridge, UK: Cambridge University Press, first edition, 2005.
5. Patrick Suppes. Axiomatic Set Theory. New York: Dover, first edition, 1972.
6. D. van Dalen. Logic and Structure. Universitext. New York: Springer Verlag, second edition,
1980.