本书是一本优秀的离散数学入门教材。书中充分考虑到初学者的需要，内容、例题、习题都经过精心的挑选和组织，讲解细致，循序渐进，实例贴近日常生活或计算机应用。本书注重算法，且算法描述独立于某种具体的编程语言。教师可根据学生的层次和兴趣来灵活拓展和组织讲解内容。本书可作为计算机专业或其他相关专业的离散数学教材或教学参考书，也可作为自学者的参考用书。

本书凝聚了作者多年的研究成果和实践经验，是一本优秀的离散数学入门教材。本书充分考虑到初学者的需要，内容、例题、习题都经过精心的挑选和组织，讲解细致，循序渐进，实例贴近日常生活或计算机应用。本书注重算法，且算法描述独立于某种具体的编程语言。教师可根据学生的层次和兴趣来灵活拓展和组织讲解内容。本书可作为计算机专业或其他相关专业的离散数学教材或教学参考书，也可作为自学者的参考用书。

PREFACE  111

TO THE STUDENT viii

1 AN INTRODUCTION TO COMBINATORIAL PROBLEMS AND

TECHNIQUES 1

1.1 TheTime to Complete a Project 2

1.2 A Matching Problem 10

1.3 A Knapsack Problem 16

1.4 Algorithms andTheir Efficiency 23

    Historical Notes 35

    Supplementary Exercises 37

    Computer Projects 39

    Suggested Readings 40

2 SETS, RELATIONS, AND FUNCTIONS 41

2.1 Set Operations 41

2.2 Equivalence Relations 47

2.3* Partial Ordering Relations 54

2.4 Functions 65

2.5 Mathematical Induction 76

2.6 Applications 84

    Historical Notes 93

    Supplementary Exercises 95

    Computer Projects 98

    Suggested Readings 98

3 CODING THEORY 99

3.1 Congruence 100

3.2 The Euclidean Algorithm 106

3.3 The RSA Method 113

3.4 Error-Detecting and Error-Correcting Codes 122

3.5 Matrix Codes 132

3.6 Matrix Codes that Correct All Single-Digit Errors 140

    Historical Notes 147

    Supplementary Exercises 149

    Computer Projects 152

    Suggested Readings 153

4 GRAPHS 154

4.1 Graphs andTheir Representations 154

4.2 Paths and Circuits 164

4.3 Shortest Paths and Distance 181

4.4 Coloringa Graph 193

4.5 Directed Graphs and Multigraphs 202

    Historical Notes 219

    Supplementary Exercises 220

    Computer Projects 226

    Suggested Readings 227

5 TREES 228

5.1 Properties of Trees 228

5.2 Spanning Trees 238

5.3 Depth-First Search 253

5.4 Rooted Trees 266

5.5 Binary Trees and Traversals 274

5.6 Optimal Binary Trees and Binary Search Trees 287

    Historical Notes 306

    Supplementary Exercises 308

    Computer Projects 311

    Suggested Readings 312

6 MATCHING 313

6.1 Systems of Distinct Representatives 313

6.2 Matchings in Graphs 319

6.3 A Matching Algorithm 327

6.4 Applications of the Algorithm 337

6.5 The Hungarian Method 346

    Historical Notes 354

    Supplementary Exercises 355

    Computer Projects 357

    Suggested Readings 357

7 NETWORK FLOWS 358

7.1 Flows and Cuts 358

7.2 A Flow Augmentation Algorithm 369

7.3 The Max-Flow Min-CutTheorem 382

7.4 Flows and Matchings 389

    Historical Notes 397

    Supplementary Exercises 397

    Computer Projects 400

    Suggested Readings 401

8 COUNTING TECHNIQUES 402

8.1 Pascal's Triangle and the Binomial Theorem 402

8.2 Three Fundamental Principles 406

8.3 Permutations and Combinations 416

8.4 Arrangements and Selections with Repetitions 421

8.5 Probability 428

8.6* The Principle of Inclusion-Exclusion 434

8.7* Generating Permutations and r-Combinations 445

    Historical Notes 452

    Supplementary Exercises 453

    Computer Projects 456

    Suggested Readings 457

9 RECURRENCE RELATIONS AND GENERATING FUNCTIONS 458

 9.1 Recurrence Relations 458

 9.2 The Method of Iteration 470

 9.3 Linear Difference Equations with Constant Coefficients 482

 9.4* Analyzing the Efficiency of Algorithms with Recurrence

     Relations 494

 9.5 Counting with Generating Functions 506

 9.6 TheAIgebra of Generating Functions 513

     Historical Notes 523

     Supplementary Exercises 524

    Computer Projects 527

     Suggested Readings 528

10 COMBINATORIAL CIRCUITS AND FINITE STATE MACHINES 529

 10.1 Logical Gates 529

 10.2 Creating Combinatorial Circuits 538

 10.3 Karnaugh Maps 546

 10.4 Finite State Machines 560

     Historical Notes 569

    Supplementary Exercises 570

    Computer Projects 573

    Suggested Readings 573

A AN INTRODUCTION TO LOGICAND PROOF 574

 A.1 Statements and Connectives 574

 A.2 Logical Equivalence 583

 A.3 Methods of Proof 587

    Historical Notes 593

    Supplementary Exercises 594

    Suggested Readings 596

B MATRICES 597

    Historical Notes 604

C THE ALGORITHMS INTHIS BOOK 607

BIBLIOGRAPHY 613

ANSWERS TO ODD-NUMBERED EXERCISES 618

PHOTO CREDITS 658

INDEX 659