|
|
|
|
|
| 内容提要： |
本书介绍了图论的常用主题，同时也包含一些尚需进一步研究或未解决的议题，用于激发学生的创新能力。全书共分13章，前3章介绍一些基础知识，后面章节介绍了树、连通性、可遍历性、子图、匹配和因子分解、可平面性、图的着色、拉姆齐数、距离及控制等内容。本书内容全面，证明与应用实例并举，还给出了证明技巧，书的最后提供了奇数题号的解答或提示。
本书可作为本科生一学期课程教材，也可供图论爱好者自学使用。 |
| |
|
| 目录： |
1. Introduction
1.1. Graphs and Graph Models 1
1.2. Connected Graphs 9
1.3. Common Classes of Graphs 19
1.4. Multigraphs and Digraphs 26
2. Degrees
2.1. The Degree of a Vertex 31
2.2. Regular Graphs 38
2.3. Degree Sequences 43
2.4. Excursion:Graphs and Matrices 48
2.5. Exploration:Irregular Graphs 50
3. Isomorphic Graphs
3.1. The Definiition of Isomorphism 55
3.2. Isomorphism as a Relation 63
3.3. Excursion:Graphs and Groups 66
3.4. Excursion:Reconstruction and Solvability 76
4. Trees
4.1. Bridges 85
4.2. Trees 87
4.3. The Minimum Spanning Tree Problem 94
4.4. Excursion:The Number of Spanning Trees 101
5. Connectivity
5.1. Cut-Vertices 107
5.2. Blocks 111
5.3. Connectivity 115
5.4. Menger's Theorem 124
5.5. Exploration:Geodetic Sets 130
6. Traversability
6.1. Eulerian Graphs 133
6.2. Hamiltonian Graphs 140
6.3. Exploration:Hamiltonian Walks and Numbers 152
6.4. Excursion:The Early Books of Graph Theory 156
7. Digraphs
7.1. Strong Digraphs 161
7.2. Tournaments 169
7.3. Excursion:Decision-Making 176
7.4. Exploration:Wine Bottle Problems 180
8. Matchings and Factorization
8.1. Matchings 183
8.2. Factorization 194
8.3. Decompositions and Graceful Labelings 209
8.4. Excursion:Instant Insanity 214
8.5. Excursion:The Petersen Graph 219
8.6. Exploration:γ-Labelings of Graphs 224
9. Planarity
9.1. Planar Graphs 227
9.2. Embedding Graphs on Surfaces 241
9.3. Excursion:Graph Minors 249
9.4. Exploration:Embedding Graphs in Graphs 253
10. Coloring
10.1. The Four Color Problem 259
10.2. Vertex Coloring 267
10.3. Edge Coloring 280
10.4. Excursion:The Heawood Map Coloring Theorem 288
10.5. Exploration:Local Coloring 293
11. Ramsey Numbers
11.1. The Ramsey Number of Graphs 297
11.2. Turan's Theorem 307
11.3. Exploration:Rainbow Ramsey Numbers 314
11.4. Excursion:Erdos Numbers 321
12. Distance
12.1. The Center of a Graph 327
12.2. Distant Vertices 333
12.3. Excursion:Locating Numbers 341
12.4. Excursion:Detour and Directed Distance 346
12.5. Exploration:Channel Assignment 351
12.6. Exploration:Distance Between Graphs 357
13. Domination
13.1. The Domination Number of a Graph 361
13.2. Exploration:Stratification 372
13.3. Exploration:Lights Out 377
13.4. Excursion:And Still It Grows More Colorful 381
Solutions and Hints for Odd-Numbered Exercises 397
References 425
Index of Names 437
Index of Mathematical Terms 440
List of Symbols 447 | |
【关闭】 |
|
