第1章　組合問(wèn)題與組合技術(shù)引論1
1.1　工程完成時(shí)間的問(wèn)題2
1.2　匹配問(wèn)題10
1.3　背包問(wèn)題16
1.4　算法及其效率23
歷史注記35
補(bǔ)充習(xí)題37
計(jì)算機(jī)題39
推薦讀物40
第2章　集合、關(guān)系和函數(shù)41
2.1　集合運(yùn)算41
2.2　等價(jià)關(guān)系47
*2.3　偏序關(guān)系54
2.4　函數(shù)65
2.5　數(shù)學(xué)歸納法76
2.6　應(yīng)用84
歷史注記93
補(bǔ)充習(xí)題95
計(jì)算機(jī)題98
推薦讀物98
第3章　編碼理論99
3.1　同余100
3.2　歐幾里得算法106
3.3　RSA方法113
3.4　檢錯(cuò)碼和糾錯(cuò)碼122
3.5　矩陣碼132
3.6　單糾錯(cuò)矩陣碼140
歷史注記147
補(bǔ)充習(xí)題149
計(jì)算機(jī)題152
推薦讀物153
第4章　圖154
4.1　圖及其表示154
4.2　通路和回路164
4.3　最短通路和距離181
4.4　圖著色193
4.5　有向圖和有向多重圖202
歷史注記219
補(bǔ)充習(xí)題220
計(jì)算機(jī)題226
推薦讀物227
第5章　樹228
5.1　樹的性質(zhì)228
5.2　生成樹238
5.3　深度優(yōu)先搜索253
5.4　根樹266
5.5　二叉樹和遍歷274
5.6　最優(yōu)二叉樹和二叉搜索樹287
歷史注記306
補(bǔ)充習(xí)題308
計(jì)算機(jī)題311
推薦讀物312
第6章　匹配313
6.1　相異代表系313
6.2　圖中的匹配319
6.3　匹配算法327
6.4　算法的應(yīng)用337
6.5　匈牙利方法346
歷史注記354
補(bǔ)充習(xí)題355
計(jì)算機(jī)題357
推薦讀物357
第7章　網(wǎng)絡(luò)流358
7.1　流和割358
7.2　流增廣算法369
7.3　最大流最小割定理382
7.4　流和匹配389
歷史注記397
補(bǔ)充習(xí)題397
計(jì)算機(jī)題400
推薦讀物401
第8章　計(jì)數(shù)技術(shù)402
8.1　帕斯卡三角形和二項(xiàng)式定理402
8.2　3個(gè)基本原理406
8.3　排列和組合416
8.4　允許重復(fù)的排列和組合421
8.5　概率428
*8.6　容斥原理434
*8.7　排列和r組合的生成445
歷史注記452
補(bǔ)充習(xí)題453
計(jì)算機(jī)題456
推薦讀物457
第9章　遞推關(guān)系與生成函數(shù)458
9.1　遞推關(guān)系458
9.2　迭代法470
9.3　常系數(shù)線性差分方程482
*9.4　用遞推關(guān)系分析算法的效率494
9.5　用生成函數(shù)計(jì)數(shù)506
9.6　生成函數(shù)的代數(shù)513
歷史注記523
補(bǔ)充習(xí)題524
計(jì)算機(jī)題527
推薦讀物528
第10章　組合電路和有限狀態(tài)機(jī)529
10.1　邏輯門529
10.2　構(gòu)造組合電路538
10.3　卡諾圖546
10.4　有限狀態(tài)機(jī)560
歷史注記569
補(bǔ)充習(xí)題570
計(jì)算機(jī)題573
推薦讀物573
附錄A　邏輯和證明簡(jiǎn)介574
A.1　命題和聯(lián)結(jié)詞574
A.2　邏輯等價(jià)583
A.3　證明的方法587
歷史注記593
補(bǔ)充習(xí)題594
推薦讀物596
附錄B　矩陣597
歷史注記604
附錄C　本書中的算法607
參考文獻(xiàn)613
奇數(shù)號(hào)習(xí)題答案618
圖片來(lái)源658


Contents
1AN INTRODUCTION TO COMBINATORIAL PROBLEMS AND TECHNIQUES1
1.1 The Time to Completea Project 2
1.2 A Matching Problem 10
1.3 A Knapsack Problem 16
1.4 Algorithms and Their 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 and Their Representations 154
4.2 Pathsand 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-Cut Theorem 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 The Algebra 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 LOGIC AND 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 IN THIS BOOK 607
BIBLIOGRAPHY 613
ANSWERS TO ODD-NUMBERED EXERCISES 618
PHOTO CREDITS 658