图论 英文版PDF电子书下载

Chapter Ⅰ Graphs and Subgraphs 1

Ⅰ.1 Definitions 1

Ⅰ.2 Isomorphism 5

Ⅰ.3 Subgraphs 9

Ⅰ.4 Vertices of attachment 11

Ⅰ.5 Components and connection 14

Ⅰ.6 Deletion of an edge 18

Ⅰ.7 Lists of nonisomorphic connected graphs 22

Ⅰ.8 Bridges 27

Ⅰ.9 Notes 30

Exercises 31

References 31

Chapter Ⅱ Contractions and the Theorem of Menger 32

Ⅱ.1 Contractions 32

Ⅱ.2 Contraction of an edge 37

Ⅱ.3 Vertices of attachment 41

Ⅱ.4 Separation numbers 43

Ⅱ.5 Menger's Theorem 46

Ⅱ.6 Hall's Theorem 50

Ⅱ.7 Notes 52

Exercises 53

References 53

Chapter Ⅲ 2-Connection 54

Ⅲ.1 Separable and 2-connected graphs 54

Ⅲ.2 Constructions for 2-connected graphs 56

Ⅲ.3 Blocks 60

Ⅲ.4 Arms 64

Ⅲ.5 Deletion and contraction of an edge 66

Ⅲ.6 Notes 68

Exercises 68

References 69

Chapter Ⅳ 3-Connection 70

Ⅳ.1 Multiple connection 70

Ⅳ.2 Some constructions for 3-connected graphs 74

Ⅳ.3 3-blocks 83

Ⅳ.4 Cleavages 95

Ⅳ.5 Deletions and contractions of edges 104

Ⅳ.6 The Wheel Theorem 111

Ⅳ.7 Notes 113

Exercises 114

References 114

Chapter Ⅴ Reconstruction 115

Ⅴ.1 The Reconstruction Problem 115

Ⅴ.2 Theory and practice 118

Ⅴ.3 Kelly's Lemma 119

Ⅴ.4 Edge-reconstruction 122

Ⅴ.5 Notes 123

Exercises 124

References 124

Chapter Ⅵ Digraphs and Paths 125

Ⅵ.1 Digraphs 125

Ⅵ.2 Paths 129

Ⅵ.3 The BEST Theorem 133

Ⅵ.4 The Matrix-Tree Theorem 138

Ⅵ.5 The Laws of Kirchhoff 142

Ⅵ.6 Identification of vertices 149

Ⅵ.7 Transportation Theory 152

Ⅵ.8 Notes 158

Exercises 159

References 159

Chapter Ⅶ Alternating Paths 161

Ⅶ.1 Cursality 161

Ⅶ.2 The bicursal subgraph 163

Ⅶ.3 Bicursal units 167

Ⅶ.4 Alternating barriers 168

Ⅶ.5 f-factors and f-barriers 170

Ⅶ.6 The f-factor theorem 174

Ⅶ.7 Subgraphs of minimum deficiency 178

Ⅶ.8 The bipartite case 180

Ⅶ.9 A theorem of Erd？s and Gallai 181

Ⅶ.10 Notes 183

Exercises 183

References 184

Chapter Ⅷ Algebraic Duality 185

Ⅷ.1 Chain-groups 185

Ⅷ.2 Primitive chains 188

Ⅷ.3 Regular chain-groups 194

Ⅷ.4 Cycles 197

Ⅷ.5 Coboundaries 200

Ⅷ.6 Reductions and contractions 204

Ⅷ.7 Algebraic duality 206

Ⅷ.8 Connectivity 209

Ⅷ.9 On transportation theory 215

Ⅷ.10 Incidence matrices 217

Ⅷ.11 Matroids 218

Ⅷ.12 Notes 219

Exercises 219

References 220

Chapter Ⅸ Polynomials Associated with Graphs 221

Ⅸ.1 V-functions 221

Ⅸ.2 The chromatic polynomial 226

Ⅸ.3 Colorings of graphs 233

Ⅸ.4 The flow polynomial 237

Ⅸ.5 Tait colorings 240

Ⅸ.6 The dichromate of a graph 243

Ⅸ.7 Some remarks on reconstruction 248

Ⅸ.8 Notes 250

Exercises 251

References 251

Chapter Ⅹ Combinatorial Maps 253

Ⅹ.1 Definitions and preliminary theorems 253

Ⅹ.2 Orientability 257

Ⅹ.3 Duality 259

Ⅹ.4 Isomorphism 261

Ⅹ.5 Drawings of maps 263

Ⅹ.6 Angles 268

Ⅹ.7 Operations on maps 268

Ⅹ.8 Combinatorial surfaces 275

Ⅹ.9 Cycles and coboundaries 281

Ⅹ.10 Notes 283

Exercises 284

References 284

Chapter Ⅺ Planarity 285

Ⅺ.1 Planar graphs 285

Ⅺ.2 Spanning subgraphs 288

Ⅺ.3 Jordan's Theorem 290

Ⅺ.4 Connectivity in planar maps 296

Ⅺ.5 The cross-cut Theorem 306

Ⅺ.6 Bridges 311

Ⅺ.7 An algorithm for planarity 314

Ⅺ.8 Peripheral circuitsin 3-connected graphs 317

Ⅺ.9 Kuratowski's Theorem 320

Ⅺ.10 Notes 325

Exercises 325

References 326

Index 327