图论导引 第2版 英文版pdf电子书版本下载

点此进入-本书在线PDF格式电子书下载【推荐-云解压-方便快捷】直接下载PDF格式图书。移动端-PC端通用
种子下载[BT下载速度快] 温馨提示：（请使用BT下载软件FDM进行下载）软件下载地址页 直链下载[便捷但速度慢]   [在线试读本书]   [在线获取解压码]

图论导引 第2版 英文版PDF格式电子书版下载

下载的文件为RAR压缩包。需要使用解压软件进行解压得到PDF格式图书。

建议使用BT下载工具Free Download Manager进行下载,简称FDM(免费,没有广告,支持多平台）。本站资源全部打包为BT种子。所以需要使用专业的BT下载软件进行下载。如 BitComet qBittorrent uTorrent等BT下载工具。迅雷目前由于本站不是热门资源。不推荐使用！后期资源热门了。安装了迅雷也可以迅雷进行下载！

（文件页数 要大于 标注页数，上中下等多册电子书除外）

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

Chapter 1 Fundamental Concepts 1

1.1 What Is a Graph？ 1

The Definition 1

Graphs as Models 3

Matrices and Isomorphism 6

Decomposition and Special Graphs 11

Exercises 14

1.2 Paths,Cycles,and Trails 19

Connection in Graphs 20

Bipartite Graphs 24

Eulerian Circuits 26

Exercises 31

1.3 Vertex Degrees and Counting 34

Counting and Bijections 35

Extremal Problems 38

Graphic Sequences 44

Exercises 47

1.4 Directed Graphs 53

Definitions and Examples 53

Vertex Degrees 58

Eulerian Digraphs 60

Orientations and Tournaments 61

Exercises 63

Chapter 2 Trees and Distance 67

2.1 Basic Properties 67

Properties of Trees 68

Distance in Trees and Graphs 70

Disjoint Spanning Trees(optional) 73

Exercises 75

2.2 Spanning Trees and Enumeration 81

Enumeration of Trees 81

Spanning Trees in Graphs 83

Decomposition and Graceful Labelings 87

Branchings and Eulerian Digraphs(optional) 89

Exercises 92

2.3 Optimization and Trees 95

Minimum Spanning Tree 95

Shortest Paths 97

Trees in Computer Science(optional) 100

Exercises 103

Chapter 3 Matchings and Factors 107

3.1 Matchings and Covers 107

Maximum Matchings 108

Hall's Matching Condition 110

Min-Max Theorems 112

Independent Sets and Covers 113

Dominating Sets(optional) 116

Exercises 118

3.2 Algorithms and Applications 123

Maximum Bipartite Matching 123

Weighted Bipartite Matching 125

Stable Matchings(optional) 130

Faster Bipartite Matching(optional) 132

Exercises 134

3.3 Matchings in General Graphs 136

Tutte's 1-factor Theorem 136

f-factors of Graphs(optional) 140

Edmonds'Blossom Algorithm(optional) 142

Exercises 145

Chapter 4 Connectivity and Paths 149

4.1 Cuts and Connectivity 149

Connectivity 149

Edge-connectivity 152

Blocks 155

Exercises 158

4.2 k-connected Graphs 161

2-connected Graphs 161

Connectivity of Digraphs 164

k-connected and k-edge-connected Graphs 166

Applications of Menger's Theorem 170

Exercises 172

4.3 Network Flow Problems 176

Maximum Network Flow 176

Integral Flows 181

Supplies and Demands(optional) 184

Exercises 188

Chapter 5 Coloring of Graphs 191

5.1 Vertex Colorings and Upper Bounds 191

Definitions and Examples 191

Upper Bounds 194

Brooks'Theorem 197

Exercises 199

5.2 Structure of k-chromatic Graphs 204

Graphs with Large Chromatic Number 205

Extremal Problems and Turán's Theorem 207

Color-Critical Graphs 210

Forced Subdivisions 212

Exercises 214

5.3 Enumerative Aspects 219

Counting Proper Colorings 219

Chordal Graphs 224

A Hint of Perfect Graphs 226

Counting Acyclic Orientations(optional) 228

Exercises 229

Chapter 6 Planar Graphs 233

6.1 Embeddings and Euler's Formula 233

Drawings in the Plane 233

Dual Graphs 236

Euler's Formula 241

Exercises 243

6.2 Characterization of Planar Graphs 246

Preparation for Kuratowski's Theorem 247

Convex Embeddings 248

Planarity Testing(optional) 252

Exercises 255

6.3 Parameters of Planarity 257

Coloring of Planar Graphs 257

Crossing Number 261

Surfaces of Higher Genus(optional) 266

Exercises 269

Chapter 7 Edges and Cycles 273

7.1 Line Graphs and Edge-coloring 273

Edge-colorings 274

Characterization of Line Graphs(optional) 279

Exercises 282

7.2 Hamiltonian Cycles 286

Necessary Conditions 287

Sufficient Conditions 288

Cycles in Directed Graphs(optional) 293

Exercises 294

7.3 Planarity,Coloring,and Cycles 299

Tait's Theorem 300

Grinberg's Theorem 302

Snarks(optional) 304

Flows and Cycle Covers(optional) 307

Exercises 314

Chapter 8 Additional Topics(optional) 319

8.1 Perfect Graphs 319

The Perfect Graph Theorem 320

Chordal Graphs Revisited 323

Other Classes of Perfect Graphs 328

Imperfect Graphs 334

The Strong Perfect Graph Conjecture 340

Exercises 344

8.2 Matroids 349

Hereditary Systems and Examples 349

Properties of Matroids 354

The Span Function 358

The Dual of a Matroid 360

Matroid Minors and Planar Graphs 363

Matroid Intersection 366

Matroid Union 369

Exercises 372

8.3 Ramsey Theory 378

The Pigeonhole Principle Revisited 378

Ramsey's Theorem 380

Ramsey Numbers 383

Graph Ramsey Theory 386

Sperner's Lemma and Bandwidth 388

Exercises 392

8.4 More Extremal Problems 396

Encodings of Graphs 397

Branchings and Gossip 404

List Coloring and Choosability 408

Partitions Using Paths and Cycles 413

Circumference 416

Exercises 422

8.5 Random Graphs 425

Existence and Expectation 426

Properties of Almost All Graphs 430

Threshold Functions 432

Evolution and Graph Parameters 436

Connectivity,Cliques,and Coloring 439

Martingales 442

Exercises 448

8.6 Eigenvalues of Graphs 452

The Characteristic Polynomial 453

Linear Algebra of Real Symmetric Matrices 456

Eigenvalues and Graph Parameters 458

Eigenvalues of Regular Graphs 460

Eigenvalues and Expanders 463

Strongly Regular Graphs 464

Exercises 467

Appendix A Mathematical Background 471

Sets 471

Quantifiers and Proofs 475

Induction and Recurrence 479

Functions 483

Counting and Binomial Coefficients 485

Relations 489

The Pigeonhole Principle 491

Appendix B Optimization and Complexity 493

Intractability 493

Heuristics and Bounds 496

NP-Completeness Proofs 499

Exercises 505

Appendix C Hints for Selected Exercises 507

General Discussion 507

Supplemental Specific Hints 508

Appendix D Glossary of Terms 515

Appendix E Supplemental Reading 533

Appendix F References 567

Author Index 569

Subject Index 575