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

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