THEORY OF GRAPHSPDF电子书下载

Chapter 1 FUNDAMENTAL CONCEPTS 1

1．1 Graph definitions 1

1．2 Local degrees 7

1．3 Subgraphs 12

1．4 Binary relations 13

1．5 Incidence matrices 18

Chapter 2 CONNECTEDNESS 22

2．1 Sequences,paths and arcs 22

2．2 Connected components 23

2．3 One-to-one correspondences 25

2．4 Distances 27

2．5 Elongations 31

2．6 Matrices and paths．Product graphs 33

2．7 Puzzles 36

Chapter 3 PATH PROBLEMS 38

3．1 Euler paths 38

3．2 Euler paths in infinite graphs 42

3．3 An excursion into labyrinths 47

3．4 Hamilton circuits 52

Chapter 4 TREES 58

4．1 Properties of trees 58

4．2 Centers in trees 62

4．3 The circuit rank 67

4．4 Many-to-one correspondences 68

4．5 Arbitrarily traceable graphs 74

Chapter 5 LEAVES AND LOBES 78

5．1 Edges and vertices of attachment 78

5．2 Leaves 81

5．3 Homomorphic graph images 83

5．4 Lobes 85

5．5 Maximal circuits 89

Chapter 6 THE AXIOM OF CHOICE 92

6．1 Well-ordering 92

6．2 The maximal principles 94

6．3 Chain sum properties 96

6．4 Maximal exclusion graphs 100

6．5 Maximal trees 101

6．6 Interrelations between maximal graphs 103

Chapter 7 MATCHING THEOREMS 106

7．1 Bipartite graphs 106

7．2 Deficiencies 108

7．3 The matching theorems 110

7．4 Mutual matchings 113

7．5 Matchings in special graphs 117

7．6 Bipartite graphs with positive deficiencies 121

7．7 Applications to matrices 125

7．8 Alternating paths and maximal matchings 132

7．9 Separating sets 138

7．10 Simultaneous matchings 139

Chapter 8 DIRECTED GRAPHS 145

8．1 The inclusion relation and accessible sets 145

8．2 The homomorphism theorem 149

8．3 Transitive graphs and embedding in order relations 150

8．4 Basis graphs 152

8．5 Alternating paths 156

8．6 Subgraphs of first degree 159

Chapter 9 ACYCLIC GRAPHS 162

9．1 Basis graphs 162

9．2 Deformations of paths 163

9．3 Reproduction graphs 166

Chapter 10 PARTIAL ORDER 170

10．1 Graphs of partial order 170

10．2 Representations as sums of ordered sets 170

10．3 Lattices and lattice operations．Closure relations 175

10．4 Dimension in partial order 178

Chapter 11 BINARY RELATIONS AND GALOIS CORRESPONDENCES 183

11．1 Galois correspondences 183

11．2 Galois connections for binary relations 187

11．3 Alternating product relations 191

11．4 Ferrers relations 193

Chapter 12 CONNECTING PATHS 197

12．1 The cross-path theorem 197

12．2 Vertex separation 200

12．3 Edge separation 202

12．4 Deficiency 203

Chapter 13 DOMINATING SETS,COVERING SETS AND INDEPENDENT SETS 206

13．1 Dominating sets 206

13．2 Covering sets and covering graphs 208

13．3 Independent sets 210

13．4 The theorem of Turan 214

13．5 The theorem of Ramsey 216

13．6 A problem in information theory 220

Chapter 14 CHROMATIC GRAPHS 224

14．1 The chromatic number 224

14．2 Sums of chromatic graphs 227

14．3 Critical graphs 229

14．4 Coloration polynomials 234

Chapter 15 GROUPS AND GRAPHS 239

15．1 Groups of automorphisms 239

15．2 Cayley＇s color graphs for groups 242

15．3 Graphs with prescribed groups 244

15．4 Edge correspondences 245

BIBLIOGRAPHY 250

LIST OF CONCEPTS 265

INDEX OF NAMES 269