Applied combinatorics
著者
書誌事項
Applied combinatorics
Wiley, c2012
6th ed
電子リソースにアクセスする 全1件
大学図書館所蔵 全6件
  青森
  岩手
  宮城
  秋田
  山形
  福島
  茨城
  栃木
  群馬
  埼玉
  千葉
  東京
  神奈川
  新潟
  富山
  石川
  福井
  山梨
  長野
  岐阜
  静岡
  愛知
  三重
  滋賀
  京都
  大阪
  兵庫
  奈良
  和歌山
  鳥取
  島根
  岡山
  広島
  山口
  徳島
  香川
  愛媛
  高知
  福岡
  佐賀
  長崎
  熊本
  大分
  宮崎
  鹿児島
  沖縄
  韓国
  中国
  タイ
  イギリス
  ドイツ
  スイス
  フランス
  ベルギー
  オランダ
  スウェーデン
  ノルウェー
  アメリカ
注記
Includes bibliographical references and index
内容説明・目次
内容説明
The new 6th edition of Applied Combinatorics builds on the previous editions with more in depth analysis of computer systems in order to help develop proficiency in basic discrete math problem solving. As one of the most widely used book in combinatorial problems, this edition explains how to reason and model combinatorically while stressing the systematic analysis of different possibilities, exploration of the logical structure of a problem, and ingenuity. Although important uses of combinatorics in computer science, operations research, and finite probability are mentioned, these applications are often used solely for motivation. Numerical examples involving the same concepts use more interesting settings such as poker probabilities or logical games. This book is designed for use by students with a wide range of ability and maturity (sophomores through beginning graduate students). The stronger the students, the harder the exercises that can be assigned. The book can be used for one-quarter, two-quarter, or one-semester course depending on how much material is used.
目次
Prelude xi
Part One Graph Theory 1
Chapter 1 Elements of Graph Theory 3
1.1 Graph Models 3
1.2 Isomorphism 14
1.3 Edge Counting 24
1.4 Planar Graphs 31
1.5 Summary and References 44
Supplementary Exercises 45
Chapter 2 Covering Circuits and Graph Coloring 49
2.1 Euler Cycles 49
2.2 Hamilton Circuits 56
2.3 Graph Coloring 68
2.4 Coloring Theorems 77
2.5 Summary and References 86
Supplement: Graph Model for Instant Insanity 87
Supplement Exercises 92
Chapter 3 Trees and Searching 93
3.1 Properties of Trees 93
3.2 Search Trees and Spanning Trees 103
3.3 The Traveling Salesperson Problem 113
3.4 Tree Analysis of Sorting Algorithms 121
3.5 Summary and References 125
Chapter 4 Network Algorithms 127
4.1 Shortest Paths 127
4.2 Minimum Spanning Trees 131
4.3 Network Flows 135
4.4 Algorithmic Matching 153
4.5 The Transportation Problem 164
4.6 Summary and References 174
Part Two Enumeration 177
Chapter 5 General Counting Methods for Arrangements and Selections 179
5.1 Two Basic Counting Principles 179
5.2 Simple Arrangements and Selections 189
5.3 Arrangements and Selections with Repetitions 206
5.4 Distributions 214
5.5 Binomial Identities 226
5.6 Summary and References 236
Supplement: Selected Solutions to Problems in Chapter 5 237
Chapter 6 Generating Functions 249
6.1 Generating Function Models 249
6.2 Calculating Coefficients of Generating Functions 256
6.3 Partitions 266
6.4 Exponential Generating Functions 271
6.5 A Summation Method 277
6.6 Summary and References 281
Chapter 7 Recurrence Relations 283
7.1 Recurrence Relation Models 283
7.2 Divide-and-Conquer Relations 296
7.3 Solution of Linear Recurrence Relations 300
7.4 Solution of Inhomogeneous Recurrence Relations 304
7.5 Solutions with Generating Functions 308
7.6 Summary and References 316
Chapter 8 Inclusion-Exclusion 319
8.1 Counting with Venn Diagrams 319
8.2 Inclusion-Exclusion Formula 328
8.3 Restricted Positions and Rook Polynomials 340
8.4 Summary and Reference 351
Part Three Additional Topics 353
Chapter 9 Polya's Enumeration Formula 355
9.1 Equivalence and Symmetry Groups 355
9.2 Burnside's Theorem 363
9.3 The Cycle Index 369
9.4 Polya's Formula 375
9.5 Summary and References 382
Chapter 10 Games with Graphs 385
10.1 Progressively Finite Games 385
10.2 Nim-Type Games 393
10.3 Summary and References 400
Postlude 401
Appendix 415
A.1 Set Theory 415
A.2 Mathematical Induction 420
A.3 A Little Probability 423
A.4 The Pigeonhole Principle 427
A.5 Computational Complexity and NP-Completeness 430
Glossary of Counting and Graph Theory Terms 435
Bibliography 439
Solutions To Odd-Numbered Problems 441
Index 475
「Nielsen BookData」 より